Exercises – KindiakMath

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

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

(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,