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

| cite | improve this answer | |

Elaboration yields much conceptual insight by viewing it as a special case of a fundamental result. Note: below the modulus is fixed and not notated (so $\,\rm n\,$ does not denote the modulus).

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

Remark $ $ 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\,$ has $\,\color{}{{\rm order}\,\ \ell}$ $\iff \big[ a^{\large n}\! \equiv 1\!\iff\! \ell\mid n\big] $

Proof $\ (\Rightarrow)\,$ By the Corollary. $\ (\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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.