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.