Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 16 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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