From a gcd to a set of attainable values
Fix integers that are not both zero. The positive greatest common divisor divides both numbers. Hence every integer combination is divisible by . This is a necessary condition for the equation to have an integer solution: if , there is no solution. The surprising fact is that this elementary obstruction is the only one.
Definition 3.5.1
(Greatest common divisor and Bézout certificate)
For integers not both zero, is the largest positive integer dividing both. A Bézout certificate for it is a pair of integers with .
Theorem 3.5.2
(Bézout's identity and the attainable values)
If are not both zero and , there are integers with , and
Proof
(The least positive combination is the gcd)
At least one of is nonzero, so by changing its sign if necessary there is a positive integer combination. Let be the least positive combination. Divide by : , where . Because both and are integer combinations of , so is . If , it contradicts the minimality of ; hence . The same argument proves . Every common divisor of divides every integer combination, in particular . Therefore , and its construction is a Bézout identity.
For the set equality, every combination is divisible by . Conversely, if for an integer , multiplying by gives .
The division algorithm is a prerequisite here, not a conclusion secretly assumed for negative remainders. Its convention ensures that a nonzero remainder is a smaller positive combination. The set equality states both directions. It does not say that an arbitrary combination equals the gcd, nor that Bézout coefficients are unique.
Every solution, not just one
Theorem 3.5.3
(The complete integer solution family)
Let be not both zero, , and suppose . Let be one integer solution of and put , . Then , and all integer solutions are
Proof
(Substitute, then subtract)
Substitution proves every displayed pair works. For the converse, let another solution be and write , . Subtraction gives .
If , then . Coprimality and Bézout's identity imply : if , multiplying by expresses as a sum of multiples of . Write . The equation gives , so cancellation yields . If , then and the equation forces ; any integer has the form for some integer . Thus the same formula also covers this zero-coefficient case. The proof includes negative coefficients, with divisibility interpreted in the integers.
Proof X-ray
Where coprimality enters the family proof
The argument has one real idea: after dividing by , the coefficients are coprime, and coprimality is exactly what turns into . Everything before that is bookkeeping, since subtracting two solutions removes the right-hand side and leaves a homogeneous equation . Bézout's identity is used a second time here, for , to write and so move the divisibility from a product to a single factor. The final cancellation of is legitimate because , and the case is not a degenerate afterthought: it is handled separately because the cancellation would be illegal. Without the division by the argument would only give with no way to remove , which is why the step size in the solution family is and not .
If , our positive gcd convention does not apply. The equation is instead : every integer pair is a solution when , and no pair is a solution when . This case must be considered separately rather than dividing by a zero gcd.
Counterexample mode
The step sizes are the coefficients divided by the gcd, not the coefficients themselves
Claim: if solves , all solutions are , . Test it on with , which works because . The pair is also a solution: and , and . But is not a multiple of , so the claim misses it. The correct step sizes are and : with , and . The repair is to divide by the gcd first.
The explorer below runs the extended Euclidean algorithm for chosen a, b and c, lists the solution family , with each member checked, and shows where any pair you enter falls in it.
Common mistake
(Keeping the old modulus after dividing a congruence)
When dividing by the common factor , the modulus must also be divided: the result is , not . Retaining modulus after division would be wrong; it would reject the solution that works in the original congruence (), since and .
Worked examples
Worked example 3.5.4
(From Euclid to the full solution family)
Solve over the integers, giving a Bézout certificate and proving the list is complete.
Repeated division gives
The last nonzero remainder is . Back-substitution yields
Thus and one solution is . Since and , the complete family is
Substitution cancels the parameter terms; the preceding theorem proves no other solutions exist.
Worked example 3.5.5
(An impossible equation and a solvable congruence)
Explain why has no integer solution. Then find all integers satisfying .
, because , , and . Every is divisible by six, but seven is not; thus the equation is impossible.
The congruence means , or equivalently for some integer . Dividing the congruence by the common factor six is legitimate here and gives . Since and , multiplication by three yields . Conversely, if , then is divisible by . Hence all solutions are , .
Worked example 3.5.6
(A zero coefficient)
Solve over the integers. Here , , so , which divides . One solution is . With and the family is , . So every solution has and arbitrary. Directly, forces and places no condition on , so the formula agrees. Using the unreduced step for would restrict to multiples of and miss the solution , since .
Exercises
Quick check
(Does have an integer solution?)
Compute the gcd of the coefficients.
Solution · Answer
, and . Every value is a multiple of , so there is no integer solution.
Quick check
(Find all integer solutions of .)
Find a Bézout certificate for first, then scale.
Solution · Answer
, so multiplying by gives and . With , , the solutions are , , . Check with : , , and .
Quick check
(Find all integers with .)
Write the congruence as for an integer .
Solution · Answer
Dividing by gives , so . The solutions are ; for instance gives . The modulus changed from to on division.