GCDs and the Euclidean Algorithm

GCDs

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.

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

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

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$.

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.

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{array}{rl}\gcd (12,\gcd (18,30))& =\gcd (12,6)\\ & =6.\end{array}$$

Pairing from the left,

$$\begin{array}{rl}\gcd (\gcd (12,18),30)& =\gcd (6,30)\\ & =6.\end{array}$$

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

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{array}{rl}\gcd (24,60)& =\gcd (2\times 12,5\times 12)\\ & =|12|\gcd (2,5)\\ & =12\times 1\\ & =12.\end{array}$$

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

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\ne 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.

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)$. $■$

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{array}{rl}\gcd (n+1,n)& =\gcd (n,1)\\ & =1,\text{ (by Lemma 1)}.\end{array}$$

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

The Division Theorem

$$a=qb+r\text{ with }0\le 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{array}{rlrl}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{array}$$

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\le r<|b|$. Basically, for negative $a$ you round the quotient towards $-\infty$, not towards $0$.

Proof. First suppose $b>0$. Choose

$$q=\lfloor \frac{a}{b}\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\le \frac{a}{b}<q+1,$$

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

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

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

$$\begin{array}{rl}qb+r& =q^{\prime }b+r^{\prime }\\ (q-q^{\prime })b& =r^{\prime }-r.\end{array}$$

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

The Euclidean Algorithm

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{array}{rl}403& =1\times 286+117,\\ 286& =2\times 117+52,\\ 117& =2\times 52+13,\\ 52& =4\times 13+0.\end{array}$$

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

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

$$\begin{array}{rl}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{array}$$

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{array}{rl}1071& =2\times 462+147,\\ 462& =3\times 147+21,\\ 147& =7\times 21+0.\end{array}$$

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{array}{rl}408& =3\times 126+30,\\ 126& =4\times 30+6,\\ 30& =5\times 6+0.\end{array}$$

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\le r<|b|$ (recall that the Division Theorem forces $r\ge 0$ even when the quotient goes negative);

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

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

Why the Algorithm Works

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 \ge 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{array}{rl}\gcd (a,b)& =\gcd (b,r_0)\\ & =\gcd (r_0,r_1)\\ & ⋮\\ & =\gcd (r_{n-1},r_n)\\ & =\gcd (r_n,0)\\ & =r_n,\text{ (by Lemma 2)}.■\end{array}$$

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{array}{rl}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{array}$$

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{array}{rl}462& =1\times 330+132,\\ 330& =2\times 132+66,\\ 132& =2\times 66+0.\end{array}$$

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

$$\begin{array}{rl}\frac{462}{66}\times \frac{330}{66}& =7\times 5\\ & =35.\end{array}$$

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