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.