3
$\begingroup$

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?

$\endgroup$
2
  • 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, 2016 at 0:14
  • $\begingroup$ By the way, 1289671298371298379182 is a semiprime. $\endgroup$ Apr 6, 2016 at 0:16

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Can this be proved without using the Galois field? $\endgroup$ Oct 30, 2018 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, 2018 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$ Nov 3, 2018 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, 2018 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, 2018 at 12:34
2
$\begingroup$

Another proof would be to consider the group $U(p)$ of multiplicative units in $\mathbb Z / p \mathbb Z$. For $p$ prime the order of $U(p)$ is $p-1$. Since $p$ is prime, $U(p)$ is cyclic (see Keith Conrad's exposition) and so it has elements of all orders $d$ dividing $p-1$.

If $a$ is such an element of order $d$ then our hypothesis is that $a^{k-1} \equiv 1 \mod p$, and so $|a|=d$ divides $k-1$. So any divisor of $p-1$ is a divisor of $k-1$, hence $p-1$ divides $k-1$.

This avoids Galois theory, unless of course you used Galois theory to prove that $U(p)$ is cyclic. But that can be avoided because all we really needed was that $U(p)$ has an element of order $q$ for each prime $q$ dividing $p-1$, which is guaranteed by Cauchy's theorem.

$\endgroup$
-1
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ How did you get from $a^{(k - 1) + m(p - 1)} = a^{k - 1}$ to $(k - 1) + m(p - 1) = k - 1$? $\endgroup$ Oct 29, 2018 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.