Sunday, September 2, 2012

find x such that 3^x-x^2 is divisible by 5?

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: