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

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!

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

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

• See here and here for generalizations of the $\rm\color{darkorange}{Lemma}\ \$ Nov 27, 2022 at 13:54
• If group theory is known then we can use Lagrange's Theorem to prove the corollaries. $\ \$ Jun 12 at 13:09