# $m$ is prime if some integer has order $m-1$ modulo $m$

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.

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.

• See Lucas's converse of little Fermat for a more efficient primality test. – Bill Dubuque Jun 26 at 20:40
• 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. – YiFan Jun 27 at 0:39
• @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) – Bill Dubuque Jun 27 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.$$