Identitas Bézout

Dalam teori bilangan elementer, identitas Bézout, atau disebut juga lema Bézout, menyatakan teorema berikut:

Identitas Bézout — Misalkan $a$ dan $b$ adalah bilangan bulat dengan pembagi persekutuan terbesar $d$ , maka akan ada bilangan bulat $x$ dan $y$ sehingga bilangan $ax+by=d$ . Lebih umumnya lagi, bilangan bulat dengan bentuk $ax+by$ adalah kelipatan dari $d$ .

Bilangan bulat $x$ dan $y$ disebut koefisien Bézout untuk $(a,b)$ , dan bilangan-bilangan tersebut tidak tunggal. Sepasang koefisien Bézout dapat dihitung dengan menggunakan algoritma Euklides diperluas (extended Euclidean algorithm). Jika $a$ dan $b$ tidak nol, algoritma Euklides diperluas menghasilkan salah satu dari dua pasangan sedemikian rupa sehingga $|x|\leq |b/d|$ dan $|y|\leq |a/d|$ . Kesamaan tersebut dapat terjadi hanya jika salah satu dari $a$ dan $b$ adalah kelipatan dari bilangan lain.

Banyak teorema lain dalam teori bilangan dasar, seperti lema Euklides atau teorema sisa Tiongkok, dihasilkan dari identitas Bézout.

Struktur penyelesaian

Jika $a$ dan $b$ adalah bukan bilangan tak nol, serta satu buah pasangan koefisien Bézout $(x,y)$ telah dihitung (katakanlah dengan menggunakan algoritma Euklides diperluas), maka semua pasangan dapat dinyatakan berikut: $\left(x-k{\frac {b}{d}},\ y+k{\frac {a}{d}}\right),$ dengan $k$ menyatakan sebarang bilangan bulat, $d$ merupakan pembagi persekutuan terbesar dari $a$ dan $b$ . Pada bentuk tersebut, pecahan disederhanakan menjadi bilangan bulat. Sebaliknya, jika $a$ dan $b$ adalah bilangan tak nol, maka tepatnya akan ada dua dari pasangan tersebut memenuhi ${\textstyle |x|\leq \left|b/d\right|}$ dan ${\textstyle |y|\leq \left|a/d\right|}$ , dan kesamaan tersebut hanya dapat terjadi jika salah satu dari $a$ dan $b$ membagi bilangan lain.

Solusi ini bergantung pada sifat pembagian Euklides, yang mengatakan sebagai berikut: diberikan dua bilangan bulat $c$ dan $d$ . Jika $d$ tidak membagi $c$ , maka terdapat satu buah pasangan $(q,r)$ sehingga $c=dq+r$ dan $0<r<|d|$ , dan sehingga juga $c=dq+r$ dan $-|d|<r<0$ .

Dua pasangan dari koefisien Bézout kecil diperoleh dari pasangan $(x,y)$ dengan memilih salah satu dari dua bilangan bulat tersebut di dekat ${\textstyle {\frac {x}{b/d}}}$ untuk $k$ di rumus sebelumnya.

Algoritma Euklides diperluas selalu menghasilkan salah satu dari dua pasangan minimal tersebut.

Contoh

Misalkan $a=12$ dan $b=42$ , sehingga $\operatorname {FPB} (12,42)=6$ . Identitas Bézout berikut, dengan koefisien Bézout ditandai dengan warna merah untuk pasangan minimal dan biru untuk pasangan lainnya, ditulis sebagai berikut:

{\begin{aligned}\vdots \\12&\times ({\color {blue}{-10}})&+\;\;42&\times \color {blue}{3}&=6\\12&\times ({\color {red}{-3}})&+\;\;42&\times \color {red}{1}&=6\\12&\times \color {red}{4}&+\;\;42&\times ({\color {red}{-1}})&=6\\12&\times \color {blue}{11}&+\;\;42&\times ({\color {blue}{-3}})&=6\\12&\times \color {blue}{18}&+\;\;42&\times ({\color {blue}{-5}})&=6\\\vdots \end{aligned}}

Jika $(x,y)=(18,-5)$ adalah pasangan asli dari koefisien Bézout ${\textstyle {\frac {18}{42/6}}\in [2,3]}$ , akan menghasilkan pasangan minimal berikut dengan memilih $k=2$ dan $k=3$ , yaitu: ${\textstyle (18-2\cdot 7,-5+2\cdot 2)=(4,-1)}$ , dan ${\textstyle (18-3\cdot 7,-5+3\cdot 2)=(-3,1)}$ .

Bukti

