Bézout's theorem is an important basic theorem of number theory. It states that if and $b$ are integers, and $c$ is an integer, then the equation $a x + b y = 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 $a x + b y = c$ has solutions

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

If the highest common factor divides $c$

Suppose $h c f (a, b) ∣ c$ ; equivalently, there is some $d$ such that $d \times h c f (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 $a x + b y = h c f (a, b)$ .

Finally, $a (x d) + b (y d) = d h c f (a, b) = c$ , as required.

Actually finding the solutions

Suppose $d \times h c f (a, b) = c$ , as above.

The extended_euclidean_algorithm can be used (efficiently!) to obtain a linear combination $a x + b y$ of $a$ and $b$ which equals $h c f (a, b)$ . Once we have found such a linear combination, the solutions to the integer equation $a x + b y = 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.