Let $a,b\in \mathbb{Z}$. We say that $a$ divides $b$, written $a|b$, if there’s an integer $n$ such 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 $|$:

1. if $a|b$ and $b|c$ then $a|c$.
2. if $a|b$ and $c|d$ then $ac|bd$.
3. if $d|a$ and $d|b$ then $d|a+b$.
4. if $d|a$ and $d|b$ then $d|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$ and $by=(ny)d$; therefore, $ax+by=(mx+ny)d$.

Division algorithm

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\le r<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<b$

Also, if $r=0$, then $a=bq$, which implies that $q|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|a$, and $d|b$, and every common divisor of $a$ and $b$ also divides $d$.

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$

First, let’s show that $d|a$. By the division algorithm, we know that

It follows that

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

In a similar fashion, $d|b$; therefore, by the divisibility property #4

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^{\prime }$ is any other common divisor of $a$ and $b$ then $d^{\prime }\le d$.

If $d^{\prime }|a$ and $d^{\prime }|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^{\prime }|d$ so either $d^{\prime }<d$ or $d^{\prime }=d$, finally we can conclude that

Euclidean Algorithm

A very efficient method to compute the greatest common denominator

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

1. Apply the division algorithm $a=bq+r,0\le r<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

Let $a,b$ be integers with $a\ge b>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|r$. Finally we can conclude that $d=(b,r)$.

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

Therefore:

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^{\prime }$ and $y^{\prime }$ so that

Since

Then

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