Euler’s Coprimes

Problem 1. Given integers $a, b, k$ , show that $\gcd(a,b) = \gcd(a+kb, b)$ .

(Click for Solution)

Solution. Let $c = \gcd(a,b)$ and $d = \gcd(a+kb, b)$ . Then

$c \mid a\quad \text{and} \quad c \mid b \quad \Rightarrow \quad c \mid (a+kb),$

so that $c \mid d$ . Similarly,

$d \mid (a+kb)\quad \text{and} \quad d \mid b \quad \Rightarrow \quad d \mid ((a+kb) - kb)= a,$

so that $d \mid c$ .

Let $n > 1$ denote any positive integer.

Definition 1. Define

$\Phi(n) := \{ 1 \leq x \leq n : \gcd(x, n) = 1\}$

and Euler’s totient function $\varphi$ by $\varphi(n) := |\Phi(n)|$ .

Problem 2. Show that

$G_n := \{ [x]_n : x \in \Phi(n)\} \subseteq \mathbb Z_n^*$

forms an Abelian group of order $\varphi(n)$ under multiplication.

(Click for Solution)

Solution. To establish closure, we need to show that for $x, y \in \Phi(n)$ , $[xy]_n = [m]_n$ for some $m \in \Phi(n)$ . To that end, use Bézout’s lemma to furnish integers $r_1, s_1, r_2, s_2$ such that

$\begin{aligned} r_1 \cdot x + s_1 \cdot n &= 1,\\ r_2 \cdot y + s_2 \cdot n &= 1. \end{aligned}$

Multiplying both equations together,

$(r_1 r_2) \cdot xy + (r_1 s_2 x + r_2 s_1 y + s_1 s_2 n) \cdot n = 1.$

By Bézout’s lemma again, $\gcd(xy, n) = 1$ .

The identity is clearly $[1]_n$ and the inverse of $[x]_n$ exists from $\gcd(x, n) = 1$ .

Problem 3 (Euler’s Theorem). Show that for any integer $a$ such that $\gcd(a, n) = 1$ ,

$[a]_n^{\varphi(n)} = [1]_n.$

(Click for Solution)

Solution. Assume $1 \leq a \leq n$ for simplicity, so that $a \in \Phi(n)$ . If $a \neq 1$ , then $\langle [a]_n \rangle \leq G_n$ . By Lagrange’s theorem,