# If $a^k\equiv a\mod p$ for all $a$, show $(p - 1)\mid (k-1)$

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!

• You are clearly assuming that $p$ is prime, but you should say so! Commented Mar 17, 2023 at 13:38

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.
• The second paragraph is at the hart of most of the proofs that $U(p)$ is cyclic, so it is as "advanced" as the one to be avoided. Commented Mar 17, 2023 at 21:09
• @Devo I disagree, though, as mentioned in my solution, I agree that the same core principle underlies both arguments. The standard proof of the Primitive root theorem requires abstraction...namely, you must introduce a new function which counts the elements of a given order and then you argue that this must coincide with Euler's totient function, for which you must prove that $\sum_{d|n}\varphi(d)=n$ which, again, is quite abstract and non-trivial. My argument rests only on a basic fact of Field Algebra. Since the claim is false for composites, I think one needs something like this.