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

Question

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.

Answer 1

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.

Answer 2

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