Greatest common divisor by group

 

Lemma 1

Fix $r, s \in \mathbb{N}$. Let $H = \left\{mr + ns \; | \; m, n \in \mathbb{Z} \right\}$. Then

$H$ is subgroup of $\mathbb{Z}$

 

  Show 1 : $H$ is a subset of $\mathbb{Z}$

  It is clear.

 

  end

 

 

  Show 2 : $H$ is closed

  $\forall x, y \in H$, there exists $m_{1}, m_{2}, n_{1}, n_{2} \in \mathbb{Z}$  s.t.

  $x = m_{1}r + n_{1}s$,     $y = m_{2}r + n_{2}s$

  $\therefore$  $x + y = (m_{1} + m_{2})r + (n_{1} + n_{2})s \in H$

 

  end

 

 

  Show 3 : $H$ is a group

  $(\mathrm{i})$ associativity

  It is clear.

 

  $(\mathrm{ii})$ identity

  $0 = 0 \cdot r + 0 \cdot s \in H$

 

  $(\mathrm{iii})$ inverse

  $\forall x \in H$, there exists $m, n \in \mathbb{Z}$  s.t.

  $x = mr + ns$

  $\therefore$  $(mr + ns) + ((-m)r + (-n)s) = ((-m)r + (-n)s) + (mr + ns) = 0$

  $\therefore$  $x^{-1} = (-m)r + (-n)s \in H$

 

  end

 

 

 

Cor 1

Fix $r, s \in \mathbb{N}$. Let $H = \left\{mr + ns \; | \; m, n \in \mathbb{Z} \right\}$. Then

$H = \left<d \right>$     for some $d \in \mathbb{N}$

 

 

 

Def 1

Fix $r, s \in \mathbb{N}$. Let $H = \left\{mr + ns \; | \; m, n \in \mathbb{Z} \right\}$

So $H = \left<d \right>$  for some $d \in \mathbb{N}$

1.  $d$ is the greatest common divisor of $r$ and $s$

(We write $d = \mathrm{gcd}(r, s)$)

2.  $r$ and $s$ are relatively prime ( or coprime ) if $\mathrm{gcd}(r, s) = 1$

 

 

 

Remark

Since $d \in H$, there exists $m_{0}, n_{0} \in \mathbb{Z}$  s.t.

$d = m_{0}r + n_{0}s$

 

 

 

Thm 1

Fix $r, s \in \mathbb{N}$. Let $d = \mathrm{gcd}(r, s)$

1.  $d \mid r$,  $d \mid s$

2.  $d' \mid r$  and  $d' \mid s$  $\Rightarrow$  $d' \mid d$

3.  $r \mid sm$  and  $\mathrm{gcd}(r, s) = 1$  $\Rightarrow$  $r \mid m$

 

pf)

  Let $H = \left\{mr + ns \; | \; m, n \in \mathbb{Z} \right\}$

  Since $H = \left<d \right>$,

  $d \mid a$     for all $a \in H$

 

  Therefore  

  $r = 1 \cdot r + 0 \cdot s$  $\Rightarrow$  $r \in H$  $\Rightarrow$  $d \mid r$

  $s = 0 \cdot r + 1 \cdot s$  $\Rightarrow$  $s \in H$  $\Rightarrow$  $d \mid s$

 

  Since $d \in H$, there exists $m_{0}, n_{0} \in \mathbb{Z}$  s.t.

  $d = m_{0}r + n_{0}s$

 

  Since $d' \mid r$  and  $d' \mid s$,

  $d' \mid m_{0}r$  and  $d' \mid n_{0}s$

  $\therefore$  $d' \mid m_{0}r + n_{0}s = d$

 

  Since $\mathrm{gcd}(r, s) = 1$, there exists $m_{0}, n_{0} \in \mathbb{Z}$  s.t.

  $m_{0}r + n_{0}s = 1$

  $\therefore$  $mm_{0}r + mn_{0}s = m$

 

  Since $r \mid mm_{0}r$  and  $r \mid mn_{0}s$,

  $r \mid m$