8.2 GCD, Euclid’s Algorithm, and Bézout’s Identity

Section 8.1 described every positive integer through its prime factors. If two numbers are already factored, their shared primes reveal their common divisors. But factorization is often much more work than we need.

This section develops a recursive alternative: repeatedly replace a pair by a smaller remainder pair while preserving all common divisors.

Common divisors and the greatest common divisor

Let $a$ and $b$ be integers, not both zero. An integer $d$ is a common divisor of $a$ and $b$ if

The greatest common divisor, written

is the greatest positive integer dividing both numbers.

For example, the positive divisors of $84$ are

while the positive divisors of $30$ are

Their positive common divisors are $1,2,3,6$, so

The order does not matter:

For $a\ne0$,

because every divisor of $a$ divides $0$, and the greatest positive divisor of $a$ is $|a|$.

Reading a gcd from prime exponents

Suppose

and

A common divisor can use only primes present in both numbers, and for each shared prime it can use no more than the smaller exponent. Therefore

This method is conceptually useful, but it first requires both factorizations. Euclid's algorithm avoids that requirement.

The division algorithm produces a quotient and remainder

Let $a\in\mathbb Z$ and let $b$ be a positive integer. The division algorithm states that there are unique integers $q$ and $r$ such that

Here:

• $q$ is the quotient;

• $r$ is the remainder;

• the inequality $0\le r<b$ selects one unique remainder.

For example,

Thus dividing $252$ by $105$ gives quotient $q=2$ and remainder $r=42$.

We write the remainder as

The expression “mod” here is a remainder operation. Section 8.3 will use the same idea to define congruence classes.

The key invariant of Euclid’s algorithm

If

then

Why are the common divisors unchanged?

First, suppose $d$ divides both $a$ and $b$. Because

the integer-linear-combination rule from Section 8.1 gives $d\mid r$. Thus every common divisor of $a,b$ is also a common divisor of $b,r$.

Conversely, suppose $d$ divides both $b$ and $r$. Since

we obtain $d\mid a$. Thus every common divisor of $b,r$ is also a common divisor of $a,b$.

The two pairs have exactly the same common divisors, so their greatest positive common divisor is the same.

This equality is an invariant: the pair of numbers changes, but its gcd does not.

Euclid’s algorithm step by step

To compute $\gcd(a,b)$ for positive integers $a\ge b$:

1. divide $a$ by $b$ to obtain $a=bq+r$;

2. replace the pair $(a,b)$ by $(b,r)$;

3. repeat until the remainder is $0$;

4. return the last nonzero remainder.

Example: $\gcd(252,105)$

The corresponding invariant chain is

Therefore

Why the algorithm terminates

Every nonzero remainder satisfies

So the second component of the pair forms a strictly decreasing sequence of nonnegative integers. It cannot decrease forever. Eventually a remainder must be $0$.

This is precisely the well-founded recursive reasoning from Chapter 7.

The algorithm can be written recursively as

The first line is the base case. The second line is the reducing recursive step.

Send two integer streams through a remainder waterfall. Each gate forms quotient-sized groups, pours the remainder into the next channel, and carries an invariant set of common-divisor tokens. Step manually or animate until the final nonzero channel reveals the gcd.

Bézout’s identity turns the gcd into a combination

For integers $a,b$, not both zero, Bézout’s identity states that there exist integers $x,y$ such that

The numbers $x$ and $y$ are called Bézout coefficients. They are not usually unique.

Euclid's algorithm finds the gcd. The extended Euclidean algorithm also recovers coefficients by reversing the remainder equations.

Back-substitution example

The forward Euclidean equations were

and

Solve the second equation for the last nonzero remainder:

Now solve the first equation for $42$:

Substitute this expression for $42$:

Thus one pair of Bézout coefficients is

and we can check

Coefficient vectors preserve the original inputs

Another viewpoint tracks every remainder as a combination of the original pair.

Represent

by coefficient vector $(1,0)$, and represent

by $(0,1)$.

When a remainder is formed by

its coefficient vector is obtained by the same subtraction:

For the example:

and

The final vector gives the Bézout coefficients directly.

Which linear combinations are possible?

Because the gcd divides both $a$ and $b$, it divides every integer combination $ax+by$. Bézout's identity also shows that the gcd itself is such a combination.

Therefore the equation

has integer solutions exactly when

For example,

has integer solutions because $21\mid42$. Multiplying the Bézout identity by $2$ gives one solution:

But $252x+105y=10$ has no integer solution because $21\nmid10$.

Reverse an Euclidean trace through a coefficient-vector switchyard. At every junction, choose the quotient-weighted subtraction that rebuilds the previous remainder; incorrect substitutions visibly break the final identity, while a correct route produces checkable Bézout coefficients.

Section bridge

Bézout coefficients do more than solve linear equations. When $\gcd(a,n)=1$, a coefficient in $ax+ny=1$ becomes a multiplicative inverse of $a$ modulo $n$. Section 8.3 develops that modular viewpoint and then combines several remainder conditions with the Chinese Remainder Theorem.