Let a,b,n be integers with n>1 and let d=gcd(a,n). If the equation [a]x=[b] has a solution in Z/nZ, prove that d divides b.
-
To say that [a]x = [b] has a solution in Z/nZ means that there is an integer p with the property that ap is congruent to b mod n. This in turn means that ap - b is a multiple of n, and hence that there is an integer q with the property that ap - b = qn. Moving b to the right hand side and qn to the left we conclude from the given information that there are integers p and q satisfying
b = ap - qn.
By definition of d, we know that d divides both a and n. So d divides both ap and qn, and hence their difference, and hence b.
b = ap - qn.
By definition of d, we know that d divides both a and n. So d divides both ap and qn, and hence their difference, and hence b.