Identitas Bézout

Di dasar teori bilangan, Identitas Bézout atau disebut juga Lemma Bézout) adalah sebagai berikut teorema:

Identitas Bézout — Misalkan a dan b menjadi bilangan bulat dengan pembagi persekutuan terbesar d . Kemudian, ada bilangan bulat x dan y seperti bilangan ax + by = d. Lebih umum lagi, bilangan bulat dari formulir ax + by persis kelipatan d.

Bilangan bulat x dan y disebut 'koefisien Bézout' untuk ( a , b ); mereka tidak unik. Sepasang koefisien Bézout dapat dihitung dengan algoritma Euklides diperpanjang. Jika a dan b tidak nol, algoritma Euclidean yang diperluas menghasilkan salah satu dari dua pasangan sedemikian rupa sehingga $|x|\leq \left|{\frac {b}{d}}\right|$ dan $|y|\leq \left|{\frac {a}{d}}\right|$ (kesetaraan dapat terjadi hanya jika salah satu dari a dan b adalah kelipatan dari yang lain).

Banyak teorema lain dalam teori bilangan dasar, seperti lemma Euklidean atau Teorema sisa Cina, dihasilkan dari identitas Bézout.

Struktur solusi

Ketika satu pasang koefisien Bézout $(x, y)$ telah dihitung (misalnya, menggunakan algoritma Euklides diperpanjang), semua pasangan dapat direpresentasikan 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|\quad {\text{and}}\quad |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)$ seperti yang $c = dq + r$ dan $0 < r < | d |$ , dan satu lagi seperti itu $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 Extended Euclidean selalu menghasilkan salah satu dari dua pasangan minimal ini.

Contoh

Misalkan, a = 12 dan b = 42, gcd (12, 42) = 6. Kemudian kita memiliki 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\cdot7, -5+2\cdot2) = (4, -1)$ , dan $(18-3\cdot7, -5+3\cdot2) = (-3, 1)$ . Domain Bézout adalah domain integral tempat memegang identitas Bézout. Secara khusus, identitas Bézout berlaku di domain ideal utama. Setiap teorema yang dihasilkan dari identitas Bézout dengan demikian benar di semua domain ini.

Bukti

Diberikan bilangan bulat bukan nol $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 = \pm1$ dan $y = 0$ ). Karena $S$ adalah himpunan bilangan bulat positif yang tidak kosong, ia memiliki elemen minimum $d=as+bt$ , dengan Prinsip keteraturan. 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 untuk pembagi persekutuan lainnya $c$ termasuk bilangan $c \leq d$ .

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

a=dq+r\quad {\text{dengan}}\quad 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

lalu jika 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 properti 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
Lemma 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]