# Finding the congruence with a large power modulo a large integer

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.

-
Did the large numbers come from somewhere in particular? – anon Aug 27 '12 at 21:05
Have you tried using a software package such as Pari/gp? – Old John Aug 27 '12 at 21:06
Is that meant to be $\pmod {4292967297}$ rather than $\pmod{4294967297}$? I ask because $2146483648 \times 2 = 4292967296$, which is quite suggestive. – Clive Newstead Aug 27 '12 at 21:09
In fact $4294967297=2^{32}+1=641\times6700416$, the first Fermat non-prime is suggestive too. – Marc van Leeuwen Aug 27 '12 at 21:33
By simple Chinese powering my computer finds $3^{2146483648} \mod 4294967297=274353412$ (and also $3^{2146483648} \mod 4292967297=158085774$); did it make a mistake? – Marc van Leeuwen Aug 27 '12 at 21:41

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

-
Of course, using CRT and the known factorization of $F_5$ we get away with using even smaller integers - again aiding calculation by hand. – Jyrki Lahtonen Aug 28 '12 at 5:22