Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
3  
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
1  
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
show 2 more comments

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.