Welcome to our community

Be a part of something great, join today!

to find the remainder

suvadip

Member
Feb 21, 2013
69
Find the remainder when 1992 is divided by 92
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
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....
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,780
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}$.