Bézout's theorem

Bé­zout’s the­o­rem is an im­por­tant ba­sic the­o­rem of num­ber the­ory. It states that if $$a$$ and $$b$$ are in­te­gers, and $$c$$ is an in­te­ger, then the equa­tion $$ax+by = c$$ has in­te­ger solu­tions in $$x$$ and $$y$$ if and only if the great­est com­mon di­vi­sor of $$a$$ and $$b$$ di­vides $$c$$.

Proof

We have two di­rec­tions of the equiv­alence to prove.

If $$ax+by=c$$ has solutions

Sup­pose $$ax+by=c$$ has solu­tions in $$x$$ and $$y$$. Then the high­est com­mon fac­tor of $$a$$ and $$b$$ di­vides $$a$$ and $$b$$, so it di­vides $$ax$$ and $$by$$; hence it di­vides their sum, and hence $$c$$.

If the high­est com­mon fac­tor di­vides $$c$$

Sup­pose $$\mathrm{hcf}(a,b) \mid c$$; equiv­a­lently, there is some $$d$$ such that $$d \times \mathrm{hcf}(a,b) = c$$.

We have the fol­low­ing fact: that the high­est com­mon fac­tor is a lin­ear com­bi­na­tion of $$a, b$$. (Proof; this can also be seen by work­ing through Eu­clid’s al­gorithm.)

There­fore there are $$x$$ and $$y$$ such that $$ax + by = \mathrm{hcf}(a,b)$$.

Fi­nally, $$a (xd) + b (yd) = d \mathrm{hcf}(a, b) = c$$, as re­quired.

Ac­tu­ally find­ing the solutions

Sup­pose $$d \times \mathrm{hcf}(a,b) = c$$, as above.

The ex­tended eu­clidean al­gorithm can be used (effi­ciently!) to ob­tain a lin­ear com­bi­na­tion $$ax+by$$ of $$a$$ and $$b$$ which equals $$\mathrm{hcf}(a,b)$$. Once we have found such a lin­ear com­bi­na­tion, the solu­tions to the in­te­ger equa­tion $$ax+by=c$$ fol­low quickly by just mul­ti­ply­ing through by $$d$$.

Importance

Bé­zout’s the­o­rem is im­por­tant as a step to­wards the proof of Eu­clid’s lemma, which it­self is the key be­hind the Fun­da­men­tal The­o­rem of Arith­metic. It also holds in gen­eral prin­ci­pal ideal do­mains.

Parents:

• Greatest common divisor

The great­est com­mon di­vi­sor of two nat­u­ral num­bers is… the largest num­ber which is a di­vi­sor of both. The clue is in the name, re­ally.