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?

  • 3
    $\begingroup$ 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 $\endgroup$ – lulu Apr 6 '16 at 0:14
  • $\begingroup$ By the way, 1289671298371298379182 is a semiprime. $\endgroup$ – астон вілла олоф мэллбэрг 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<p-1$. 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<p$, but it has $p$ roots in the Galois field $\operatorname{GF}(p)$. This is impossible, so $r=0$ must be the case.

  • $\begingroup$ Can this be proved without using the Galois field? $\endgroup$ – farleyknight Oct 30 '18 at 1:44
  • 1
    $\begingroup$ 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$. $\endgroup$ – user593746 Oct 31 '18 at 7:46
  • 1
    $\begingroup$ How about without a Galois field and without a primitive root? My textbook includes neither of these but has pretty much this exact question. $\endgroup$ – farleyknight Nov 3 '18 at 21:48
  • 2
    $\begingroup$ 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).$$ $\endgroup$ – user593746 Nov 4 '18 at 12:31
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.