# Let p be a prime and k a positive integer such that $a^k$mod p = a mod p for all integers a. Prove that p - 1 divides k - 1.

Let p be a prime and k a positive integer such that $a^k$mod p = a mod p for all integers a. Prove that p - 1 divides k - 1.

I think I need to use Fermat's Little Theorem, and I can get $a^k$mod p = $a^p$mod p, and I think it follows that $a^{k-1}$mod p = $a^{p-1}$mod p = 1, but from there I'm stumped.

I think it follows that $a^{k-1}$ = m$a^{p-1}$, but why couldn't m be a fraction, i.e. k - 1 divides p - 1 but not the other way around?

• You need more than Fermat's Little Theorem...you have to use the existence of an element of order $p-1$. See, eg, Primitive Roots – lulu Apr 6 '16 at 0:14
• By the way, 1289671298371298379182 is a semiprime. – астон вілла олоф мэллбэрг Apr 6 '16 at 0:16

The OP's solution is incorrect. This deduction is flawed:

"Multiplying both sides by $$a^{k-1}$$ $$a^{k-1}({a^{p-1}})^m=1a^{k-1} \implies a^{(k-1)+m(p-1)}=a^{k-1} \implies (k-1)+m(p-1) = k-1$$ by the definition $$x$$ mod $$(p-1)$$".

Here is a different approach. Let $$k-1=(p-1)q+r$$ for some non-negative integers $$q$$ and $$r$$ with $$r. If $$r\neq 0$$, then we have by Fermat's little theorem that $$a^{r+1}\equiv a^{r+(p-1)q+1}= a^{k}\equiv a\pmod{p}.$$ Therefore, the polynomial $$x^{r+1}-x$$ is of degree $$r+1, but it has $$p$$ roots in the Galois field $$\operatorname{GF}(p)$$. This is impossible, so $$r=0$$ must be the case.

• Can this be proved without using the Galois field? – farleyknight Oct 30 '18 at 1:44
• Yes, see lulu's comment. Since there exists a primitive root $g$ modulo $p$, $g^k\not\equiv1\pmod{p}$ for any positive integer $k<p-1$. But with $a=g$, we have $g^{r+1}\equiv g\pmod{p}$, or $g^r\equiv 1\pmod{p}$, but $r<p-1$. That is, $r=0$. – user593746 Oct 31 '18 at 7:46
• How about without a Galois field and without a primitive root? My textbook includes neither of these but has pretty much this exact question. – farleyknight Nov 3 '18 at 21:48
• How about induction? Let $f$ be any function of integers. Define $\Delta f(n)=f(n+1)-f(n)$. Then, $\Delta^k f$ denotes the $k$-time iteration of $\Delta$. For example, $$\Delta^2f(n)=\Delta (\Delta f)(n)=\Delta f(n+1)-\Delta f(n)=f(n+2)-2f(n+1)+f(n).$$ – user593746 Nov 4 '18 at 12:31
• Prove that $\Delta^k n^k=k!$ and $\Delta^l n^k=0$ for $l>k$. If $n^{r+1}\equiv n\pmod{p}$ holds for any integer $n$, then $\Delta^{r+1}n^{r+1}\equiv \Delta^{r+1}n\pmod{p}$. If $r>0$, then $\Delta^{r+1}n=0$, but $\Delta^{r+1}n^{r+1}=(r+1)!$. So, we have $$(r+1)!\equiv 0\pmod{p}.$$ This contradicts the assumption that $r<p-1$. This proof is as elementary as I can think of. – user593746 Nov 4 '18 at 12:34

I figured out my own question. Here is is for anyone else that wants to know (maybe my classmates...)

By FML, $a^p=a$ mod $p$.

$a^p$ mod $p=a$ mod $p$

multiplying both sides by $a^{-1}$ we get:

$a^{-1}a^p=a^{-1}a$ $\implies$ $a^{p-1}=1$.

$a^{p-1}=1$ (mod $p$)

Taking each each side to the m$^{th}$ power:

$({a^{p-1}})^m=1^m \implies ({a^{p-1})}^m=1$

Multiplying both sides by $a^{k-1}$

$a^{k-1}({a^{p-1}})^m=1a^{k-1} \implies a^{(k-1)+m(p-1)}=a^{k-1} \implies (k-1)+m(p-1) = k-1$

by the definition $x$ mod $(p-1)$ iff $x=q(p-1)+r$, so

$(k-1)+m(p-1) = k-1 \implies (k-1)$ mod $(p-1)=k-1$

By hypothesis we have $a^k$=a mod p. Like in the beginning,

$a^k$=a mod p $\implies$ $a^{-1}a^k$= $a^{-1}$a mod p $\implies$ $a^{k-1}$ = 1 mod p

Substituting $(k-1)$ mod $(p-1)$ for $k-1$ we get:

$a^{(k-1) \textrm{ mod } (p-1)} = 1$ mod $p = a^0$ mod $p= a^{0\textrm{ mod }(p-1)}$mod $p$

so, $(k-1)$ mod $p = 0$mod $p$

By definition, this means that

$(k-1)=m(p-1)$, i.e. that $p-1$ divides $k-1$. $\square$

• How did you get from $a^{(k - 1) + m(p - 1)} = a^{k - 1}$ to $(k - 1) + m(p - 1) = k - 1$? – farleyknight Oct 29 '18 at 20:33