1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See Lucas's converse of little Fermat for a more efficient primality test. $\endgroup$ – Bill Dubuque Jun 26 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 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$ – Bill Dubuque Jun 27 at 1:26
1
$\begingroup$

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.$

$\endgroup$

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.