5
$\begingroup$

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.

  • 0
    Maybe the exponent was meant to be 2147483648.2012-08-28

2 Answers 2

1

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.

1

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

  • 0
    Of course, using CRT and the known factorization of $F_5$ we get away with using even smaller integers - again aiding calculation by hand.2012-08-28