A Classic Numbers Challenge

I’m not very interested in number theory, but when I am, it is rather interesting. Bézout’s lemma is a fascinating result that invokes two uses of the division algorithm. But first, we need the notion of a greatest common divisor, abbreviated by $\gcd$ .

Definition 1. Let $a, b$ be positive integers. An integer $d$ is a common divisor of $a, b$ if the following property holds:

$d \mid a$ and $d \mid b$ .

Additionally, $d$ is a greatest common divisor of $a, b$ , denoted $d = \gcd(a, b)$ , if the following additional property holds

For any common divisor $c$ of $a, b$ , $c \mid d$ .

It is relatively clear that in this formulation of greatest common divisors, $d$ is unique.

Bézout’s Lemma. Let $a,b$ be positive integers with greatest common divisor $\gcd(a, b) = 1$ . We call $a, b$ relatively prime. Then there exist integers $x,y$ such that $ax+by = 1$ .

Proof. The proof of this result is ingenious. I’m certainly not its originator, but I am fascinated by it. The result is obvious if $a = 1$ or $b = 1$ . Suppose $a > 1$ and $b > 1$ .

Define the set $K := \{ar + bs : r, s \in \mathbb Z\} \cap \mathbb Z_{> 0}$ . The line of attack is to find a minimum element $d$ of $K$ so that $ax +by = d$ , then prove that $d = 1$ .

For the first claim, use the division algorithm to find integers $q$ and $r \in [0, a)$ such that $b = aq+r$ . We need to show that $r \neq 0$ . If $r = 0$ , then $a \mid b$ implies $a \mid \gcd(a, b)= 1$ , thus $2 \leq a \leq 1 < 2$ , a contradiction. Thus, $r \neq 0$ and $r = b-aq \in K$ .

Since $K \neq \emptyset$ and is bounded below, it contains a smallest element $d := \min(K)$ . Thus, there exist integers $x,y$ such that $ax + by = d$ .

For the second claim, we need to show that $d \mid a$ . A symmetrical argument shows that $d \mid b$ , which implies that $d \mid \gcd(a, b) = 1$ . Since $1 \mid d$ automatically, we will have $d = 1$ , as required.

For the claim $d \mid a$ , employ the division algorithm a second time to find integers $q'$ and $r' \in [0, d)$ such that $a = dq' + r'$ . Then $r' = a - dq'$ . This time, we need to show that $r' = 0$ . To that end, substitute $d$ to obtain

$r' = a - (ax+by)q' = a(1-xq') + b(-yq').$

If $r' > 0$ , then $r' \in K$ , so that $d \leq r' < d$ , a contradiction. Thus, $r' = 0$ , yielding $a = dq' \Rightarrow d \mid a$ .

The implications of Bézout’s identity are nontrivial.

Theorem 1. Let $a, b$ be positive integers with $\gcd(a, b) = d$ . Then there exist integers $x, y$ such that $ax + by = d$ . Furthermore, any integer is of the form $ax + by$ if and only if it is a multiple of $d$ .

Proof. For the first result, $\gcd(a/d, b/d) = \gcd(a, b)/d = d/d = 1$ . Then, there are integers $x, y$ such that

$\displaystyle ax+by = d\left(\frac ad \cdot x + \frac bd \cdot y\right) = d \cdot 1 = d.$

The second result follows from the first via divisibility properties.

We have shown that every number can be broken down into a unique product of primes, known as the fundamental theorem of arithmetic.

Therein, we employed Euclid’s lemma, which, strictly speaking, we have not proven. Have we broken mathematics? Nope. It turns out that Bézout’s lemma is key to establish Euclid’s lemma, with which we can prove the fundamental theorem of arithmetic.

Theorem 2 (Euclid’s Lemma). Let $p$ be a prime number. Then for integers $a, b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$ .

Proof. Suppose $p \mid ab$ . If $p \mid a$ , then we are done. Suppose otherwise. Define $d := \gcd(p, a)$ . Since $d \mid p$ and $p$ is prime, $d = 1$ or $d = p$ . If $d = p$ , then $p = d \mid a$ , a contradiction. Thus, $\gcd(p, a) = 1$ .

By Bézout’s lemma, there exist integers $x,y$ such that $px+ay = 1$ . Multiplying by $b$ yields $pxb + (ab)y = (px+ay)b = b$ . Since $p \mid ab$ , find an integer $k$ such that $ab = kp$ , so that

$p(xb + ky) = pxb + (kp)y = pxb + (ab)y = b.$

This implies that $p \mid b$ , as required.

—Joel Kindiak, 11 Nov 24, 1300H

Responses

The Problem with Rationals – KindiakMath

December 25, 2024 at 12:57 am

[…] tells us . Using Euclid’s lemma, we have . Thus, find an integer such that . This […]

LikeLike

What Makes Strong Induction Strong? – KindiakMath

December 28, 2025 at 12:44 am

[…] will use Euclid’s lemma to establish uniqueness, for the sake of completeness. As an aside, Euclid’s lemma will be […]

LikeLike

The Problem with Rationals – KindiakMath

March 20, 2026 at 1:36 am

[…] contradiction such an exists. Write , where are integers with and having no common factors (in number-theoretic language, ). By […]

LikeLike

A Classic Numbers Challenge

Share this:

Responses

Leave a reply to What Makes Strong Induction Strong? – KindiakMath Cancel reply