GCDs and the Euclidean Algorithm

GCDs#

Note

Common Divisor
A common divisor of two integers $a$ and $b$ is any integer $d$ such that both $d \mid a$ and $d \mid b$ .

Example. Which of $1$ , $-6$ and $9$ are common divisors of $12$ and $18$ ?
Since $1 \mid 12$ and $1 \mid 18$ , $1$ is a common divisor; since $-6 \mid 12$ and $-6 \mid 18$ , $-6$ is also a common divisor; but $9 \nmid 12$ , so $9$ is not.

Note

GCD
A greatest common divisor (GCD) of two integers $a$ and $b$ is any integer $d$ such that

d \mid a \text{ and } d \mid b

and

\text{for all } c \in \mathbb{Z}, \text{if } c \mid a \text{ and } c \mid b, \text{ then } c \mid d.

Here, both 6 and -6 are GCDs of 12 and 18.

Note

Standard GCD
The standard greatest common divisor of two integers $a$ and $b$ (not both 0), written as $\gcd{(a,b)}$ is the integer $d$ such that

d \mid a \text{ and } d \mid b

and

\text{for all } c \in \mathbb{Z}, \text{if } c \mid a \text{ and } c \mid b, \text{ then } c \leq d.

Here, $\gcd{(12,18)} = 6.$

Note

Coprime
Two integers $a$ and $b$ are coprime if they have no common divisors other than $\pm 1$ . In other words, $\gcd{(a,b)} = 1$ .

Example. Which of the following pairs are coprime?
$2$ and $3$ are coprime; $9$ and $-10$ are coprime; $12$ and $18$ are not coprime, since $6$ divides both; $0$ and $1$ are coprime, since the only divisors of $1$ are $\pm 1$ .

Note

Lemma 1
For any integer $a$ , $\gcd{(a,1)} = 1$ .

Note

Lemma 2
For any integer $a$ , $\gcd{(a,0)} = |a|$ .
Suppose $d$ is the greatest divisor of $a$ and 0, therefore $d \mid a$ and $d \mid 0$ ; $d \geq 0$ .
Since we are looking at the greatest divisor, $d=a$ is the strongest candidate that satisfies $d \mid a$ . However, $d \geq 0$ , so instead we can assume that $d = |a|$ . Since every integer divides 0, we know that $|a| \mid 0$ , therefore we know that $\gcd{(a,0)}=|a|$ .

Associativity of gcd: gcd(a, gcd(b, c)) equals gcd(gcd(a, b), c), with divisibility arrows outlining the proof
GCD scaling property: gcd(ac, bc) equals the absolute value of c times gcd(a, b)
Euclid's lemma: if a divides bc and gcd(a, b) equals 1, then a divides c
GCD remainder property: if a equals qb plus c, then gcd(a, b) equals gcd(b, c)

Properties of the Standard GCD#

Lemmas 1 and 2 are actually just the first two of a family of useful properties of the standard GCD. Suppose $a$ , $b$ , $c$ and $q$ are integers; then the following all hold.

Note

Lemma 3
For any integers $a$ , $b$ and $c$ ,

\gcd{(a, \gcd{(b,c)})} = \gcd{(\gcd{(a,b)}, c)}.

Basically, $\gcd$ is associative; if you need the GCD of three (or more) numbers, you can pair them up in whatever order you like and the answer does not change. The proof is a Topic 1 problem (Q12), so I'm not gonna write it here.

Example. Find the GCD of $12$ , $18$ and $30$ .
Pairing from the right,

\begin{align*} \gcd{(12, \gcd{(18,30)})} &= \gcd{(12, 6)} \\ &= 6. \end{align*}

Pairing from the left,

\begin{align*} \gcd{(\gcd{(12,18)}, 30)} &= \gcd{(6, 30)} \\ &= 6. \end{align*}

Both orders agree, so the GCD of all three numbers is $6$ .

Note

Lemma 4
For any integers $a$ , $b$ and $c$ ,

\gcd{(ac, bc)} = |c| \gcd{(a,b)}.

Basically, a shared factor can be pulled straight out the front of a $\gcd$ ; just remember the absolute value, since the standard GCD is never negative.

Example. Find $\gcd{(24, 60)}$ .
Notice that $24$ and $60$ share the factor $12$ , so

