GCD & Euclid’s Algorithm

GCD & Euclid’s Algorithm#

Programming Environment#

import numpy as np

Euclid’s Algorithm#

Euclid’s Elements Book VII Props. 1 & 2

\(Theorem\) [Humphreys & Prest 1.1.5 pp. 9] Euclid’s Elements Book VII Proposition 2

Let \(a\) and \(b\) be positive integers. \(a, b \in \mathbb{P}\)
If \(a\) divides \(b\) then \(a\) is the greatest common divisor of \(a\) and \(b\).
Otherwise, applying the division theorem repeatedly define a sequence of positive integers by \(r_1, r_2, \dots, r_n\) by

\[\begin{split} \begin{align*} b &= a q_1 + r_1 && 0 \le r_1 \lt |a| \\ a &= r_1q_2 + r_2 && 0 \le r_2 \lt r_1 \\ \vdots \\ r_{n - 2} &= r_{n - 1}q_n + r_n && 0 \le r_n \lt r_{n - 1} \\ r_{n - 1} &= r_nq_{n + 1} \\ \end{align*} \end{split}\]

Then \(r_n\) is the greatest common divisor of \(a\) and \(b\).

\(Proof\) [Humphreys & Prest pp. 9]

Apply the division theorem to the successive non-zero remainders \(r_1, r_2, \dots, r_n\).
Since \(a, r_1, r_2, \dots, r_n\) is a decreasing sequence of positive integers, it must eventually stop, terminating with an integer \(r_n\) which–because no non-zero remainder \(r_{n + 1}\) is produced–must, therefore, divide \(r_{n - 1}\).
Then apply the gcd lemma back up the sequence of equations so that \(gcd(b, a) = gcd(a, r_1) = \dots = gcd(r_{n - 2}, r_{n - 1}) = gcd(r_{n - 1}, r_n) = r_n\).
\(\therefore r_n = gcd(a, b)\).

\(\blacksquare\)

\(Proof \,\, by \,\, construction\) [Bressoud pp. 7]

Assume that \(a\) and \(b\) are positive.

This process continues until the remainder is \(0\), which must eventually happen since the remainders are always nonnegative and each remainder is strictly smaller than the previous one.

\( \begin{aligned} a &= m_1 \times b + r_1 && 0 \le r_1 \lt |b| && r_1 = 0 \implies b \mid a, gcd(a, b) = b, m = 0, n = 1 \\ b &= m_2 \times r_1 + r_2 && 0 \le r_2 \lt r_1 && r_2 = 0 \implies gcd(a, b) = r_1 \\ r_1 &= m_3 \times r_2 + r_3 && 0 \le r_3 \lt r_2 && r_3 = 0 \implies gcd(a, b) = r_2 \\ \vdots \\ r_{k - 2} &= m_k \times r_{k - 1} + r_k && 0 \lt r_k \lt r_{k - 1} \\ r_{k - 1} &= m_{k + 1} \times r_k + 0 && && gcd(a, b) = r_k \\ \end{aligned} \)

The last non-zero remainder, \(r_k\), is the greatest common divisor of \(a\) and \(b\).

We work back up the list of equalities to show that \(r_k\) is a common divisor of \(a\) and \(b\).

\( \begin{aligned} r_k &\mid r_k \\ r_k &\mid r_{k - 1} && \text{by the last equality} \\ r_k &\mid r_{k - 2} && \text{by the second to last equality} \\ \vdots \\ r_k &\mid r_3 \\ r_k &\mid r_2 \\ r_k &\mid r_1 && \text{by the third equality} \\ r_k &\mid b && \text{by the second equality} \\ r_k &\mid a && \text{by the first equality} \\ \end{aligned} \)

To show that \(r_k\) is the largest common divisor, let \(d\) be any other common divisor.

\( \begin{aligned} d &\mid a \\ d &\mid b \\ d &\mid r_1 && \text{by} \,\, a = m_1 \times b + r_1 \end{aligned} \)

\(Example\) [Humphreys & Prest pp. 10]

Let \(a = 30\) and \(b = 171\).

