Let $p$ be a prime and $k$a positive ingeger such that $a^k=a (mod p)$ for all integers a. prove that $p-1$divides $k-1$

Question

Attempt : by Fermat's little theorem we can obtain following equaility $$ a^{k-1}=e=a^{p-1} $$ (mod $p$)

Now, by devision algorithm

$k-1=(p-1)q+r $

$(0 \le r \lt p-1)$

then $$a^{k-1}=a^{(p-1)q+r}$$

$$=a^{(p-1)q}a^r$$

$$=a^r=e (mod p)$$ I want to show $r$ must be zero but I 'm lack of information about $r$ can you give me more hint ? I'd appreciate for hint in any other way than my method

Answer 1

Hint: If $a^r\equiv 1\bmod p$ for all $a\not\equiv 0\bmod p$ (I'm assuming that what you've proven, I find it a bit hard to follow your argument exactly), what happens when $a$ is a primitive root $\bmod p$? When is a power of a primitive root $\equiv 1\bmod p$?