22
$\begingroup$

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!

$\endgroup$

2 Answers 2

23
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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.

$\endgroup$

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.