Asked by Aakash
Find the remainder when (19)^92 is divided by 92.
Answers
Answered by
Leo Galleguillos
Interesting. Do you know how to get started on this problem?
Answered by
Rohit ranjan
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