definition

Let $$a,b \in \mathbb{Z}$$, we say that $$a$$ divides $$b$$, written $$a \divides b$$, if there's an integer $$n$$ so that

$b = na$

If $$a$$ divides $$b$$ then $$b$$ is divisible by $$a$$ and $$a$$ is a divisor or factor of $$b$$, also $$b$$ is called a multiple of $$a$$.

Additional properties of the relation $$\divides$$:

1. if $$a \divides b$$ and $$b \divides c$$ then $$a \divides c$$
2. if $$a \divides b$$ and $$c \divides d$$ then $$ac \divides bd$$
3. if $$d \divides a$$ and $$d \divides b$$ then $$d \divides a + b$$
4. if $$d \divides a$$ and $$d \divides b$$ then $$d \divides ax + by$$ for any integers $$x,y$$

Proof.

1. if $$b=ma$$ and $$c=nb$$ then $$c=(nm)a$$
2. if $$b=ma$$ and $$d=nc$$ then $$bd=(nm)ac$$
3. if $$a=md$$ and $$b=nd$$ then $$a + b=(m + n)d$$
4. if $$a=md$$, $$b=nd$$ then $$ax=(mx)d$$, $$by=(ny)d$$ therefore $$ax + by = (mx + ny)d$$

## Division algorithm

definition

Let $$a, b \in \mathbb{Z}$$ with $$b > 0$$, then there exists $$q, r \in \mathbb{Z}$$ such that

$a = bq + r, \quad \text{where 0 \leq r \lt b}$

Proof. if $$bq$$ is the largest multiple of $$b$$ that does not exceed $$a$$ then $$r = a - bq$$ is positive and since $$b(q + 1) > a$$ then $$r \lt b$$.

Also, if $$r = 0$$ then $$a = bq$$ which implies that $$q \divides a$$.

## Greatest common divisor

Let $$a, b \in \mathbb{N}$$, the greatest common divisor of $$a$$ and $$b$$, written as $$gcd(a,b)$$ or $$(a,b)$$, is the element $$d$$ in $$\mathbb{N}$$ such that $$d \divides a$$ and $$d \divides b$$ and every common divisor of $$a$$ and $$b$$ also divides $$d$$.

theorem

Let $$a$$ and $$b$$ be two numbers in $$\mathbb{N}$$, the value of $$(a,b)$$ is a linear combination of $$a$$ and $$b$$ i.e. there exists $$s,t$$ in $$\mathbb{Z}$$ such that

$sa + tb = (a, b)$

Proof.

Let $$d$$ be the least positive integer that is a linear combination of $$a$$ and $$b$$

$d = sa + tb$

First lets show that $$d \divides a$$, by the division algorithm we know that

$a = dq + r, \quad \text{where 0 \le r \lt d}$

It follows that

\begin{align*} r &= a - dq \\ &= a - (sa + tb)q \\ &= a - saq - tbq \\ &= (1 - sq)a + (-tq)b \\ \end{align*}

We can see that $$r$$ is a linear combination of $$a$$ and $$b$$. Since $$0 \le r \lt d$$ and considering that we defined $$d$$ as the least positive linear combination of $$a$$ and $$b$$ it follows that $$r = 0$$ (if $$0 \lt r \lt d$$ then $$r$$ would be the least possible linear combination which is a contradiction), therefore $$d \divides a$$.

In a similar fashion $$d \divides b$$, therefore by the divisibility property #4

$d \divides sa + tb$

The next thing to prove is that $$d$$ is the greatest common divisor of $$a$$ and $$b$$. To prove this lets show that if $$d'$$ is any other common divisor of $$a$$ and $$b$$ then $$d' \le d$$.

If $$d' \divides a$$ and $$d' \divides b$$ then by the divisibility property #4 it divides any other linear combination of $$a$$ and $$b$$, since $$d = sa + bt$$ is one linear combination of $$a$$ and $$b$$ it follows that $$d' \divides d$$ so either $$d' \lt d$$ or $$d' = d$$, finally we can conclude that

$d = (a,b)$

### Euclidean Algorithm

A very efficient method to compute the greatest common denominator

theorem

Suppose $$a, b$$ be integers with $$a \ge b \gt 0$$

1. Apply the division algorithm $$a = bq + r, 0 \le r \lt b$$
2. Rename $$b$$ as $$a$$ and $$r$$ as $$b$$ and repeat 1 until $$r = 0$$

The last nonzero remainder is the greatest common divisor of $$a$$ and $$b$$

The euclidean algorithm depends on the following lemma

lemma

Let $$a, b$$ be integers with $$a \ge b \gt 0$$. Let $$r$$ be the remainder of dividing $$a$$ by $$b$$ then

$(a,b) = (b, r)$

Proof. Let $$q$$ be the quotient of dividing $$a$$ by $$b$$ so that $$a = bq + r$$. If $$d = (a,b)$$ then it must divide any other linear combination of $$a$$ and $$b$$ like $$r = a - bq$$, therefore $$d \divides r$$. Finally we can conclude that $$d = (b,r)$$.

Proof of the theorem If we keep on repeating the division algorithm we have:

\begin{align*} a &= bq_1 + r_1, \quad (a,b) = (b, r_1) \\ b &= r_1q_2 + r_2, \quad (b, r_1) = (r_1, r_2) \\ r_1 &= r_2q_3 + r_3, \quad (r_1, r_2) = (r_2, r_3) \\ r_2 &= r_3q_4 + r_4, \quad (r_2, r_3) = (r_3, r_4) \\ & \; \vdots \\ r_{n-3} &= r_{n-2}q_{n-1} + r_{n-1}, \quad (r_{n-3}, r_{n-2}) = (r_{n-2}, r_{n-1}) \\ r_{n-2} &= r_{n-1}q_n + r_n, \quad (r_{n-2}, r_{n-1}) = (r_{n-1}, r_n) \\ r_{n-1} &= r_n q_{n+1}, \quad \quad (r_{n-1}, r_n) = r_n \end{align*}

Therefore

$(a,b) = (b,r_1) = (r_1,r_2) = (r_2, r_3) = (r_3, r_4) = \ldots = (r_{n-3}, r_{n-2}) = (r_{n-2}, r_{n-1}) = (r_{n-1}, r_n) = r_n$

### Extended Euclidean Algorithm

One of the applications of the euclidean algorithm is the calculation of the integers $$x,y$$ satisfying $$d = (a,b) = ax + by$$

First note that if $$b=0$$ then $$(a,b) = (a,0) = a$$, now assume that there are integers $$x'$$ and $$y'$$ so that

$(a,b) = (b,r) = bx' + ry'$

Since

\begin{align*} r &= a - bq \\ &= a - b \left \lfloor \frac{a}{b} \right \rfloor \end{align*}

Then

\begin{align*} (a,b) &= bx' + \Big( a - \left \lfloor \frac{a}{b} \right \rfloor b \Big) y' \\ &= bx' + ay' - \left \lfloor \frac{a}{b} \right \rfloor by' \\ &= a(y') + b \Big(x' - \left \lfloor \frac{a}{b} \right \rfloor y'\Big) \end{align*}

Comparing it to $$(a,b) = ax + by$$ we obtain the required coefficients $$x$$ and $$y$$ based on the following recursive equations

\begin{align*} x &= \begin{cases} 1, & \text{when r = 0} \\ y', & \text{otherwise} \end{cases} \\ y &= \begin{cases} 0, & \text{when r = 0} \\ x' - \left \lfloor \frac{a}{b} \right \rfloor y', & \text{otherwise} \end{cases} \end{align*}

References