Thread: congruence problem

Hi,

Find an x which satisfies 13^x = 13 mod 5003^2.

I started by noting that the same x will solve 13^(x - 1) = 1 mod 5003^2.

Since 5003 is prime and of course does not divide 13, we know that 13^(5002) = 13^(5003 - 1) = 1 mod 5003.

I'm not sure how to move from mod 5003 to mod 5003^2, though i'm kind of guessing that the answer is x = 5002 for the 5003^2 case, but i'm not sure. does anyone know what to do or know of a useful theroem? Thanks.

The totient function (phi(n)) is the number of integers less than and relatively prime to n. It's known that for an integer relatively prime to the modulus, a^phi(n) = 1 mod n. For instance, for a prime p, phi(p) = p-1 and
a^(p-1) = 1 mod p. In your case the modulus is of the form p^2, and phi(p^2) = p^2 - p. So an x that would solve your equation is:
5003^2 - 5003 + 1.

?

yeah you are right x=1 works, but i forgot to add that you have to find an x greater than 1