I am trying to prove by contrapositive, i.e.

If $m$ is composite, then for all $a \in \mathbb{Z}$, either $a^{m-1} \not \equiv 1 \pmod{m}$ or $\exists k: 0 < k < m-1$ where $a^k \equiv 1 \pmod{m}$.

I can easily show it when $\gcd(a, m)=1$ by Euler's theorem. But I am having trouble for the case when $\gcd(a, m) \ne 1$.

I am aware of another question that asks for the same thing (Show that $m$ is prime if there exists $a\in\Bbb Z$ such that $a^{m-1}\equiv 1\pmod m$) but I am looking for a proof without using groups and rings.


2 Answers 2


Hypothesis $\,\Rightarrow\,a\,$ has order $\,m\!-\!1\,$ thus by Euler $\ m\!-\!1\mid \phi(m),\, $ so $\ m\!-\!1 \le \phi(m),\, $ so $\,m\,$ is prime, by $\ \phi(m) \le m-\color{#c00}{2}\ $ for composite $\,m\,$ (they have at least $\,\color{#c00}2\ $ smaller naturals non-coprime to $m).$

Remark $ $ As for your method note that the case where the gcd $\,(a,n)>1$ cannot occur since $\,a^{\large m-1}\equiv 1\pmod{\!m}$ $\,\Rightarrow\, \underbrace{\color{#0a0}a^{\large m-1}\!+ k\,\color{#0a0}m =\color{#c00} 1}_{\Large d\ \mid\ \color{#0a0}{a,\ m}\,\ \Rightarrow\,\ d\ \mid\ \color{#c00}1}\,\Rightarrow\, (a,m) = 1$

More generally, a zero-divisor can't be a unit in a nontrivial ring.

  • $\begingroup$ See Lucas's converse of little Fermat for a more efficient primality test. $\endgroup$ Jun 26, 2019 at 20:40
  • $\begingroup$ Note that this is a particular case of Lagrange's theorem (group theory), which states that the order of an element in a group always divides the order of the group. Here the group is $G=(\mathbb Z/m\mathbb Z)^*$. OP might want to learn more about this. $\endgroup$
    – YiFan
    Jun 27, 2019 at 0:39
  • $\begingroup$ @YiFan It you read the question you will learn that the OP is aware of such a group-theoretic proof (see their link) but they seek a proof not using groups or rings (many courses in elementary number theory don't assume any knowledge of such) $\endgroup$ Jun 27, 2019 at 1:26

Assume $\gcd(a,m)=x$. Then $a^k=x\cdot$something $\ne1\pmod m$

Edit: $a^k=mx+c,\exists x,c$. But $x|a^k,x|mx$, therefore $x|c.$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .