Let $m$ be the smallest positive integer such that $a^m \equiv 1 \pmod n$

Question

Let $n \in \mathbb{N}$, $a$ an integer and $\gcd(a, n) = 1$. Further, let $m$ be the smallest positive integer such that $$a^m \equiv 1 \pmod n.$$

Prove that $m$ divides $\phi(n)$.

Can anyone help me with this proof?

Answer 1

Note that from Euler's theorem $$a^{\phi(n)} \equiv 1 \pmod{n}$$

Now use the division remainder theorem :

$$\phi(n)=mc+r$$ for some $r$ with $0 \leq r \leq m-1$ .

Using this in the above :

$$1 \equiv a^{\phi(n)} \equiv a^{mc+r} \equiv a^r \cdot (a^m)^c \equiv a^r \cdot 1^c \equiv a^r \pmod{n}$$

This means that $a^r \equiv 1 \pmod{n}$ .

But because $r < m-1$ and $m$ is the minimal such number it follows that $r=0$ so $\phi(n)=mc$ .

This means that $m \mid \phi(n)$ .

Answer 2

This can be done by Lagrange's theorem : If $G$ is a group, and $a$ an element in $G$, the order of $a$ divides the order of $G$. Now, choose $G=(\mathbb{Z}/n\mathbb{Z})^{\star}$. since $(a,n)=1$, the class of $a$ belongs to $G$, which has order $\phi(n)$.