Find the remainder when (19)^92 is divided by 92.
2 answers
Interesting. Do you know how to get started on this problem?
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
(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
0 answers