17
$\begingroup$

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!

2 Answers 2

18

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

11

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 $\,a\,$ has $\,\color{#0a0}{{\rm order}\,\ \ell}\ $ then $\,a^{\large n}\! \equiv 1\iff \ell\mid n$

Proof $\ \ (\Rightarrow)\ $ Follows by the Theorem. $\ \ (\Leftarrow)\ \ n =\ell k\,\Rightarrow\, a^{\large n}\! \equiv (\color{#0a0}{a^{\large \ell}})^{\large k}\!\equiv \color{#0a0}{\bf 1}^k\equiv 1$

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.