\begin{align*} \gcd{(24,60)} &= \gcd{(2 \times 12, 5 \times 12)} \\ &= |12| \gcd{(2,5)} \\ &= 12 \times 1 \\ &= 12. \end{align*}

The same works for negative shared factors; $\gcd{(-15,-25)} = |-5|\gcd{(3,5)} = 5 \times 1 = 5$ .

Note

Lemma 5
For any integers $a$ , $b$ and $c$ , if $a \mid bc$ and $\gcd{(a,b)} = 1$ , then $a \mid c$ .

Basically, if $a$ divides a product but is coprime to one of the factors, then it has no choice but to divide the other factor; none of $a$ can "hide" inside $b$ , so all of it must land on $c$ .

Example. Suppose $7 \mid 3c$ for some integer $c$ . What can we say about $c$ ?
Since $\gcd{(7,3)} = 1$ , Lemma 5 tells us that $7 \mid c$ . For instance, if $3c = 42$ , then $c = 14$ , and indeed $7 \mid 14$ .

It is important to remember that Lemma 5 fails without the coprime condition. For example, $6 \mid 4 \times 3$ , but $\gcd{(6,4)} = 2 \neq 1$ , and sure enough $6 \nmid 4$ and $6 \nmid 3$ .

The Key Lemma#

The last property is the engine behind the Euclidean Algorithm, so it gets its own proof.

Note

Lemma 6
For any integers $a$ , $b$ , $c$ and $q$ , if $a = qb + c$ , then

\boxed{\gcd{(a,b)} = \gcd{(b,c)}}.

Proof. We show that the pairs $(a,b)$ and $(b,c)$ have exactly the same common divisors; if the two sets of common divisors are identical, then in particular their greatest elements must be equal.
Suppose $d \mid a$ and $d \mid b$ . Since $c = a - qb$ is an integer combination of $a$ and $b$ , we get $d \mid c$ ; so every common divisor of $a$ and $b$ is also a common divisor of $b$ and $c$ .
Conversely, suppose $d \mid b$ and $d \mid c$ . Since $a = qb + c$ is an integer combination of $b$ and $c$ , we get $d \mid a$ ; so every common divisor of $b$ and $c$ is also a common divisor of $a$ and $b$ .
Hence the two pairs share the same common divisors, and therefore the same greatest common divisor; that is, $\gcd{(a,b)} = \gcd{(b,c)}$ . $\blacksquare$

Basically, replacing $a$ with its remainder on division by $b$ does not change the GCD; this lets us shrink a GCD problem into a smaller one over and over again until it becomes trivial, which is exactly what the Euclidean Algorithm does.

Example. Show that any two consecutive integers are coprime, and hence find $\gcd{(2026, 2025)}$ .
For any integer $n$ we can write

n + 1 = 1 \times n + 1,

so by Lemma 6,

\begin{align*} \gcd{(n+1, n)} &= \gcd{(n, 1)} \\ &= 1, \text{ (by Lemma 1)}. \end{align*}

Therefore any two consecutive integers are coprime; in particular, $\gcd{(2026, 2025)} = 1$ , with no arithmetic needed at all.

The Division Theorem#

Note

The Division Theorem
For any integers $a$ and $b$ with $b \neq 0$ , there exist unique integers $q$ and $r$ such that both

a = qb + r \text{ with } 0 \leq r < |b|.

We call $q$ the quotient and $r$ the remainder when $a$ is divided by $b$ .

It is important to note here that $r$ must ALWAYS be at least 0, even if $q$ is negative;

30 = -7 \times -4 + 2

Example. Find the quotient and remainder when $30$ is divided by $7$ ; $30$ is divided by $6$ ; $30$ is divided by $-4$ ; and $-30$ is divided by $4$ .

\begin{aligned} 30 &= 4 \times 7 + 2 && \text{where } q = 4,\ r = 2, \\ 30 &= 5 \times 6 + 0 && \text{where } q = 5,\ r = 0, \\ 30 &= -7 \times -4 + 2 && \text{where } q = -7,\ r = 2, \\ -30 &= -8 \times 4 + 2 && \text{where } q = -8,\ r = 2. \end{aligned}

A common trap with negative $a$ is to write $-30 = -7 \times 4 - 2$ ; this is arithmetically true, but it is NOT the Division Theorem, because the remainder $-2$ is negative. Instead, we push the quotient one further down to $-8$ so that the remainder lands back in the range $0 \leq r < |b|$ . Basically, for negative $a$ you round the quotient towards $-\infty$ , not towards $0$ .

