Can anybody help me out with this number theory question? My question is as follows:
If $n$ is a positive integer and if an integer $x$ exists such that $x^{n-1}\equiv 1 \pmod n$ and $x^{\frac{n-1}{q}} \neq 1 \pmod n$ for all prime divisors $q$ of $n-1$, then $n$ is prime.
I believe we have to use some reasoning on the order of $x$, but I don't know where to start. Thanks!