TSSFL TECHNOLOGY STACK

We explore a couple of examples that involve relatively prime integers and greatest common divisor (gcd).

We will make use of the following fact:

Let $a$ and $b$ be any two integers, not both zero. Then an integer $d\ge 1$ is called a greatest common divisor of $a$ and $b$ if the following properties hold:

(i) $d/a$ and $d/b$ (ii) For any integer $k$, if $k/a$ and $k/b$, then $k/d$


Problem 1

Prove that if $(a, \ b) = d$, and $a = qb + r$, then $d/r$.

Proof

If $d = (a, \ b)$, then $d/a$ and $d/b$.

So $a = md$, $b = nd$ for some $m, \ n \in \mathbb{Z}$.

We thus have $r = a - qb = md - qnd = (m-qn)d$, and hence $d/r$


Problem 2

Let $a \ \text{and} \ b$ are relatively prime integers and suppose that $a$ divides $bc$, where $c \in \mathbb{Z}$. Prove that $a$ divides $c$.

Proof

Since $a$ and $b$ are relatively prime, $\implies$ $(a,b) = 1$ $\implies$ $ma + nb = 1$ for some $m, n \in \mathbb{Z}$.
$a/bc$ $\implies$ $bc = ka$, $k \in \mathbb{Z}$.

We need to show that $a/c$ i.e., $c = ra$, $r \in \mathbb{Z}$.

Thus, $mac + nbc = c$

$mac + nka = c$

$(mc + nk)a = c$, which $\implies$ $a/c$


Problem 3

Let $a$, $b$ and $c$ be integers. Suppose that $a$ and $b$ relatively prime and that $a$ and $c$ are also relatively prime. Prove that $a$ and $bc$ relatively prime.

Proof

Since $a$ and $b$ are relatively prime, $ma + nb = 1$, $m, n \in \mathbb{Z}$

Since $a$ and $c$ are relatively prime, $ka + sc = 1$, $k, s \in \mathbb{Z}$

So, $mac + nbc = c$

$smac + snbc = sc = 1 - ka$

$smac + ka + snbc = 1$

$(smc + k)a + (sn)bc = 1$. Thus $(a, bc) = 1$

Problem 4

Show that $(ma, mb) = m(a,b), \ m>0, \ m, \ n \in \mathbb{Z}.$

Solution

For natural numbers $a, \ b, \ d, \ m \ne 0$, suppose $(a,b) = d$ which implies $d/a$ and $d/b$ and thus $d = na + kb$ for some integers $n, \ k.$

$\implies$ $dm/ma,$ and $dm/mb$ and $dm = nma + kmb = (ma, mb)$ for some integers $n, \ k.$

Since $d = (a,b)$,

Then $dm = m(a,b) = (ma, mb)$