\[\begin{split} \begin{align*} b &= aq + r && 0 \le r \lt |a| \\ 171 &= 5 \cdot 30 + 21 && 0 \le 21 \lt 30 && gcd(171, 30) = gcd(30, 21) \\ 30 &= 1 \cdot 21 + 9 && 0 \le 9 \lt 21 && gcd(30, 21) = gcd(21, 9) \\ 21 &= 2 \cdot 9 + 3 && 0 \le 3 \lt 9 && gcd(21, 9) = gcd(9, 3) \\ 9 &= 3 \cdot 3 + 0 && 0 \le 0 \lt 3 && gcd(9, 3) = 3 \\ \end{align*} \end{split}\]

\(3 = gcd(9, 3) = gcd(21, 9) = gcd(30, 21) = gcd(171, 30)\)

\[\begin{split} \begin{align*} 3 &= 21 - 2 \cdot 9 && 3 = 21 - 2 \cdot 9 \\ &= 21 - 2 \cdot (30 - 21) && 9 = 30 - 1 \cdot 21 \\ &= 3 \cdot 21 - 2 \cdot 30 \\ &= 3 \cdot (171 - 5 \cdot 30) - 2 \cdot 30 && 21 = 171 - 5 \cdot 30 \\ &= 3 \cdot 171 - 17 \cdot 30 \\ &= 3 \cdot 171 + (-17) \cdot 30 \\ \end{align*} \end{split}\]

\(3 = (-17) \cdot 30 + 3 \cdot 171\)

a, b =  30, 171
x, y = -17,   3
c    = a*x + b*y

assert c == np.gcd(a, b)
print (c)

3

\(Example\) [Humphreys & Prest pp. 14]

Let \(a = -24\) and \(b = -102\).

\[\begin{split} \begin{align*} b &= qa + r && 0 \le r \lt |a| && gcd(b, a) = gcd(a, r) \\ -102 &= 5 \cdot (-24) + 18 && 0 \le 18 \lt 24 && gcd(-102, -24) = gcd(-24, 18) \\ -24 &= -2 \cdot 18 + 12 && 0 \le 12 \lt 18 && gcd(-24, 18) = gcd(18, 12) \\ 18 &= 1 \cdot 12 + 6 && 0 \le 6 \lt 12 && gcd(18, 12) = gcd(12, 6) \\ 12 &= 2 \cdot 6 + 0 && 0 \le 0 \lt 6 && gcd(12, 6) = 6 \\ \end{align*} \end{split}\]

\(6 = gcd(12, 6) = gcd(18, 12) = gcd(-24, 18) = gcd(-102, -24)\)

\[\begin{split} \begin{align*} 6 &= 18 - 1 \cdot 12 && 6 = 18 - 1 \cdot 12 \\ &= 18 - 1 \cdot (-24 - (-2) \cdot 18) && 12 = -24 - (-2) \cdot 18 \\ &= 18 - 1 \cdot (-24 + 2 \cdot 18) \\ &= (-1) \cdot 18 - 1 \cdot (-24) \\ &= (-1) \cdot (-102 - 5 \cdot (-24)) - 1 \cdot (-24) && 18 = -102 - 5 \cdot (-24) \\ &= (-1) \cdot (-102) + 5 \cdot (-24) - 1 \cdot (-24) \\ &= (-1) \cdot (-102) + 4 \cdot (-24) \\ \end{align*} \end{split}\]

\(6 = 4 \cdot (-24) + (-1) \cdot (-102)\)

a, b = -24, -102
x, y =   4,   -1
c    = a*x + b*y

assert c == np.gcd(a, b)
print (c)

6

Find the GCD as a linear combination via matrices#

[Humphreys & Prest pp. 10-11]

Find \(gcd(a, b)\) of \(a\) and \(b\) as a linear combination \(as + bt\).

Set up a partitoned matrix which represents the equations \(x = b\) and \(y = a\).

