Exercise 3.2.22 (Euler(s Theorem)

Question

Use Lagrange's Theorem in the multiplicative group $(\mathbb{Z}/ n \mathbb{Z})^	imes$ to prove {\bf Euler's Theorem}: $a^{\varphi(n)} \equiv 1 \mod n$ for every integer $a$ relatively prime to $n$, where $\varphi$ denotes Euler's $\varphi$-function.

Richard Ganaye · Accepted Answer

\begin{proof} 
If the integer $a$ relatively prime to $n$, then $\overline{a} \in (\mathbb{Z}/ n \mathbb{Z})^	imes$. By Lagrange's Theorem, the order of $\overline{a}$ divides $|(\mathbb{Z}/ n \mathbb{Z})^	imes| =\varphi(n)$, hence
$$\overline{a}^{\varphi(n)} = \overline{1}.$$
This shows that
$$a^{\varphi(n)} \equiv 1 \pmod n \qquad (	ext{if } a \wedge n = 1).$$

\end{proof}

Exercise 3.2.22 (Euler(s Theorem)

Answers

Comments

Exercise 3.2.22 (Euler(s Theorem)

Answers

Comments

Add answer