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
    Did the large numbers come from somewhere in particular?2012-08-27
  • 0
    Have you tried using a software package such as Pari/gp?2012-08-27
  • 3
    Is that meant to be $\pmod {4292967297}$ rather than $\pmod{4294967297}$? I ask because $2146483648 \times 2 = 4292967296$, which is quite suggestive.2012-08-27
  • 1
    In fact $4294967297=2^{32}+1=641\times6700416$, the first Fermat non-prime is suggestive too.2012-08-27
  • 0
    By simple Chinese powering my computer finds $3^{2146483648} \mod 4294967297=274353412$ (and also $3^{2146483648} \mod 4292967297=158085774$); did it make a mistake?2012-08-27
  • 0
    @Marc, of course you meant 6700417.2012-08-28
  • 0
    Maybe the exponent was meant to be 2147483648.2012-08-28

2 Answers 2