# If $a^\phi = 1$ then the order of $a$ divides $\phi$

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. First we eliminate the need to know Euler's Theorem beforehand by recalling a common pigeonhole proof that $$\rm\,\color{#0a0}a\,$$ has finite order iff $$\rm\color{#0a0}{\,a\ \text{is coprime to }\, m}$$.

$$\rm\color{darkorange}{Lemma}\ \ \ a^k\equiv \color{#c00}1\pmod{\!m}\,$$ for some $$\rm\,k>0\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\bmod m\,$$ finite & pigeonhole there are $$\rm \,j> 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 (recall $$\rm (\color{#0a0}{a,m})=1\Rightarrow \rm\color{c00}a\,$$ is invertible so cancellable). $$\ \bf\small QED$$

The set $$\cal O$$ of integers $$\rm n\! >\!0$$ with $$\rm\,a^{\large n} \equiv 1\,$$ is $$\rm\overset{\textstyle (\color{#0a0}{a,m})=\color{}1^{\phantom{|^.}}\!\!}{\color{darkorange}{nonempty}}$$ & closed under $$\rm\color{#c00}{positive\ subtraction}$$, 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 \big[ a^{\large n}\! \equiv 1\!\iff\! \ell\mid n\big]$$

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.