Bézout's identity 2026-10-13
For integers not both zero, there are integers such that . The extended Euclidean algorithm constructs them. For example, and ; the second identity also gives the modular inverse of modulo .
The identity converts a greatest common divisor into a solvability certificate. The linear Diophantine equation is solvable in integers precisely when divides . Every common divisor divides any integer linear combination; conversely, multiplying a Bézout identity by constructs a solution when that quotient is integral. The coefficients generally are not unique, as the description of all solutions of a linear Diophantine equation makes explicit.
Linear Diophantine equation Created 2026-09-24 Updated 2026-11-05
A linear Diophantine equation in two variables is with integer coefficients and unknown integers . Assume are not both zero, and put .
The linear Diophantine equation solvability criterion gives a solution exactly when : every integer linear combination is divisible by , and Bézout's identity supplies a combination equal to which can be multiplied by . The extended Euclidean algorithm constructs the coefficients. All solutions of a linear Diophantine equation then describes the complete one-parameter family when both coefficients are nonzero.
For example, has , and all its solutions are , with . There is no solution with both coordinates nonnegative, since those inequalities require and . Thus an integer-solvability test does not automatically settle a problem requiring nonnegative integers. If both coefficients are zero, the separate equation has every integer pair as a solution when , and none otherwise.
Past exam of the mathematics course of the University of Cambridge 2014 ia Paper 4 1E Solution Created 2026-09-24 Updated 2026-10-06
The Euclidean algorithm givesThus the greatest common divisor is . The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with , .
To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by . The result is . Since and are coprime integers, divides , givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.
For the modular arithmetic calculation, , so is the modular inverse of . Multiplication gives . The admissible integers are for , ending at ; the next is . There are such integers.
Back-substitute in the Euclidean algorithm to obtain an integer linear combination:Multiplying by gives the particular solution of the linear Diophantine equation. Subtracting it from any other solution and dividing by givesThe integers and are coprime, so divides . Writing forces . Conversely these expressions satisfy the original equation for every integer . Thus all solutions of a linear Diophantine equation here are