How would I reduce the following modulus:
$3^{2146483648} \pmod {4294967297}$
It's supposed to end up being congruent to 10,324,303 but I'm having some difficulty getting there via Euler's phi function reduction.
How would I reduce the following modulus:
$3^{2146483648} \pmod {4294967297}$
It's supposed to end up being congruent to 10,324,303 but I'm having some difficulty getting there via Euler's phi function reduction.
Maple says, $3^{2147483648}\equiv10324303\pmod{4294967297}$ Note that the 4th digit of the exponent is 7, not 6.
I don't see any nice way to do this. As Marc points out, $4294967297=641\times6700417$ both of those factors being prime. Then $\phi(4294967297)=640\times6700416=4288266240$ so by Euler $3^{4288266240}\equiv1\pmod{4294967297}$ but I don't see how to make use of this. Alternatively, ${\rm lcm}(640,6700416)=33502080$ so $3^{33502080}\equiv1\pmod{4294967297}$ Then $2147483648\equiv3350528\pmod{33502080}$ so $3^{2147483648}\equiv3^{3350528}\pmod{4294967297}$ and now what do we do? Another way is to work modulo 641 and modulo 6700417 individually and then put the results together using the Chinese Remainder Theorem, but I think the calculations aren't much easier that way. So I'm stumped as to how to get the answer without just letting a machine do it for you.
I am assuming that the exponent is meant to be $2^{31}$ and the modulus is $2^{32}+1$. Repeated squaring will then take you there reasonably fast and (more importantly) without the intermediate results blowing up on your face. A younger version of yours truly might have enjoyed the task of doing it by hand, but now I prefer to use Mathematica:
In[1]:= m=2^32+1
Out[1]=4294967297
In[2]:=t=3;
In[3]:=For[i=1,i<32,++i,t=Mod[t^2,m]]
In[4]:=t
Out[4]=10324303