[summary: Bézout's theorem 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$.]

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$. ([hcf_is_linear_combination Proof]; this [extended_euclidean_algorithm can also be seen] by working through [euclidean_algorithm 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.