\[\begin{split} \left( \begin{array}{cc|c} 1 & 0 & b \\ 0 & 1 & a \\ \end{array} \right) \iff \left( \begin{array}{cc|c} 1 & 0 & aq_1 + r_1 \\ 0 & 1 & a \\ \end{array} \right) \end{split}\]

If \(r_1 = 0\) then
\(a = gcd(a, b)\)
\(a = 0 \cdot b + 1 \cdot a\)
and we are done.

Otherwise, subtract \(q_1\) times the bottom row from the top row.
\(b = aq_1 + r_1\) with \(0 \le r_1 \lt |a|\)
\(b = aq_1 + r_1 \iff b - aq_1 = r_1\).

\[\begin{split} \left( \begin{array}{cc|c} 1 & -q_1 & b - aq_1 \\ 0 & 1 & a \\ \end{array} \right) \iff \left( \begin{array}{cc|c} 1 & -q_1 & r_1 \\ 0 & 1 & a \\ \end{array} \right) \end{split}\]

If \(r_2 = 0\) then
\(r_1 = gcd(r_1, a) = gcd(a, b)\)
\(r_1 = 1 \cdot b + (-q_1) \cdot a\)
and we are done.

Otherwise, subtract \(q_2\) times the top row from the bottom row.
\(a = r_1q_2 + r_2\) with \(0 \le r_2 \lt r_1\)
\(a = r_1q_2 + r_2 \iff a - r_1q_2 = r_2\).

\[\begin{split} \left( \begin{array}{cc|c} 1 & -q_1 & r_1 \\ -q_2 & 1 + q_1q_2 & a - r_1q_2 \\ \end{array} \right) \iff \left( \begin{array}{cc|c} 1 & -q_1 & r_1 \\ -q_2 & 1 + q_1q_2 & r_2 \\ \end{array} \right) \end{split}\]

If \(r_3 = 0\) then
\(r_2 = gcd(r_2, r_1) = gcd(r_1, a) = gcd(a, b)\)
\(r_2 = (-q_2) \cdot b + (1 + q_1q_2) \cdot a\)
and we are done.

Otherwise, subtract \(q_3\) times the bottom row from the top row.
\(r_1 = r_2q_3 + r_3\) with \(0 \le r_3 \lt r_2\)
\(r_1 = r_2q_3 + r_3 \iff r_1 - r_2q_3 = r_3\).

\[\begin{split} \left( \begin{array}{cc|c} 1 + q_2q_3 & -q_1 - q_3 - q_1q_2q_3 & r_1 - r_2q_3 \\ -q_2 & 1 + q_1q_2 & r_2 \\ \end{array} \right) \iff \left( \begin{array}{cc|c} 1 + q_2q_3 & -q_1 - q_3 - q_1q_2q_3 & r_3 \\ -q_2 & 1 + q_1q_2 & r_2 \\ \end{array} \right) \end{split}\]

And so on. If at some stage one of the rows is

\[ \begin{array}{cc|c} n_i & m_i & r_i & (*) \end{array} \]

representing the equation

\[ \begin{align*} bn_i + am_i = r_i \end{align*} \]

and if the other row reads

\[ \begin{array}{cc|c} n_{i + 1} & m_{i + 1} & r_{i + 1} & (**) \end{array} \]

then we set

\[ \begin{align*} r_i &= r_{i + 1}q_{i + 2} + r_{i + 2} && 0 \le r_{i + 2} \lt r_{i + 1} \end{align*} \]

and we subtract \(q_{i + 2}\) times the second of these rows from the first and replace \((*)\) with the result.

Note that these operations reduce the size of the non-negative numbers in the right-hand column and so eventually the process will stop. When it stops, we will have the \(gcd\).
If the row containing the \(gcd\) reads

\[ \begin{array}{cc|c} n & m & d \end{array} \]

then we have the expression

\[ \begin{align*} bn + am = d \end{align*} \]

of \(d\) as the integral linear combination of \(a\) and \(b\).

\(Example\) [Humphreys & Prest pp. 11]

