As 3 and 5 are coprimes
So
3^4 = 1 mod 5
3^{4k+1} = 3 mod 5
3^{4k+2}= 4 mod 5
3^{4k+3}
= 2 mod 5
Now (5k+m)^2 mod 5 = 0 if m=
0, 1 if m= 1 or 4, 4 if m = 2 or 3 mod 5
now 3^x= x^2 mod 5
if
x = 4k that is 0 mod 4 and 1 mod 5 ( in both cases
remainder 1)
or x = 4k and 4 mod 5( in both cases remainder 1)
or x = 4k+2 or 2 mod 4 and 2or 3 mod 5
x = 0 mod 4 and 1 mod
5 => x= 16 mod 20
or x = 4k and 4 mod 5 => x = 4 mod 20
or x =2 mod 5 and 2 mod 4 => x = 2 mod 20
or x =
2 mod 4 and 3 mod 5 => x= 18 mod 20
x
= a mod 4 ,b mod 5 can be solved by Chinese remainder theorem
I
have not detailed steps
No comments:
Post a Comment