Bézoutova lema

Bézoutova lema ili Bézoutov identitet je jedan od najvažnijih rezultata u elementarnoj teoriji brojeva. Lema tvrdi:

Neka su $a,b$ cijeli brojevi i neka je $d$ najveća zajednička mjera brojeva $a,b.$ Tada postoje $x,y\in \mathbb{Z}$ takvi da je $ax+by=d.$ Uz to, vrijedi $d=M(a,b).$

Iako se lema zove po francuskom matematičaru Étienne Bézoutu (1730. – 1783.), ovu je tvrdnju u svom radu ranije iskazao drugi francuski matematičar, Claude Gaspard Bachet de Méziriac (1581. – 1638.).

Dokaz

Promotrimo skup $S=\{ax+by|x,y\in \mathbb{Z},ax+by>0\}.$ Uočimo da su $a,b\in S.$ Dakle, $S$ nije neprazan skup. Prema svojstvu dobre uređenosti prirodnih brojeva postoji najmanji element skupa $S.$ Prema tome, neka je $d$ najmanji član od $S.$ To znači da ga možemo zapisati kao $d=ak+bl,k,l\in \mathbb{Z}.$ (1)

Dokaz ćemo da $d\mid a,d\mid b,$ ali i da je $d=M(a,b).$ Pretpostavimo bez smanjenja općenitosti (BSO) da $d\nmid a.$ Prema teoremu o dijeljenju s ostatkom možemo pisati $a=dq+r,q\in \mathbb{Z},r=\{1,2,...,d-1\}.$ Dobivamo $r=a-dq.$ Koristeći (1) dobivamo $r=a(1-kq)+b(-ql),$ što znači $r\in S$. No, $0<r<d,$ što je kontradikcija jer je $d=\min S.$ Dakle, $d\mid a$ i analogno $d\mid b.$

Još valja dokazati da je $d=M(a,b).$ Pretpostavimo da $c\mid a,b$ i BSO $c>0.$ Dakle vrijedi $a=cs,b=ct,s,t\in \mathbb{N}.$ Znamo da je $d=ka+lb$ pa je preko gornjih jednakosti $d=c(ks+lt).$ Vidimo da $c\mid d$ pa je zaista $d=M(a,b)$ čime je lema dokazana.

Dokaz je moguće zorno pokazati i primjenom Euklidovog algoritma.

Uvjet relativne prostosti

Iz dokaza se vidi da kada je $ax+by=1$ slijedi $M(a,b)=1$ i obrnuto, kada su $a,b$ relativno prosti mora biti $ax+by=1$ za neke $x,y\in \mathbb{Z}.$

Vanjske poveznice

• Bézoutova lema na Mathworldu Predložak:Eng oznaka
• Kalkulator x i y prema Bézoutovoj lemi Predložak:Eng oznaka