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 $hcf(a,b)\mid c$; equivalently, there is some $d$ such that $d\times 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=hcf(a,b)$.

Finally, $a\left(xd\right)+b\left(yd\right)=dhcf(a,b)=c$, as required.

Actually finding the solutions

Suppose $d\times 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 $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.