Proof. First suppose $b > 0$ . Choose

q = \left\lfloor \frac{a}{b} \right\rfloor \text{ and } r = a - qb,

i.e. $q$ is the largest integer less than or equal to $\frac{a}{b}$ . Then $a = qb + r$ holds by construction, and since

q \leq \frac{a}{b} < q + 1,

multiplying through by $b$ and then subtracting $qb$ gives

0 \leq a - qb < b, \text{ that is, } 0 \leq r < b,

as required. The case $b < 0$ works the same way, except we instead take $q = \left\lceil \frac{a}{b} \right\rceil$ .
For uniqueness, suppose there were a second solution $a = q'b + r'$ with $0 \leq r' < |b|$ . Setting the two expressions for $a$ equal,

\begin{align*} qb + r &= q'b + r' \\ (q - q')b &= r' - r. \end{align*}

Since both remainders lie in the interval $[0, |b|)$ , their difference satisfies $-|b| < r' - r < |b|$ . But $r' - r = (q - q')b$ is an integer multiple of $b$ , and the only multiple of $b$ strictly between $-|b|$ and $|b|$ is $0$ . Hence $r = r'$ and $q = q'$ ; the quotient and remainder are unique. $\blacksquare$

The Euclidean Algorithm#

Note

The Euclidean Algorithm
The Euclidean Algorithm is a process that, given two integers $a$ and $b \neq 0$ as inputs, efficiently outputs $\gcd{(a,b)}$ . The algorithm makes use of the Division Theorem, finding quotients and remainders iteratively in the following way:

\begin{aligned} a &= q_0 \times b + r_0 && \text{where } q_0, r_0 \in \mathbb{Z} \text{ and } |b| > r_0 \geq 0, \\ b &= q_1 \times r_0 + r_1 && \text{where } q_1, r_1 \in \mathbb{Z} \text{ and } r_0 > r_1 \geq 0, \\ r_0 &= q_2 \times r_1 + r_2 && \text{where } q_2, r_2 \in \mathbb{Z} \text{ and } r_1 > r_2 \geq 0, \\ r_1 &= q_3 \times r_2 + r_3 && \text{where } q_3, r_3 \in \mathbb{Z} \text{ and } r_2 > r_3 \geq 0, \\ &\;\;\vdots && \;\;\vdots \\ r_{n-2} &= q_n \times r_{n-1} + r_n && \text{where } q_n, r_n \in \mathbb{Z} \text{ and } r_{n-1} > r_n \geq 0, \\ r_{n-1} &= q_{n+1} \times r_n + 0 && \text{where } q_{n+1} \in \mathbb{Z} \text{ and } r_n > 0. \end{aligned}

The process terminates immediately after the $n$ th step, when the remainder is first found to be zero. The remainder at the $n$ th step is then the GCD of $a$ and $b$ . That is,

\boxed{\gcd{(a,b)} = r_n}.

Basically, you divide $a$ by $b$ , then divide $b$ by the remainder, then divide that remainder by the new remainder, and so on; each line just feeds the two right-most numbers of the line above back into the Division Theorem. The remainders keep strictly shrinking, so eventually one hits $0$ , and the last non-zero remainder is the GCD.

Example. Use the Euclidean Algorithm to find $\gcd{(403, 286)}$ .

\begin{align*} 403 &= 1 \times 286 + 117, \\ 286 &= 2 \times 117 + 52, \\ 117 &= 2 \times 52 + 13, \\ 52 &= 4 \times 13 + 0. \end{align*}

The last non-zero remainder is $13$ , therefore $\gcd{(403, 286)} = 13$ .

Example. Use the Euclidean Algorithm to find $\gcd{(283, 193)}$ .

\begin{align*} 283 &= 1 \times 193 + 90, \\ 193 &= 2 \times 90 + 13, \\ 90 &= 6 \times 13 + 12, \\ 13 &= 1 \times 12 + 1, \\ 12 &= 12 \times 1 + 0. \end{align*}

The last non-zero remainder is $1$ , therefore $\gcd{(283, 193)} = 1$ ; i.e. $283$ and $193$ are coprime.

Example. Use the Euclidean Algorithm to find $\gcd{(1071, 462)}$ .
Even with bigger numbers the remainders collapse very quickly;

\begin{align*} 1071 &= 2 \times 462 + 147, \\ 462 &= 3 \times 147 + 21, \\ 147 &= 7 \times 21 + 0. \end{align*}

Therefore $\gcd{(1071, 462)} = 21$ .

Negative Inputs#

Since an integer and its negative have exactly the same divisors, we have

\gcd{(-a, b)} = \gcd{(a, b)} = \gcd{(a, -b)},

so the easiest way to deal with a negative input is to just drop the sign before starting.

Example. Find $\gcd{(-408, 126)}$ .
Dropping the sign first, $\gcd{(-408, 126)} = \gcd{(408, 126)}$ , so

\begin{align*} 408 &= 3 \times 126 + 30, \\ 126 &= 4 \times 30 + 6, \\ 30 &= 5 \times 6 + 0. \end{align*}

Therefore $\gcd{(-408, 126)} = 6$ .
Alternatively, the algorithm works perfectly fine on the negative input directly, as long as every remainder stays in the range $0 \leq r < |b|$ (recall that the Division Theorem forces $r \geq 0$ even when the quotient goes negative);

\begin{align*} -408 &= -4 \times 126 + 96, \\ 126 &= 1 \times 96 + 30, \\ 96 &= 3 \times 30 + 6, \\ 30 &= 5 \times 6 + 0. \end{align*}

Both routes agree that the answer is $6$ ; dropping the sign first is simply less error-prone.

Why the Algorithm Works#

Note

Theorem
For any integer inputs $a$ and $b \neq 0$ , the Euclidean Algorithm always outputs $\gcd{(a,b)}$ .

Proof. There are two things to show; that the process always terminates, and that it always returns the standard GCD.
For termination, notice that the remainders satisfy

|b| > r_0 > r_1 > r_2 > \cdots \geq 0,

so they form a strictly decreasing sequence of non-negative integers; such a sequence cannot go on forever, so a zero remainder must appear after at most $|b|$ steps.
For correctness, every line of the algorithm has exactly the form of Lemma 6, so each step replaces the current pair with a smaller pair that has the same GCD. If the algorithm terminates after $n$ steps, then

\begin{align*} \gcd{(a,b)} &= \gcd{(b, r_0)} \\ &= \gcd{(r_0, r_1)} \\ &\;\;\vdots \\ &= \gcd{(r_{n-1}, r_n)} \\ &= \gcd{(r_n, 0)} \\ &= r_n, \text{ (by Lemma 2)}. \qquad \blacksquare \end{align*}

Notice how the very last pair $(r_n, 0)$ hands us the answer for free; this is exactly why Lemma 2 matters.

More Examples#

Example. Find $\gcd{(89, 55)}$ .
Both $89$ and $55$ are consecutive Fibonacci numbers;

\begin{align*} 89 &= 1 \times 55 + 34, \\ 55 &= 1 \times 34 + 21, \\ 34 &= 1 \times 21 + 13, \\ 21 &= 1 \times 13 + 8, \\ 13 &= 1 \times 8 + 5, \\ 8 &= 1 \times 5 + 3, \\ 5 &= 1 \times 3 + 2, \\ 3 &= 1 \times 2 + 1, \\ 2 &= 2 \times 1 + 0. \end{align*}

Therefore $\gcd{(89, 55)} = 1$ ; any two consecutive Fibonacci numbers are coprime. Notice how every quotient is $1$ until the final step, and the remainders are just the Fibonacci numbers marching back down ( $34, 21, 13, 8, 5, 3, 2, 1$ ); consecutive Fibonacci numbers are actually the worst case input for the Euclidean Algorithm, forcing the maximum possible number of steps for numbers of their size.

Example. A rectangular floor is $462$ cm by $330$ cm. What is the side length of the largest square tile that can tile the floor exactly, and how many tiles are needed?
A square tile of side $s$ tiles the floor exactly if and only if $s \mid 462$ and $s \mid 330$ ; the largest such $s$ is precisely $\gcd{(462, 330)}$ .

\begin{align*} 462 &= 1 \times 330 + 132, \\ 330 &= 2 \times 132 + 66, \\ 132 &= 2 \times 66 + 0. \end{align*}

So the largest tile has side $66$ cm, and the number of tiles needed is

\begin{align*} \frac{462}{66} \times \frac{330}{66} &= 7 \times 5 \\ &= 35. \end{align*}

Therefore, the largest square tile is $66$ cm $\times$ $66$ cm, and $35$ tiles are needed.