Problem:
If $x^{n-1} \equiv 1 \pmod{n}$, and for all divisors $q$ of $n - 1$, $a^{q} \not\equiv 1 \pmod{n}$, then $n$ is prime. $(n > 1)$
I read the proof in the book and it was very straightforward; however, I wonder is there a way to prove it by just using congruence property?
And another related question about power residue:
If we have $a^{n - 1} \equiv 1 \pmod{n}$. Is there any relation between $n - 1$ and $\phi(n)$? Because I thought of $a^{\phi(n)} \equiv 1 \pmod{n}$, when $(a, n) = 1$. I try to think of away to connect these two ideas, but I still cannot see it.
Any idea?
Thanks,