I want to show that 17^21 + 19^21 is divisible by 36 by actual computation of the integers and getting the remainder by division. Is it possible in MATLAB?

5 次查看（过去 30 天）
Seetha Rama Raju Sanapala
评论： Jon 2015-10-2
I want to show that 17^21 + 19^21 is divisible by 36 by actual computation of the integers and getting the remainder and quotient by division. Is it possible in MATLAB? I know to prove by algebra. But I want to compute the actual values. My machine is 64 bit. uint64 saturates for these numbers and you dont get the exact values.
  3 个评论
显示 1更早的评论
Jon
Jon 2015-10-2
Technically nothing I stated was wrong, but I concede I had no business answering this question. Nice answer below.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

John D'Errico
John D'Errico 2015-10-1
Jon was wrong in his comment. Why? I'll show the true answer using my vpi toolbox.
vpij(17)^21 + vpij(19)^21
ans =
783301429606381938554583636
See that the number is large. Larger than you can store in a double. The limit of a double to represent a number as a flint (a floating point number that represents an exact integer, and does so with no error) is 2^53 - 1.
log2((17)^21 + (19)^21)
ans =
89.34
In fact, the above shows the number is too large to be stored in a uint64, which would be limited to 64 bits.
Is it divisible by 36? Yes. Again, my vpi toolbox gives a result that you can trust.
mod(vpi(17)^21 + vpi(19)^21,36)
ans =
0
Can we know this is true using only arithmetic based on doubles? Yes. It is not even that terribly difficult, just a short loop.
m17 = 1;
m19 = 1;
for i = 1:21
m17 = mod(m17*17,36);
m19 = mod(m19*19,36);
end
mod(m17 + m19,36)
ans =
0
So clearly this is quite doable using only small integers and a short loop, all of which numbers fit easily into a double. In fact, we could have done the computation using uint16 integers, since nothing in that computation could possibly ever be larger than 18*19+16*17=614.
Had the exponent been larger, it is actually possible to do the computation efficiently in O(log2( p)), where p is the exponent. Of course, the loop I wrote above is only O( p), so not as good if p were immensely large.
Walter Roberson
Walter Roberson 2015-10-1
John D'Errico will probably mention his Variable Precision Integer package from the File Exchange.
You can also proceed using the Symbolic Toolbox:
S = sym(17)^21 + sym(19)^21;
mod(S, 36)

类别

在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by