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

-

Hint $\$ With only slightly more effort one can view this as a special case of a basic result.

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

$$\rm \color{#0A0}n>\color{#C00}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#0A0}{a^n} \equiv a^{n-m}\, \color{#C00}{a^m} \equiv a^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$

So, by 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$.

Remark $\$ See here for elaboration on the above proof. For more on the key innate structure see this post on order ideals and denominator ideals.

-