Diberikan bilangan bulat taknol $a$ dan $b$ , misalkan $S=\{ax+by\mid x,y\in \mathbb {Z} {\text{ dan }}ax+by>0\}.$ Himpunan $S$ tidak kosong karena berisi salah satunya $a$ atau $-a$ (dengan $x=\pm 1$ dan $y=0$ ). Karena $S$ adalah himpunan bilangan bulat positif takkosong, ini memiliki unsur minimum $d=as+bt$ , dengan prinsip urutan rapi. Untuk membuktikan bahwa $d$ adalah pembagi persekutuan terbesar dari $a$ dan $b$ , kita harus membuktikan bahwa $d$ adalah pembagi persekutuan dari $a$ dan $b$ , dan bahwa untuk suatu pembagi persekutuan lainnya $c$ termasuk bilangan $c\leq d$ .

Divisi Euklides dari $a$ oleh $d$ boleh ditulis

a=dq+r

dengan

0\leq r<d

.

Sisa $r$ ada di $S\cup \{0\}$ , lantaran

{\begin{aligned}r&=a-qd\\&=a-q(as+bt)\\&=a(1-qs)-bqt.\end{aligned}}

Untuk tiga atau lebih bilangan bulat

Identitas Bézout dapat diperluas menjadi lebih dari dua bilangan bulat: jika

\gcd(a_{1},a_{2},\ldots ,a_{n})=d

maka bilangan bulat $x_{1},x_{2},\ldots ,x_{n}$ seperti yang

d=a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}

memiliki sifat berikut:

$d$ adalah bilangan bulat positif terkecil dari bentuk ini;
setiap angka dari formulir ini adalah kelipatan $d$ .

Sejarah

Matematikawan asal Prancis Étienne Bézout (1730–1783) membuktikan identitas ini untuk polinomial.^[1] Namun, pernyataan untuk bilangan bulat ini sudah dapat ditemukan dalam karya ahli matematika Prancis lainnya, Claude Gaspard Bachet de Méziriac (1581–1638).^[2]^[3]^[4]

Lihat pula

Teorema AF+BG, analog dari identitas Bézout untuk polinomial homogen dalam tiga tak tentu
Teorema dasar aritmetika
Lema Euklidean

Catatan

^ Bézout, É. (1779). Théorie générale des équations algébriques. Paris, France: Ph.-D. Pierres.
^ Tignol, Jean-Pierre (2001). Galois' Theory of Algebraic Equations. Singapore: World Scientific. ISBN 981-02-4541-6.
^ Claude Gaspard Bachet (sieur de Méziriac) (1624). Problèmes plaisants & délectables qui se font par les nombres (edisi ke-2nd). Lyons, France: Pierre Rigaud & Associates. hlm. 18–33. Di halaman-halaman ini, Bachet membuktikan (tanpa persamaan) "Proposisi XVIII. Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d’iceux, surpassant de l’unité un multiple de l’autre." (Mengingat dua bilangan [yang] relatif prima, temukan kelipatan terendah dari masing-masing [sedemikian rupa sehingga] satu kelipatan melebihi yang lain dengan satu kesatuan (1).) Masalah ini (yaitu, ax - by = 1) adalah kasus khusus persamaan Bézout dan digunakan oleh Bachet untuk menyelesaikan masalah yang muncul pada halaman 199 ff.
^ See also: Maarten Bullynck (February 2009). "Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany" (PDF). Historia Mathematica. 36 (1): 48–72. doi:10.1016/j.hm.2008.08.009.

Pranala luar

Online calculator for Bézout's identity.
Weisstein, Eric W. "Bézout's Identity". MathWorld.

[1] Bézout, É. (1779). Théorie générale des équations algébriques. Paris, France: Ph.-D. Pierres.

[2] Tignol, Jean-Pierre (2001). Galois' Theory of Algebraic Equations. Singapore: World Scientific. ISBN 981-02-4541-6.

[3] Claude Gaspard Bachet (sieur de Méziriac) (1624). Problèmes plaisants & délectables qui se font par les nombres (edisi ke-2nd). Lyons, France: Pierre Rigaud & Associates. hlm. 18–33. Di halaman-halaman ini, Bachet membuktikan (tanpa persamaan) "Proposisi XVIII. Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d’iceux, surpassant de l’unité un multiple de l’autre." (Mengingat dua bilangan [yang] relatif prima, temukan kelipatan terendah dari masing-masing [sedemikian rupa sehingga] satu kelipatan melebihi yang lain dengan satu kesatuan (1).) Masalah ini (yaitu, ax - by = 1) adalah kasus khusus persamaan Bézout dan digunakan oleh Bachet untuk menyelesaikan masalah yang muncul pada halaman 199 ff.

[4] See also: Maarten Bullynck (February 2009). "Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany" (PDF). Historia Mathematica. 36 (1): 48–72. doi:10.1016/j.hm.2008.08.009.

[1]

[2]

[3]

[4]