MHB What is the remainder when 1992 is divided by 92 using the CRT?

[Suvadip]

Find the remainder when 19⁹² is divided by 92

 

[Evgeny.Makarov]

One way is to find remaindes of $19^2$, $19^{2^2}$, $19^{2^3}$ and so on. For example, $19^2=361\equiv-7\pmod{92}$, $19^4\equiv(-7)^2=49\pmod{92}$, etc. Then write 92 in binary: $92=2^6+2^4+2^3+2^2$. So, you need to compute the remainder of $19^{2^6}\cdot19^{2^4}\cdot19^{2^3}\cdot19^{2^2}$. That is, use two tricks: take the remainder after each multiplication and use smart exponentiation by taking consecutive squares instead of multiplying 19 by itself 92 times.

Another way is to use Euler's theorem: $19^{\varphi(92)}\equiv1\pmod{92}$. Here $\varphi(92)=92\left(1-\frac{1}{2}\right)\left(1-\frac{1}{23}\right)=44$. So, $19^{88}\equiv1\pmod{92}$ and you only need to compute $19^4\pmod{92}$.

 

[Deveno]

Continuing Evgeny's comment, note that:

[math]19^2 \equiv 361 \equiv 85 \equiv -7\ (\text{mod }92)[/math]

(I have a profound dislike of "big numbers").

It follows that:

[math]19^{92} \equiv 19^4 \equiv (19^2)^2 \equiv 49\ (\text{mod }92)[/math].

EDIT: I must learn to read someday, this was implicit in the first post. I'll go crawl under a rock now...

 

[I like Serena]

Alternatively, the Chinese Remainder Theorem (CRT) says we can split up $92$ into $2^2 \cdot 23$.

If you're not learning about the CRT you might as well stop reading now, since my explanation is rather concise. Sorry.
Since I rather like CRT, I'll continue.

More specifically, CRT says that $19^{92} \pmod{92}$ can be (isomorphically) mapped to:
$$(19^{92} \text{ mod }4,\ 19^{92} \text{ mod } 23) \equiv ((-1)^{92} \text{ mod } 4,\ (-4)^{92 \text{ mod } 22} \text{ mod } 23) \equiv (1 \text{ mod } 4, 3 \text{ mod } 23)$$

The solutions from the 2nd argument are one of $3, 26, 49, 72$.
Only $49$ fits the first argument.

Therefore $19^{92} \equiv 49 \pmod{92}$.