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|$ . Kesetaraan 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$ tidaknol dan satu pasang koefisien Bézout $(x,y)$ telah dihitung (misalnya, menggunakan algoritma Euklides diperluas), semua pasangan dapat diwakilkan dalam bentuk

\left(x-k{\frac {b}{\gcd(a,b)}},\ y+k{\frac {a}{\gcd(a,b)}}\right)

,

di mana $k$ adalah bilangan bulat sembarang dan pecahan disederhanakan menjadi bilangan bulat.

Di antara pasangan koefisien Bézout ini, tepat dua di antaranya memuaskan

|x|\leq \left|{\frac {b}{\gcd(a,b)}}\right|

dan

|y|\leq \left|{\frac {a}{\gcd(a,b)}}\right|

dan kesetaraan hanya dapat terjadi jika salah satu dari $a$ dan $b$ membagi yang lain.

Ini bergantung pada properti Divisi Euclidean: diberikan dua bilangan bulat $c$ dan $d$ , jika $d$ tidak membagi $c$ , maka terdapat tepat satu pasang $(q,r)$ sehingga $c=dq+r$ dan $0<r<|d|$ , dan ada lagi sehingga $c=dq+r$ dan $-|d|<r<0$ .

Dua pasang koefisien Bézout kecil diperoleh dari koefisien yang diberikan $(x,y)$ dengan memilih untuk $k$ dalam rumus di atas salah satu dari dua bilangan bulat di sebelahnya ${\frac {x}{b/\gcd(a,b)}}$ .

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

Contoh

Misalkan, $a=12$ dan $b=42$ , $\gcd(12,42)=6$ . Kemudian identitas Bézout berikut, dengan koefisien Bézout ditulis dengan warna merah untuk pasangan minimal dan biru untuk pasangan lainnya.

{\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 ${\frac {18}{42/6}}\in [2,3]$ menghasilkan pasangan minimal melalui $k=2$ , masing-masing $k=3$ : $(18-2\cdot 7,-5+2\cdot 2)=(4,-1)$ , dan $(18-3\cdot 7,-5+3\cdot 2)=(-3,1)$ . Ranah Bézout adalah ranah integral tempat memegang identitas Bézout. Secara khusus, identitas Bézout berlaku di ranah ideal utama. Setiap teorema yang dihasilkan dari identitas Bézout dengan demikian benar di semua ranah ini.

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]