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?

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.

[Jon]

Not sure exactly what you're looking for, and I'm not sure that this doesn't suffer the same problems you stated, but

rem((17^21 + 19^21),36)

says the remainder is 24.

[John D'Errico]

@Jon - Sorry, but you are simply wrong here. Those numbers overflow the precision available to a double.

[Jon]

Technically nothing I stated was wrong, but I concede I had no business answering this question. Nice answer below.

Answer 1

[John D'Errico]

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.

Answer 2

[Walter Roberson]

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)

[John D'Errico]

:)

Or its successor, vpij. But you can also do it using uint16 integers.