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.