Bézout's Identity connects divisibility, greatest common divisors, and integer linear combinations. This cheat sheet helps students find integers that solve equations of the form . The Extended Euclidean Algorithm gives a reliable way to compute both the greatest common divisor and the needed coefficients.
These tools are especially important in number theory, modular arithmetic, and cryptography.
The core idea is that for any integers and , not both zero, there exist integers and such that . The Euclidean Algorithm finds by repeated division with remainders. The extended version works backward through those divisions to express the gcd as a linear combination of the original numbers.
If , Bézout's Identity also gives the modular inverse of modulo .
Key Facts
- Bézout's Identity states that for integers and , not both zero, there exist integers and such that .
- The Euclidean Algorithm uses repeated division: , where , then replaces with .
- The last nonzero remainder in the Euclidean Algorithm is .
- The Extended Euclidean Algorithm rewrites remainders backward until is expressed as .
- If , then and are relatively prime and there exist integers and such that .
- A linear Diophantine equation has integer solutions exactly when divides .
- If , then multiplying by gives one solution to when .
- If , then is a modular inverse of modulo , so .
Vocabulary
- Greatest common divisor
- The greatest common divisor is the largest positive integer that divides both and .
- Bézout coefficients
- Bézout coefficients are integers and that satisfy .
- Euclidean Algorithm
- The Euclidean Algorithm is a repeated division process used to find efficiently.
- Extended Euclidean Algorithm
- The Extended Euclidean Algorithm finds both and integers and such that .
- Relatively prime
- Two integers and are relatively prime when .
- Modular inverse
- A modular inverse of modulo is a number such that .
Common Mistakes to Avoid
- Stopping before the last nonzero remainder is a mistake because is the last nonzero remainder, not the final remainder .
- Using quotient signs incorrectly during back substitution is wrong because each equation must be rearranged exactly, such as .
- Assuming Bézout coefficients are unique is wrong because if one pair works, infinitely many related pairs can also work.
- Claiming every equation has integer solutions is wrong because solutions exist only when .
- Forgetting to reduce a negative modular inverse is a mistake because an answer like should often be written as .
Practice Questions
- 1 Use the Extended Euclidean Algorithm to find integers and such that .
- 2 Find the modular inverse of modulo using Bézout's Identity.
- 3 Determine whether the equation has integer solutions, and if it does, find one solution.
- 4 Explain why has a modular inverse modulo exactly when .
Understanding Bezout's Identity & Extended Euclidean Algorithm
A useful way to understand why the method works is to study every integer that can be made by taking a multiple of one starting number and adding a multiple of the other. This collection includes negative values, zero, and positive values. Among its positive values, there is a smallest one.
Division shows that this smallest value must divide both starting numbers. It is therefore their greatest common divisor.
This argument explains why a greatest common divisor is not just a result of repeated division. It is the smallest positive amount that can be built from the two numbers using whole-number multiples.
Working backward is valid because each remainder came from an earlier division. For example, if thirty divided by eighteen leaves twelve, then twelve can be written as thirty minus one times eighteen. If eighteen divided by twelve leaves six, then six can be written as eighteen minus one times twelve.
Replacing twelve with its earlier expression writes six using thirty and eighteen. Students often lose signs during this substitution. Parentheses matter.
When a negative multiplier is distributed across a bracket, every term inside changes sign. A clean table of remainders and their coefficients can reduce errors. Start with the first number as one copy of itself and zero copies of the second.
Start with the second number as zero copies of the first and one copy of itself. Update these coefficients at every division step.
The method does more than find one pair of whole-number solutions. It describes a pattern of infinitely many solutions when a target amount is possible. First find one solution.
Then add the second starting number divided by the greatest common divisor to the first unknown, while subtracting the first starting number divided by the greatest common divisor from the second unknown. Repeating that change with any whole-number multiplier gives another solution. This matters in problems about making exact totals with fixed package sizes, arranging equal groups, or finding times that satisfy two repeating schedules.
A solution may exist mathematically but fail a real-world condition. For package counts, negative answers are usually meaningless, so students must choose a solution from the full pattern that makes both counts nonnegative.
Modular inverses are another practical use because they undo multiplication within a repeating remainder system. On a clock-like system with a fixed modulus, multiplying by a number can only be reversed when that number shares no factor with the modulus except one. For instance, a number divisible by two cannot have an inverse in a system whose modulus is even, because its products stay even and can never leave remainder one.
A correct inverse can be checked quickly by multiplying it by the original number and confirming that division by the modulus leaves remainder one. Encryption methods use this same idea with very large integers.
In class, the most important habit is to check the greatest common divisor before searching for an inverse or trying to solve a target equation. That one check tells you whether a solution is possible.