# Introduction
Bézout’s Identity is a fundamental theorem in number theory that describes a powerful relationship between the greatest common divisor of two integers and their integer linear combinations. It establishes that the greatest common divisor of two integers can always be expressed as a sum of integer multiples of those numbers.
The theorem is named after the French mathematician Étienne Bézout, whose work contributed to the development of algebra and number theory. The identity is particularly important because it connects the calculation of the Highest Common Factor (HCF), also called the Greatest Common Divisor (GCD), with algebraic equations.
The central formula is:
**ax + by = gcd(a, b)**
Here, a and b are integers, gcd(a, b) represents their greatest common divisor, and x and y are integers that make the equation true.
For example, consider the integers 30 and 18. Their greatest common divisor is 6. We can express 6 as an integer linear combination of 30 and 18:
30 × 2 + 18 × (−3) = 6
Simplifying gives:
60 − 54 = 6
Therefore, one valid representation is:
30(2) + 18(−3) = gcd(30, 18)
This example demonstrates that the GCD is not merely a number that divides both integers. It can also be represented using integer coefficients multiplied by the original numbers.
Bézout’s Identity is closely connected to Euclid’s Division Lemma and the extended Euclidean algorithm. It is used in solving linear Diophantine equations, finding modular multiplicative inverses, studying divisibility, and understanding several important concepts in abstract algebra and elementary number theory.
## 1. What Is Bézout’s Identity?
Bézout’s Identity states that for any integers a and b that are not both zero, there exist integers x and y such that:
**ax + by = gcd(a, b)**
The expression ax + by is called an integer linear combination of a and b.
The term *integer linear combination* means that the original numbers are multiplied by integers and then added together. The coefficients x and y may be positive, negative, or zero.
For example, let a = 12 and b = 8.
The greatest common divisor is:
gcd(12, 8) = 4
We can represent 4 as:
12(1) + 8(−1) = 4
Therefore:
12 − 8 = 4
This confirms the identity for these numbers, with x = 1 and y = −1.
### Understanding the formula
The formula contains four important components.
**a and b:** These are the original integers. They may be positive, negative, or zero, provided they are not both zero.
**x and y:** These are integer coefficients chosen to satisfy the equation.
**gcd(a, b):** This is the greatest positive integer that divides both a and b exactly.
**ax + by:** This is the integer linear combination that equals the GCD.
The identity guarantees that suitable integer coefficients always exist. It does not claim that these coefficients are always unique. In many cases, several different pairs of integers can satisfy the same equation.
## 2. Statement of Bézout’s Identity
The formal statement is:
**For any integers a and b, not both zero, there exist integers x and y such that ax + by = gcd(a, b).**
For positive integers, the greatest common divisor is the largest positive integer dividing both numbers.
For example, consider 21 and 15.
Their common positive divisors include 1 and 3, so:
gcd(21, 15) = 3
We can write:
21(−2) + 15(3) = 3
Calculating the left-hand side gives:
−42 + 45 = 3
Therefore, x = −2 and y = 3 provide a valid representation.
This example shows why negative coefficients are allowed. If coefficients were restricted to non-negative integers, it would not always be possible to represent the GCD using the identity.
### What does the theorem guarantee?
Bézout’s Identity guarantees three main facts.
First, the GCD can be expressed as an integer linear combination of the original integers.
Second, the coefficients can be found using the extended Euclidean algorithm.
Third, when the GCD is 1, the two integers are relatively prime, and there exist integers x and y satisfying:
ax + by = 1
This final case is especially useful in modular arithmetic and in solving certain integer equations.
## 3. Mathematical Formula and Important Properties
The main formula is:
ax + by = gcd(a, b)
For positive integers a and b, write their GCD as d. Then:
ax + by = d
The values x and y are integers.
### Property 1: The GCD divides both integers
If d = gcd(a, b), then:
d divides a
and:
d divides b
This is part of the definition of the greatest common divisor.
### Property 2: Every common divisor divides the GCD
Every common divisor of a and b divides every integer linear combination of a and b.
If d divides both a and b, then d divides ax and d divides by for any integers x and y. Consequently, d divides ax + by.
This property is central to the proof of Bézout’s Identity.
### Property 3: Relatively prime integers
Two integers are called relatively prime or coprime if their GCD is 1.
For coprime integers a and b, Bézout’s Identity becomes:
ax + by = 1
For example:
5(−1) + 2(3) = 1
Since gcd(5, 2) = 1, this is a valid Bézout representation.
### Property 4: Coefficients are not necessarily unique
Consider the equation:
12x + 8y = 4
One solution is x = 1 and y = −1.
Indeed:
12(1) + 8(−1) = 4
Another solution is x = −1 and y = 2:
12(−1) + 8(2) = −12 + 16 = 4
Both pairs satisfy the equation. Thus, the identity guarantees the existence of integer coefficients, not one unique pair.
## 4. Proof of Bézout’s Identity
One standard proof uses the well-ordering principle for positive integers.
The well-ordering principle states that every non-empty set of positive integers contains a smallest element.
Let a and b be integers that are not both zero. For the proof, we can initially consider their absolute values and assume a and b are non-negative, with at least one positive. The general result for signed integers follows by adjusting the signs of the coefficients.
Consider the set of all positive integer linear combinations of a and b:
S = {ax + by : x, y are integers and ax + by > 0}
This set is non-empty. For example, when a is positive, choosing x = 1 and y = 0 produces a positive combination. If a is zero and b is positive, choosing x = 0 and y = 1 produces a positive combination.
By the well-ordering principle, S contains a smallest positive integer. Let that integer be d.
Therefore:
d = ax + by
for some integers x and y.
We will prove that d is the greatest common divisor of a and b.
### Step 1: Show that d divides a
Divide a by d using the division algorithm. There exist integers q and r such that:
a = dq + r
where:
0 ≤ r < d
Rearrange:
r = a − dq
Since d = ax + by:
r = a − q(ax + by)
Expand:
r = a − aqx − bqy
Rearrange:
r = a(1 − qx) + b(−qy)
The numbers 1 − qx and −qy are integers. Thus, r is an integer linear combination of a and b.
If r were positive, it would be an element of S smaller than d. This would contradict the choice of d as the smallest positive element of S.
Therefore, r = 0.
Since a = dq + r, we obtain:
a = dq
Hence, d divides a.
### Step 2: Show that d divides b
Apply the same argument to b.
By the division algorithm:
b = dq₂ + r₂
where:
0 ≤ r₂ < d
Rearranging and using d = ax + by shows that r₂ is also an integer linear combination of a and b.
If r₂ were positive, it would contradict the minimality of d.
Therefore, r₂ = 0, which means:
b = dq₂
Hence, d divides b.
### Step 3: Show that d is the greatest common divisor
We have proved that d divides both a and b. Therefore, d is a common divisor.
Now let c be any common divisor of a and b.
Since c divides a and b, it also divides ax and by for every pair of integers x and y. Consequently, c divides their sum:
ax + by = d
Thus, every common divisor of a and b divides d.
Since d itself is a common divisor and every common divisor divides d, d is the greatest common divisor.
Therefore:
d = gcd(a, b)
But d was defined as an integer linear combination:
d = ax + by
Hence:
**ax + by = gcd(a, b)**
This proves Bézout’s Identity.
## 5. Relationship Between Bézout’s Identity and the Euclidean Algorithm
The Euclidean algorithm calculates the GCD by repeatedly applying division. Bézout’s Identity states that this GCD can be written as an integer linear combination of the original numbers.
The extended Euclidean algorithm combines these ideas. It finds both the GCD and the coefficients x and y.
Consider 30 and 18.
First, apply Euclid’s Division Lemma:
30 = 18 × 1 + 12
Next:
18 = 12 × 1 + 6
Finally:
12 = 6 × 2 + 0
The last non-zero remainder is 6. Therefore:
gcd(30, 18) = 6
Now work backwards to express 6 as a linear combination of 30 and 18.
From the second equation:
6 = 18 − 12
From the first equation:
12 = 30 − 18
Substitute this expression:
6 = 18 − (30 − 18)
Expand:
6 = 18 − 30 + 18
Therefore:
6 = −30 + 2(18)
This is a Bézout representation with:
x = −1
y = 2
Check:
30(−1) + 18(2) = −30 + 36 = 6
Hence, Bézout’s Identity is verified for 30 and 18.
### Why does working backwards help?
The Euclidean algorithm finds the GCD through successive remainders. Each remainder is an integer linear combination of the two preceding numbers.
When we work backwards, we replace the remainders with expressions involving the previous numbers. Eventually, the last non-zero remainder is expressed in terms of the original integers.
That process produces the coefficients required by Bézout’s Identity.
## 6. Solved Examples of Bézout’s Identity
### Example 1: Find a Bézout representation for 12 and 8
First calculate the GCD:
12 = 8 × 1 + 4
8 = 4 × 2 + 0
Therefore:
gcd(12, 8) = 4
From the first equation:
4 = 12 − 8
Thus:
12(1) + 8(−1) = 4
The coefficients are x = 1 and y = −1.
### Example 2: Find a Bézout representation for 35 and 15
Apply the Euclidean algorithm:
35 = 15 × 2 + 5
15 = 5 × 3 + 0
Therefore:
gcd(35, 15) = 5
From the first equation:
5 = 35 − 2(15)
So:
35(1) + 15(−2) = 5
The coefficients are x = 1 and y = −2.
### Example 3: Find a Bézout representation for 56 and 42
Apply division:
56 = 42 × 1 + 14
42 = 14 × 3 + 0
Therefore:
gcd(56, 42) = 14
Rearrange the first equation:
14 = 56 − 42
Thus:
56(1) + 42(−1) = 14
The coefficients are x = 1 and y = −1.
### Example 4: Find a Bézout representation for 101 and 23
Apply the Euclidean algorithm:
101 = 23 × 4 + 9
23 = 9 × 2 + 5
9 = 5 × 1 + 4
5 = 4 × 1 + 1
4 = 1 × 4 + 0
Therefore:
gcd(101, 23) = 1
Now work backwards.
From:
5 = 4 + 1
we get:
1 = 5 − 4
Since 4 = 9 − 5:
1 = 5 − (9 − 5)
1 = 2(5) − 9
Since 5 = 23 − 2(9):
1 = 2(23 − 2(9)) − 9
1 = 2(23) − 5(9)
Since 9 = 101 − 4(23):
1 = 2(23) − 5(101 − 4(23))
1 = 22(23) − 5(101)
Therefore:
**101(−5) + 23(22) = 1**
The coefficients are x = −5 and y = 22.
This result also proves that 101 and 23 are relatively prime.
### Example 5: Find a Bézout representation for 252 and 105
Apply the Euclidean algorithm:
252 = 105 × 2 + 42
105 = 42 × 2 + 21
42 = 21 × 2 + 0
Therefore:
gcd(252, 105) = 21
From the second equation:
21 = 105 − 2(42)
Using 42 = 252 − 2(105):
21 = 105 − 2(252 − 2(105))
21 = 5(105) − 2(252)
Therefore:
**252(−2) + 105(5) = 21**
The coefficients are x = −2 and y = 5.
### Example 6: Find a Bézout representation for 99 and 78
Apply division:
99 = 78 × 1 + 21
78 = 21 × 3 + 15
21 = 15 × 1 + 6
15 = 6 × 2 + 3
6 = 3 × 2 + 0
Therefore:
gcd(99, 78) = 3
Work backwards:
3 = 15 − 2(6)
Since 6 = 21 − 15:
3 = 15 − 2(21 − 15)
3 = 3(15) − 2(21)
Since 15 = 78 − 3(21):
3 = 3(78 − 3(21)) − 2(21)
3 = 3(78) − 11(21)
Since 21 = 99 − 78:
3 = 3(78) − 11(99 − 78)
3 = −11(99) + 14(78)
Therefore:
**99(−11) + 78(14) = 3**
The coefficients are x = −11 and y = 14.
## 7. Bézout’s Identity and Linear Diophantine Equations
A linear Diophantine equation is a linear equation in which the unknowns are required to be integers.
Consider:
ax + by = c
where a, b, and c are integers.
Bézout’s Identity helps determine when this equation has an integer solution.
The key result is:
**The equation ax + by = c has an integer solution if and only if gcd(a, b) divides c**, provided a and b are not both zero.
### Why is divisibility necessary?
Let d = gcd(a, b).
Since d divides both a and b, it divides every integer linear combination ax + by.
Therefore, if:
ax + by = c
then d must divide c.
If d does not divide c, no integer solution can exist.
### Why is divisibility sufficient?
Bézout’s Identity guarantees integers x₀ and y₀ such that:
ax₀ + by₀ = d
If d divides c, write c = kd for some integer k.
Multiply the identity by k:
a(kx₀) + b(ky₀) = kd = c
Thus, x = kx₀ and y = ky₀ provide an integer solution.
This proves the condition.
### Example: Solve 6x + 9y = 3
First calculate:
gcd(6, 9) = 3
Since 3 divides the right-hand side, an integer solution exists.
Divide the equation by 3:
2x + 3y = 1
One solution is:
x = −1, y = 1
Check:
6(−1) + 9(1) = −6 + 9 = 3
Therefore, the equation has an integer solution.
### Example: Determine whether 6x + 9y = 4 has an integer solution
The GCD of 6 and 9 is 3.
However, 3 does not divide 4.
Therefore, the equation has no integer solution.
This demonstrates how