1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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