as 3 and 5 are coprimes
so 3^4 = 1 mod 5 as per Fermats little theorem
now 3^(4k+1) = 3 mod 5
3^(4k+2) = 4 mod 5
3^(4k+3) = 2 mod 5
3^(4k) = 1 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 = 0 mod 4 and 1 mod 5 ( in both cases remainder 1)
or x = 0 mod 4 and 1 mod 5( in both cases remainder 1)
or x = 2 mod 4 and 2 or 3 mod 5
x = 0 mod 4 and 1 mod 5 => x= 16 mod 20 (checking 0,4,8,12,16)
or x = 0 mod 4 mod 5 => x = 4 mod 20 (checking 0,4,8,12,16)
x =2 mod 5 and 2 mod 4 => x = 2 mod 20 as remainders are 2
or x = 2 mod 4 and 3 mod 5 => x= 18 mod 20 (checking 2,6,10,14,18)
so solutions x = 2 mod 20, 4 mod 20, 18 mod 20, 16 mod 20
This could be solved by using Chinese remainder theorem but bing smapll number I checked for direct
No comments:
Post a Comment