$\bmod n\!:\ a^n \equiv 1\!\iff\! $ order of $a$ divides $n,\,$ e.g. when $\,n = \phi(m)$

Question

How can I show that the order of an element modulo $m$ divides $\phi(m)$?

I know that if $a$ and $m$ are relatively prime, then the least positive integer $x$ such that $a^x\equiv1\pmod m$ is its order modulo $m$. I also know that, by Euler's theorem, $a^{\phi(m)}\equiv1\pmod m$. Therefore, it must be the case that $x\leq\phi(m)$

However, all that I am left to do is to show that $kx=\phi(m)$, for some integer $k$. Do you guys have an idea on how to do this? Thanks in advance!

Answer 1

Hint: Let $\phi(m)=xq+r$, where $0\le r<x$. Show that $a^r\equiv 1 \pmod{m}$. This contradicts the definition of $x$, unless $r=0$.

Answer 2

Elaboration yields conceptual insight. We view it as a special case of a fundamental result that characterizes cycles (period) of powers in modular arithmetic. Below the modulus $\rm m$ is fixed and often unnotated. [Note: we can remove the need to know Euler's or Fermat's Theorem by recalling a common pigeonhole proof that $\rm\,\color{#0a0}a\,$ has finite order iff $\rm\color{#0a0}{\,a\ \text{is coprime to }\, m}\, -\:\!$ cf. $\rm\color{darkorange}{Lemma}$ below].

The set $\cal O$ of integers $\,\rm n\! >\!0\,$ with $\rm\,a^{\large n} \equiv 1\,$ is $\smash{\rm\overset{\textstyle (\color{#0a0}{a,m})=\color{}1^{\phantom{|^.}}\!\!}{\color{darkorange}{nonempty}}}$ & closed under $\rm\color{#c00}{subtraction_{>0}},\,$ i.e.

$$\rm \color{#90f}n>\color{#0a0}k\in{\cal O}\,\Rightarrow\ \color{#c00}{n\!-\!k}\in{\cal O}\ \ \ [{\rm by}\ \ 1\equiv \color{#90f}{a^{\large n}} \equiv a^{\large n-k}\, \color{#0a0}{a^{\large k}} \equiv a^{\large\color{#c00}{n-k}}] $$

Thus every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\,\ell\ \! $ := order of $\rm\,a,\,$ by below.

Theorem $\ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > k\, \in {\cal O} \, \Rightarrow\, n\!-\!k\, \in \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\,\ell \in\cal O.$

Proof $\ $ If not there's a least nonmultiple $\rm\,n\in \cal O,\,$ contra $\rm\,n\!-\!\ell \in \cal O\,$ is a nonmultiple of $\rm\,\ell$.

---

Remark $ $ This immediately yields the following very useful

Corollary$\:\!_1$ $\ $ If $\,\color{#c00}{a^{\large \ell}\equiv 1}\,$ then $\ \ell\mid n\,\Rightarrow\, a^{\large n}\!\equiv 1,\, $ and conversely if $\,a\,$ has order $\,\ell$

Proof $\ \ (\Rightarrow)\ \ n =\ell k\,\Rightarrow\, a^{\large n}\! \equiv (\color{#c00}{a^{\large \ell}})^{\large k}\!\equiv \color{#c00}{ 1}^k\equiv 1\, $ by the Congruence Power Rule.
$\,(\Leftarrow)\,\ a^n\equiv 1,\ \ell := {\rm ord}(a)\Rightarrow \ell\mid n\,$ by prior Theorem (cf. line preceding Theorem).

Corollary$\:\!_2$ $\ \ a\,$ has $\color{}{{\rm order}\,\ \ell}$ $\iff \left[\, a^{\large n}\! \equiv 1\!\iff\! \ell\mid n\,\right] $

Proof $\ (\Rightarrow)\,$ By Corollary$\:\!_1$. $\ (\Leftarrow)\ $ By the equivalence the least positive $n$ with $\,a^n\equiv 1$ equals the least positive multiple of $\,\ell,\,$ which is $\,\ell$.

See here for elaboration on the Theorem, including other proofs. For more on the key innate algebraic structure see this post on order ideals / groups and denominator ideals.

---

$\rm\color{darkorange}{Lemma}\ \ \ a^k\equiv \color{#c00}1\pmod{\!m}\,$ for some $\rm\,0<k<m\iff (\color{#0a0}{a,m})=1.\ \ $ Proof:

$\rm(\Rightarrow)\,\ \color{#0a0}a\,a^{k-1}+\color{#0a0}mk = \color{#c00}1\Rightarrow (\color{#0a0}{a,m})=1,\,$ by $\rm\,d\mid\color{#0a0}{a,m}\Rightarrow d\mid\color{#c00}1.\,\ $ $(\Leftarrow)\ $ By $\rm\,|\Bbb Z_m\backslash \:\!0\:\!|=m\!-\!1 <\color{#90f}m\,$ & pigeonhole there are $\rm \,1\le k<j\le \color{#90f}m\,$ with $\rm \,a^j\equiv a^k$ so $\rm\,a^{j-k}\equiv 1\,$ via cancel $\,\rm a^k\,$ (i.e. cancel $\rm\,a\,$ from both sides, repeated $\rm\,k\,$ times, recalling $\rm (\color{#0a0}{a,m})=1\Rightarrow \rm\color{c00}a\,$ is invertible so cancellable). By the inequalities we have $\rm\,j-k\le \color{#90f}m-1 < m.\,$