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:

\(\displaystyle 19^2 \equiv 361 \equiv 85 \equiv -7\ (\text{mod }92)\)

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

It follows that:

\(\displaystyle 19^{92} \equiv 19^4 \equiv (19^2)^2 \equiv 49\ (\text{mod }92)\).

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}$.

 

[CellCoree]

The Chinese Remainder Theorem (CRT) is a mathematical tool that is used to find the remainder when a number is divided by multiple divisors. In this case, the CRT can be applied to find the remainder when 1992 is divided by 92.

To use the CRT, we first need to find the prime factors of both 1992 and 92. The prime factorization of 1992 is 2^3 * 3 * 83 and the prime factorization of 92 is 2^2 * 23.

Next, we need to find the least common multiple (LCM) of the two divisors, which is 2^3 * 3 * 23 * 83. Then, we can use the CRT formula to find the remainder:

Remainder = (1992 mod 2^3) * (92 mod 2^2) * (92 mod 23) * (92 mod 83) mod 2^3 * 3 * 23 * 83

= (0) * (0) * (0) * (92) mod 2^3 * 3 * 23 * 83

= 0 mod 2^3 * 3 * 23 * 83

= 0

Therefore, the remainder when 1992 is divided by 92 using the CRT is 0. This means that 1992 is evenly divisible by 92, and there is no remainder.

In conclusion, the Chinese Remainder Theorem is a useful tool for finding the remainder when a number is divided by multiple divisors. In the case of 1992 divided by 92, the remainder is 0.