GCD & Euclid’s Algorithm

GCD & Euclid’s Algorithm#

Programming Environment#

import numpy as np

Division Theorem#

The division theorem expresses a key property of integer division (that is, when an integer is divided by a non-zero integer).

\(Theorem\) [Humphreys & Prest 1.1.1 pp. 3-4] [Bressoud pp. 7]

Given integers \(a\) and \(b\) with \(a \ne 0\) there exist unique integers \(q\) and \(r\) such that
\(b = q \times a + r\) where \(0 \le r \lt |a|\)
where \(q\) is the quotient of \(b\) by \(a\) and \(r\) is the remainder.

\[ \color{red} \forall a, b \in \mathbb{Z} \,\, ((b \ne 0) \implies \exists q, r \in \mathbb{Z} \,\, ((abs(b) \gt r \ge 0) \land (a = qb + r))) \]

It is proved elsewhere that if \(a \mid b\), then \(r = 0\).
If \(a \nmid b\), then \(r\) satisfies the stronger inequalities \(0 \lt r \lt |a|\).
In other words, remainders are always non-negative.

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

Let \(a = 3\) and \(b = 7\).
Then there are integers \(q\) and \(r\) st \(7 = 3q + r\) with \(0 \le r \lt |3|\).
\(7 = 2 \cdot 3 + 1\) with \(0 \le 1 \lt |3|\).

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

Let \(a = 4\) and \(b = 12\).
Then there are integers \(q\) and \(r\) st \(12 = 4q + r\) with \(0 \le r \lt |4|\).
\(12 = 3 \cdot 4 + 0\) with \(0 \le 0 \lt |4|\).

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

Let \(a = 4\) and \(b = -9\).
Then there are integers \(q\) and \(r\) st \(-9 = 4q + r\) with \(0 \le r \lt |4|\).
\(-9 = (-3) \cdot 4 + 3\) with \(0 \le 3 \lt |4|\).
Note that \(q = -2\) and \(r = -1\) do not satisfy \(0 \le r \lt |4|\).
\(-9 = (-2) \cdot 4 + (-1)\) but not with \(0 \le -1 \lt |4|\).

\(Proof \,\, by \,\, contradiction\)

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

If \(b \gt a\), then just take \(q = 0, r = a\).

\[ a = 0 \times b + a \]

Therefore, let \(b \le a\).

Consider the set of non-negative differences between \(b\) and integer multiples of \(a\).

\[ D = \{ a - bk : a - bk \ge 0 \land k \in \mathbb{N} \} \]

\(D\) is non-empty since it contains \(a = a - b \cdot 0\) and \(a \ge b \gt 0\).

By the well-ordering principle, \(D\) contains a least element: \(r = a - bq\), say.

\(Contradictory \,\, step\)

If it were the case that \(r\) was not strictly less than \(b\), then we would have \(r - b \ge 0\)

\[ r \not\lt b \implies r - b \ge 0 \]

and, therefore, \(r - b = (a - bq) - b = a - b(q + 1)\).

\[\begin{split} \begin{align*} r &= a - bq \\ r - b &= a - b(q + 1) \\ \implies r - b &\lt r && Contradiction! \\ \end{align*} \end{split}\]

Then \(r - b\) would be a member of \(D\) strictly less than \(r\), contradicting the minimality of \(r\).

Therefore, \(r\) does satisfy \(0 \le r \lt b\).

\(\blacksquare\)

GCD#

\(Theorem\) [Humphreys & Prest 1.1.2 pp. 6]

Let \(a\) and \(b\) be positive integers. \(a, b \in \mathbb{P}\)
There is a positive integer \(d\) such that

(i) \(d\) divides \(a\) and \(d\) divides \(b\), and
(ii) if \(c\) is a positive integer which divides both \(a\) and \(b\) then \(c\) divides \(d\) (i.e., any common divisor of \(a\) and \(b\) divides \(d\)).

\[ \forall a, b \in \mathbb{P} \,\, [ \,\, \exists d \in \mathbb{P} \,\, ((d \mid a \land d \mid b) \land (\forall c \in \mathbb{P} ((c \mid a \land c \mid b) \implies c \mid d))) \,\, ] \]

\(Proof \,\, by \,\, contradiction\) [Humphreys & Prest pp. 6]

Let \(D\) be the set of all positive integers of the form \(as + bt\) where \(s\) and \(t\) vary over the set of all integers.

\[ D = \{ as + bt : s, t \in \mathbb{Z}, as + bt \gt 0 \} \]

\(D\) is non-empty since \(a = a \cdot 1 + b \cdot 0\) is in \(D\).
\(D\) has a least element \(d\) by the well-ordering principle.
Since \(d\) is in \(D\), there are integers \(s\) and \(t\) such that \(d = as + bt\).
We must show that (ii) any common divisor \(c\) of \(a\) and \(b\) is a divisor of \(d\).

Let \(c \mid a\) and \(c \mid b\).
Then there are integers \(g\) and \(h\) such that \(a = cg\) and \(b = ch\).
\(as + bt = (cg)s + (ch)t = c(gs + ht) \implies c \mid c(gs + ht) \implies c \mid as + bt \implies c \mid d\)
\(\therefore c \mid d\)

We must show that (i) \(d \mid a\) and \(d \mid b\).
Showing that \(d \mid a\) is sufficient because \(a\) and \(b\) are interchangeable throughout the proof and so, by symmetry, \(d \mid b\).

