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