Bézoutova lema

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

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

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

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

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

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

Uvjet relativne prostosti

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

Vanjske poveznice

• Bézoutova lema na Mathworldu (engl.)
• Kalkulator x i y prema Bézoutovoj lemi (engl.)