Exercise 855Number theory › CongruencesL1Added 3 Nov 2026

The order of an element mod $n$

#order#multiplicative group#divisor

Statement

Let $a$ be coprime to $n$ . Define $\operatorname{ord}_n(a)$ as the smallest positive $k$ with $a^k\equiv1\pmod n$ . Show that $\operatorname{ord}_n(a)\mid\varphi(n)$ .

Hint

Use Euler's theorem and division.

Show solutionHide solution

Solution

Euler. $a^{\varphi(n)}\equiv1\pmod n$ .

Division. Write $\varphi(n)=qk+r$ with $k=\operatorname{ord}_n(a)$ and $0\le r<k$ . Then $1\equiv a^{\varphi(n)}=a^{qk+r}\equiv a^r\pmod n$ . By minimality of $k$ , $r=0$ .

Conclusion. $k\mid\varphi(n)$ .

The order of an element mod $n$

Statement

Solution

More problems in Congruences