Problem statement. Suppose that $k$ is a positive integer and $p$ a prime such that $a^k\equiv a\mod p$ for all positive integers $a$. Show that $(p - 1)$ divides $(k-1)$.
The proof is simple if we can use the fact that $U(p):=(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic. In that case, we simply observe that $|U(p)|=p-1$ and select any generator $a$. It is a well-known result that if in a finite cyclic group generated by $a$ we have $a^i=a^j$, then the order of $a$ divides $i-j$. Hence $p-1$ divides $k-1$.
The problem is, the student who needs to prove this result isn't allowed to use the fact that $U(p)$ is cyclic. And all the proofs I know for $U(p)$ being cyclic are way too advanced for him, so he isn't able to prove it for himself. Hence I am asking:
Question. Is there an elementary proof of the above, appropriate to an undergraduate abstract algebra course, that doesn't use the fact that $U(p)$ is cyclic?
(Then again, maybe I am wrong that it is too advanced for him to prove that $U(p)$ is cyclic. If you have any ideas there, they are welcome too.)
Thanks guys!
Well...Since, for non-zero $a$, we have $a^{p-1}\equiv a^{k-1}\equiv 1\pmod p$ we can deduce that $a^d\equiv 1 \pmod p$ for $d=\gcd(p-1,k-1)$. Here, of course, $1≤d≤p-1$.
But you know that $\mathbb Z/p\mathbb Z$ is a field (at least, I assume your students know that) so $a^d\equiv 1 \pmod p$ can't have more than $d$ roots. The desired conclusion follows.
That's the same principle which underlies the standard proof that primitive roots exist, but this case is more elementary (I'd say). Indeed, this argument might serve as a good introduction to the proof of the primitive root theorem.