# Bézout's theorem

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.

Parents:

- Greatest common divisor
The greatest common divisor of two natural numbers is… the largest number which is a divisor of both. The clue is in the name, really.