Find remainder of $29^{282239}$ mod $68600$

Question

I am trying to solve example in title. I know from wolfram alpha that result is 63869. By applying Euler's phi formula I get $ \varphi(68600) = 23520 $, so the number $29^{282239}$ gives same remainder as the number $29^{23519}$, but this number still is not computable by calculator. How can I proceed to compute the remainder? Thank you

Answer 1

Note that $282239 \equiv 23519 \equiv -1 \pmod{\phi(68600)}.$ So you really just have to find $29^{-1} \pmod{68600}.$ So solve the Diophantine equation

$$29x+68600 y = 1$$

to get $x=63869.$

Answer 2

Note that $68\,600=2^3\times5^2\times7^3$. So, compute the remainders of the division of $29^{282\,239}$ by $2^3$, by $5^2$, and by $7^3$. Then use the Chinese Remainder Theorem.

Answer 3

$$68600=7^3\cdot5^2\cdot8$$

As $\phi(25)=20$ and $2882239\equiv-1\pmod{20},$

$$\implies29^{2882239}\equiv29^{-1}\pmod{25}\equiv-7\equiv18\ \ \ \ (1)$$

As $\lambda(8)=2,2882239\equiv1\pmod2$

$$\implies29^{2882239}\equiv29\pmod8\equiv5\ \ \ \ (2)$$

Finally as $\phi(7^3)=294$ and $2882239\equiv157\pmod{294}$

$$29^{2882239}\equiv29^{157}\pmod{7^3}$$

Now as $29^{157}=(1+4\cdot7)^{157}\equiv1+\binom{157}128++\binom{157}228^2\pmod{7^3}\equiv?\ \ \ \ (3)$

Finally apply CRT on $(1),(2),(3)$

Answer 4

So you have found that $282~239$ modulo $23~520$ is actually $23~520 - 1$. You know from the Totient theorem that $$29^{23~520}\equiv 1\mod 68~600$$ This means that $$29^{23~519}\equiv 29^{-1}\mod 68~600.$$

Doing out the GCD steps we find that:

68600 = 15 + 2365 * 29 
      = 15 + 2365 * (14 + 1 * 15)
      = 15 + 2365 * (14 + 1 * (14 + 1))

at which point we find out that the GCD is 1, which is not terribly surprising given that 29 is prime and not a factor of 68600. But what this lets you do is to reverse these steps to find the modular inverse, since you know:

-1 * 14 + 1 * 15 = 1    (starting point)
-1 * (29 - 15) + 15 = 1 (substitute expression you got for 29)
-1 * 29 + 2 * 15 = 1    (new starting point)
-1 * 29 + 2 * (68600 - 2365 * 29) = 1  (repeat)
(-1 + 2 * -2365) * 29 + 2 * 68600 = 1  (rearranged)
-4731 * 29 + 2 * 68600 = 1 (ending point)

Thus $-4~731$ is the multiplicative inverse of $29$ modulo $68~600$ and you just need to convert it to a positive number to make your teacher happy.