# Order of an Element Modulo $n$ Divides $\phi(n)$

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

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

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

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

Elaboration yields much conceptual insight by viewing it as a special case of a fundamental result.

The set $$\,\cal O\,$$ of integers $$\rm\:n >0\:$$ such that $$\rm\:a^{\large n} \equiv 1\:$$ is closed under positive subtraction, i.e.

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

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

Theorem $$\ \$$ If a nonempty set of positive integers $$\rm\,\cal O\,$$ satisfies $$\rm\ n > m\, \in {\cal O} \, \Rightarrow\, n\!-\!m\, \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$$.

This immediately yields the following very useful

Corollary $$\$$ If $$\,\color{#0a0}{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{#0a0}{a^{\large \ell}})^{\large k}\!\equiv \color{#0a0}{\bf 1}^k\equiv 1.\$$ $$\,(\Leftarrow)\$$ Follows by the Theorem.

Corollary $$\$$ $$\,a^{\large n}\! \equiv 1\iff \ell\mid n\,\$$ when $$\ \,a\,$$ has $$\,\color{}{{\rm order}\,\ \ell}$$

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