Question

Find the remainder when (19)^92 is divided by 92.

Answer 1

Interesting. Do you know how to get started on this problem?

Answer 2

Chinese Remainder theorem (along with other results). First note 92= 4 × 23 with gcd
(4,23) =1. Let us call N= 1992. We will compute, N(mod 4) and N (mod 23) and then use CRT to
compute N (mod 92).
First, N (mod 4) = (19)
92( 𝑚𝑜𝑑 4) = (−1)
92(𝑚𝑜𝑑 4) = 1
and 𝑁(𝑚𝑜𝑑 23) = 194
.[(19)
22 (𝑚𝑜𝑑 23)]
2
(𝑚𝑜𝑑 23) = (−4)
4
(𝑚𝑜𝑑 23) = (16)
4
(𝑚𝑜𝑑 23) = (−7)
2
(𝑚𝑜𝑑 23) = 49
(𝑚𝑜𝑑 23) = 3.
Note in the above we have used Fermat’s Little Theorem. Now, If you know CRT, you can
directly say 𝑁( 𝑚𝑜𝑑 92) = 49.
If not, you can compute it. One way to do it is write down two lists of numbers (one for each
relation) and pick out the first common number