\( \newcommand{\bmat}{\left(\begin{array}{cc|c}} \newcommand{\emat}{\end{array}\right)} \begin{aligned} & \bmat 1 & 0 & 171 \\ 0 & 1 & 30 \\ \emat && \begin{aligned} 1 \cdot 171 + 0 \cdot 30 &= 171 \\ 0 \cdot 171 + 1 \cdot 30 &= 30 \\ \end{aligned} \\ \to & \bmat 1 & -5 & 21 \\ 0 & 1 & 30 \\ \emat \\ \to & \bmat 1 & -5 & 21 \\ -1 & 6 & 9 \\ \emat \\ \to & \bmat 3 & -17 & 3 \\ -1 & 6 & 9 \\ \emat \\ \to & \bmat 3 & -17 & 3 \\ -10 & 57 & 0 \\ \emat && \begin{aligned} 3 \cdot 171 - 17 \cdot 30 &= 3 = gcd(171, 30) \\ (-10) \cdot 171 + 57 \cdot 30 &= 0 \\ \end{aligned} \end{aligned} \)

Generalization of GCD#

\(Definition\) [Humphreys & Prest pp. 12]

Let \(a_1, \dots, a_n\) be positive integers.
Then \(gcd(a_1, \dots, a_n)\) is the positive integer \(m\) with the property that \(m \mid a_i\) for each \(i\) and, whenever \(c\) is an integer with \(c \mid a_i\) for each \(i\), we have \(c \mid m\).

\(Proof \,\, idea\) [Humphreys & Prest pp. 12]

\(gcd(a_1, \dots, a_n) = gcd(gcd(a_1, \dots, a_{n - 1}), a_n)\)
In other words, we can compute the \(gcd\) of \(n\) numbers \(a_1, \dots, a_n\) by computing the \(gcd\) of the first \(n - 1\) of them and then computing the \(gcd\) of that and the last number \(a_n\).
If we can compute the \(gcd\) of two numbers, then we can compute the \(gcd\) of \(n\) numbers.

\(Claim\) [Humphreys & Prest pp. 12]

For all \(n\) and integers \(a_1, \dots, a_n\) it is the case that \(gcd(a_1, \dots, a_n) = gcd(gcd(a_1, \dots, a_{n - 1}), a_n)\).

\(Proof\)

TODO

\(\blacksquare\)

\(Example\) [Humphreys & Prest pp. 12]

\[\begin{split} \begin{align*} & gcd(24, 60, 30, 8) \\ = & gcd(gcd(24, 60, 30), 8) \\ = & gcd(gcd(gcd(24, 60), 30), 8) \\ = & gcd(gcd(12, 30), 8) \\ = & gcd(6, 8) \\ = & 2 \\ \end{align*} \end{split}\]

LCM#

\(Definition\) [Humphreys & Prest pp. 14]

The least common multiple \(lcm(a, b)\) of integers \(a\) and \(b\) is the positive integer \(m\) s.t. both

  1. \(a\) and \(b\) divide \(m\) (so \(m\) is a common multiple of \(a\) and \(b\)), and s.t.

  2. \(m\) divides every common multiple of \(a\) and \(b\).

\(Claim\) [Humphreys & Prest pp. 14]

\(m = lcm(a, b)\) exists and is unique.

\[ \color{red} \forall a, b \in \mathbb{Z} \,\, \exists m \in \mathbb{P} \,\, [ \,\, m = lcm(a, b) \iff (((a \mid m) \land (b \mid m)) \land (m \mid CommonMultiple(a, b))) \,\, ] \]

\(Proof\)

TODO

\(\blacksquare\)

\(Definition\) [Humphreys & Prest pp. 14]

Let \(a_1, \dots, a_n\) be non-zero integers.
\(lcm(a_1, \dots, a_n)\) is the unique positive integer \(m\) which satisfies \(a_i \mid m\) for all \(i\) and, whenever an integer \(c\) satisfies \(a_i \mid c\) for all \(i\), we have \(m \mid c\).

\(Example\) [Humphreys & Prest pp. 14]

\(lcm(6, 15, 4) = lcm(lcm(6, 15), 4) = lcm(30, 4) = 60\).