Question

Can someone please help with this question, with a explicit solution?
4^k is congruent to 1 (mod 19), solve for the smallest positive integer k; thx so much~~

Answer 1

Simply go through the possible values for k = 0, 1, 2, 3..., 18, 19

4^0 = 1 (mod 19)


4^1 = 4 (mod 19)


4^2 = 16 (mod 19)
4^2 = -3 (mod 19)


4*4^2 = -3*4 (mod 19)
4^3 = -12 (mod 19)
4^3 = 7 (mod 19)


(4^2)^2 = (-3)^2 (mod 19)
4^(2*2) = 9 (mod 19)
4^4 = 9 (mod 19)


(4^4)^2 = (9)^2 (mod 19)
4^(4*2) = 81 (mod 19)
4^8 = 5 (mod 19)


4*4^8 = 4*5 (mod 19)
4^(1+8) = 20 (mod 19)
4^9 = 1 (mod 19)


So the smallest integer is k = 9

Answer 2

Actually according to the fermat little theorem , we could easy conclude that k=18; so is there a easier way to find the smallest integer such that k=9?

Answer 3

well you can use the idea that if a^k = 1 (mod n) where gcd(a,n) = 1, then q | k for some integer q


This means that if you know that k = 18 is a solution, then some factor of 18 is also a solution.