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

  • Thread starter Thread starter Suvadip
  • Start date Start date
  • Tags Tags
    Remainder
AI Thread Summary
The remainder when 1992 is divided by 92 can be calculated using the Chinese Remainder Theorem (CRT) and Euler's theorem. By computing powers of 19 modulo 92, it is determined that 19^2 is congruent to -7, leading to further calculations that show 19^4 is congruent to 49 modulo 92. The CRT approach confirms that 19^92 modulo 4 and 23 yields consistent results, ultimately leading to the conclusion that 19^92 is congruent to 49 modulo 92. Thus, the remainder when 1992 is divided by 92 is 49.
Suvadip
Messages
68
Reaction score
0
Find the remainder when 1992 is divided by 92
 
Mathematics news on Phys.org
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}$.
 
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...
 
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}$.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top