We may write \(a = dq + r \,\, , \,\, 0 \le r \lt d\) by the division theorem.
To show that \(d \mid a\) is to show that \(r = 0\).
\(a = dq + r \implies \textcolor{green}{r} = a - dq = a - (as + bt)q = \textcolor{green}{a(1 - sq) + b(-tq)}\)
If \(r\) were positive then it would meet the criteria of \(D\) and so would belong to \(D\).
But \(d\) was chosen to be minimal in \(D\) and \(r\) is strictly less than \(d\). \(Contradiction!\)
\(\therefore (r = 0) \land (d \mid a) \land (d \mid b)\)

\(\blacksquare\)

\(Definition\) [Humphreys & Prest pp. 7] [Bressoud pp. 6]

Let \(a\) and \(b\) be integers.
The integer \(d\) satisfying conditions (i) and (ii) of theorem 1.1.2 is called the greatest common divisor of \(a\) and \(b\) and is denoted \(gcd(a, b)\).
In other words, the greatest common divisor of \(a\) and \(b\) is the largest positive integer which divides both \(a\) and \(b\).

Note that \(gcd(a, b) = gcd(b, a)\).
Note that if \(a \mid b\) then \(a = gcd(a, b)\).

Bézout’s Identity#

\(Corollary\) [Humphreys & Prest 1.1.3 pp. 7-8]

Let \(a\) and \(b\) be positive integers.
The greatest common divisor \(d\) of \(a\) and \(b\) is the smallest positive integral linear combination of \(a\) and \(b\).
That is, \(d = as + bt\) for some integers \(s\) and \(t\).

\(Lemma\) [Bressoud 1.5 pp. 6]

Let \(a\) and \(b\) be integers and let \(g = gcd(a, b)\).
Then there are integers \(m\) and \(n\) such that \(g = ma + nb\).

\(Proof\) [Bressoud pp. 6]

Let \(p\) be a prime and let \(p \mid ab\).
If \(p \mid a\) then we are done.
If \(p \nmid a\) then \(gcd(p, a) = 1\) because \(1\) is the only other positive integer that divides \(p\).

Then there are integers \(m\) and \(n\) s.t. \(gcd(p, a) = 1 = mp + na \iff b = mpb + nab\).
Show that \(p \mid mpb\).

\(p \mid p(mb) = mpb\) since \(p\) divides integer multiples of itself.

Show that \(p \mid nab\).

\(p \mid ab\) and so it follows that \(p \mid ab(n)\) since \(p\) divides integer multiples of itself.

\(\therefore p \mid b = mpb + nab\).

Therefore, if \(p \nmid a\) then \(p \mid b\).

\(\blacksquare\)

\(Example\) [Bressoud pp. 6]

Let \(a = 21\) and \(b = 6\) so that \(g = 3 = gcd(21, 6)\).
Then there are integers \(1\) and \(-3\) st \(3 = 1 \cdot 21 + (-3) \cdot 6\).
There are also integers \(-1\) and \(4\) st \(3 = (-1) \cdot 21 + 4 \cdot 6\).

Computing GCD#

\(Lemma\) [Humphreys & Prest 1.1.4 pp. 8] Euclid’s Elements Book VII Proposition 1

Let \(a\) and \(b\) be natural numbers and let \(a\) be non-zero.
Let \(b = aq + r\) where \(q\) and \(r\) are positive integers.
Then \(gcd(a, b) = gcd(a, r)\).

\[ \color{red} \forall a, b \in \mathbb{N} \,\, [ \,\, ((a \ne 0) \land (\exists q, r \in \mathbb{P} \,\, (b = aq + r))) \implies gcd(a, b) = gcd(a, r) \,\, ] \]

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

Let \(d = gcd(a, b)\).
\(b = aq + r \iff b - aq = r\)

By definition, \(d \mid a\) and \(d \mid b\).
Then \(d \mid b - aq \iff d \mid r\) and so \(d\) is a common divisor of \(a\) and \(r\).
\(\therefore d \mid gcd(a, r)\) since a common divisor of two integers also divides their \(gcd\).

By definition, \(gcd(a, r) \mid a\) and \(gcd(a, r) \mid r\).
\(gcd(a, r) \mid aq + r \iff gcd(a, r) \mid b\) and so \(gcd(a, r)\) is a common divisor of \(a\) and \(b\).
\(\therefore gcd(a, r) \mid d\) since a common divisor of two integers also divides their \(gcd\).

\(\therefore d = gcd(a, r) = gcd(a, b)\) since \(d \mid gcd(a, r)\) and \(gcd(a, r) \mid d\).

\(\blacksquare\)

\(Example\) [Humphreys & Prest pp. 8-9]

Let \(a = 30\) and \(b = 171\).
Then we can write \(171 = 30q + r\) with \(q = 5\) and \(r = 21\) (or \(q = 3\) and \(r = 81\)).
Let \(d = gcd(30, 171)\).
\(171 = 30 \cdot 5 + 21 \iff 171 - 30 \cdot 5 = 21\)

By definition, \(d \mid 30\) and \(d \mid 171\).
Then \(d \mid 171 - 30 \cdot 5 \iff d \mid 21\).
\(\therefore d \mid gcd(30, 21)\).

By definition, \(gcd(30, 21) \mid 30\) and \(gcd(30, 21) \mid 21\).
\(gcd(30, 21) \mid 30 \cdot 5 + 21 \iff gcd(30, 21) \mid 171\).
\(gcd(30, 21) \mid d\).

\(\therefore d = gcd(30, 21) = gcd(30, 171)\).

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)

\(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)

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

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

\(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\).

GCD & Euclid’s Algorithm

Contents

GCD & Euclid’s Algorithm#

Programming Environment#

Division Theorem#

GCD#

Bézout’s Identity#

Computing GCD#

Euclid’s Algorithm#

Find the GCD as a linear combination via matrices#

Generalization of GCD#

LCM#

Extended Euclidean Algorithm#