Bézout’s theorem is an important basic theorem of number theory. It states that if \(a\) and \(b\) are integers, and \(c\) is an integer, then the equation \(ax+by = c\) has integer solutions in \(x\) and \(y\) if and only if the greatest common divisor of \(a\) and \(b\) divides \(c\).

Proof

We have two directions of the equivalence to prove.

If \(ax+by=c\) has solutions

Suppose \(ax+by=c\) has solutions in \(x\) and \(y\). Then the highest common factor of \(a\) and \(b\) divides \(a\) and \(b\), so it divides \(ax\) and \(by\); hence it divides their sum, and hence \(c\).

If the highest common factor divides \(c\)

Suppose \(\mathrm{hcf}(a,b) \mid c\); equivalently, there is some \(d\) such that \(d \times \mathrm{hcf}(a,b) = c\).

We have the following fact: that the highest common factor is a linear combination of \(a, b\). (Proof; this can also be seen by working through Euclid’s algorithm.)

Therefore there are \(x\) and \(y\) such that \(ax + by = \mathrm{hcf}(a,b)\).

Finally, \(a (xd) + b (yd) = d \mathrm{hcf}(a, b) = c\), as required.

Actually finding the solutions

Suppose \(d \times \mathrm{hcf}(a,b) = c\), as above.

The extended euclidean algorithm can be used (efficiently!) to obtain a linear combination \(ax+by\) of \(a\) and \(b\) which equals \(\mathrm{hcf}(a,b)\). Once we have found such a linear combination, the solutions to the integer equation \(ax+by=c\) follow quickly by just multiplying through by \(d\).

Importance

Bézout’s theorem is important as a step towards the proof of Euclid’s lemma, which itself is the key behind the Fundamental Theorem of Arithmetic. It also holds in general principal ideal domains.