# On slightly stronger form of the converse of Fermat's little theorem [duplicate]

Fom wiki Fermat's little theorem, the theorem is as follows: If there exists an integer $$a$$ such that $$a^{p-1}\equiv 1\pmod p$$ and for all primes $$q$$ dividing $$p − 1$$ one has $${\displaystyle a^{(p-1)/q}\not \equiv 1{\pmod {p}},}$$ then $$p$$ is prime.

How to prove this theorem?

• Do you know about Euler's theorem? It says that $a^{\phi(n)} \equiv 1 \; (\textrm{mod} \; n)$ for all $a \in \mathbf{Z}$ where $\phi$ is Euler's totient function. Using this and the fact that $\phi(n) = n - 1$ if and only if $n$ is prime, you can prove your theorem! Feb 17 at 7:44
• @JosephHarrison Yes I know Euler's theorem. Feb 17 at 8:37
• @JosephHarrison Nothing made. Feb 17 at 12:42
• @JosephHarrison Yes I looked at that answer, but it seems that answer doen't helps. Feb 19 at 2:57
• @miket If $a^{p - 1} \equiv 1 \mod{p}$, then $\phi(p)$ divides $p - 1$. Writing $p - 1 = k\phi(p)$ for some integer $k$, if $k > 1$ then it is divisible by a prime $q$. Then $(p - 1)/q = k\phi(p)/q$, the latter of which is a multiple of $\phi(p)$ and so $a^{(p - 1)/q} \equiv 1 \mod{p}$, against assumption. Therefore we must have $k = 1$ so that $\phi(p) = p - 1$ and $p$ is prime. I hope this helps! Feel free to ask for clarifications. Feb 19 at 19:38