Identitas Bézout

Halaman ini berisi artikel tentang teorema Bézout dalam aritmetika. Untuk teorema Bézout dalam geometri aljabar, lihat teorema Bézout.

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

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

Bilangan bulat ${\displaystyle x}$ dan ${\displaystyle y}$ disebut koefisien Bézout untuk ${\displaystyle (a,b)}$, dan bilangan-bilangan tersebut tidak tunggal. Sepasang koefisien Bézout dapat dihitung dengan menggunakan algoritma Euklides diperluas (extended Euclidean algorithm). Jika ${\displaystyle a}$ dan ${\displaystyle b}$ tidak nol, algoritma Euklides diperluas menghasilkan salah satu dari dua pasangan sedemikian rupa sehingga ${\displaystyle |x|\leq |b/d|}$ dan ${\displaystyle |y|\leq |a/d|}$. Kesamaan tersebut dapat terjadi hanya jika salah satu dari ${\displaystyle a}$ dan ${\displaystyle 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 ${\displaystyle a}$ dan ${\displaystyle b}$ adalah bukan bilangan tak nol, serta satu buah pasangan koefisien Bézout ${\displaystyle (x,y)}$ telah dihitung (katakanlah dengan menggunakan algoritma Euklides diperluas), maka semua pasangan dapat dinyatakan berikut:$${\displaystyle \left(x-k{\frac {b}{d}},\ y+k{\frac {a}{d}}\right),}$$dengan ${\displaystyle k}$ menyatakan sebarang bilangan bulat, ${\displaystyle d}$ merupakan faktor persekutuan terbesar dari ${\displaystyle a}$ dan ${\displaystyle b}$. Pada bentuk tersebut, pecahan disederhanakan menjadi bilangan bulat. Sebaliknya, jika ${\displaystyle a}$ dan ${\displaystyle 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 ${\displaystyle a}$ dan ${\displaystyle b}$ membagi bilangan lain.

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

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

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

Contoh

Misalkan ${\displaystyle a=12}$ dan ${\displaystyle b=42}$, sehingga ${\displaystyle \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:

${\displaystyle {\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 ${\displaystyle (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 ${\displaystyle k=2}$ dan ${\displaystyle 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 ${\displaystyle a}$ dan ${\displaystyle b}$, dan misalkan ${\displaystyle S=\{ax+by\mid x,y\in \mathbb {Z} {\text{ dan }}ax+by>0\}.}$ Himpunan ${\displaystyle S}$ tidak kosong karena berisi ${\displaystyle a}$ ataupun ${\displaystyle -a}$ (dengan ${\displaystyle x=\pm 1}$ dan ${\displaystyle y=0}$). Karena ${\displaystyle S}$ adalah himpunan bilangan bulat positif takkosong, ${\displaystyle S}$ memiliki anggota minimum ${\displaystyle d=as+bt}$, berdasarkan well-ordering principle. Untuk membuktikan bahwa ${\displaystyle d}$ adalah faktor persekutuan terbesar dari ${\displaystyle a}$ dan ${\displaystyle b}$, maka harus dibuktikan bahwa ${\displaystyle d}$ adalah pembagi persekutuan dari ${\displaystyle a}$ dan ${\displaystyle b}$, dan bahwa untuk sebarang pembagi persekutuan lainnya ${\displaystyle c}$, maka ${\displaystyle c\leq d}$.

Pembagian Euklides dari ${\displaystyle a}$ oleh ${\displaystyle d}$ dapat ditulis ${\displaystyle a=dq+r}$ dengan ${\displaystyle 0\leq r<d}$. Sisa pembagian ${\displaystyle r}$ terdapat di ${\displaystyle S\cup \{0\}}$, sebab$${\displaystyle {\begin{aligned}r&=a-qd\\&=a-q(as+bt)\\&=a(1-qs)-bqt.\end{aligned}}}$$Dengan demikian, ${\displaystyle r}$ adalah bilangan dari bentuk ${\displaystyle ax+by}$, dan karena itu ${\displaystyle r\in S\cup \{0\}}$. Akan tetapi, ${\displaystyle 0\leq r<d}$ dan ${\displaystyle d}$ adalah bilangan bulat positif terkecil di S, maka sisa pembagian ${\displaystyle r}$ tidak terdapat di ${\displaystyle S}$, sehingga mengakibatkan ${\displaystyle r}$ menjadi 0. Maka dari itu, dapat disiratkan bahwa ${\displaystyle d}$ pembagi ${\displaystyle a}$. Dengan cara yang serupa, ${\displaystyle d}$ juga pembagi ${\displaystyle b}$, dan demikian ${\displaystyle d}$ adalah pembagi persekutuan dari ${\displaystyle a}$ dan ${\displaystyle b}$.

Sekarang, misalkan ${\displaystyle c}$ adalah sebarang pembagi persekutuan dari ${\displaystyle a}$ dan ${\displaystyle b}$, dalam artian bahwa akan ada ${\displaystyle u}$ dan ${\displaystyle v}$ sehingga ${\displaystyle a=cu}$ dan ${\displaystyle b=cv}$. Jadi,$${\displaystyle {\begin{aligned}d&=as+bt\\&=cus+cvt\\&=c(us+vt).\end{aligned}}}$$Maka dapat dikatakan bahwa ${\displaystyle c}$ adalah pembagi ${\displaystyle d}$, dan demikian bahwa ${\displaystyle c\leq d}$.

Perumuman

Perumuman untuk tiga bilangan bulat atau lebih

Identitas Bézout dapat diperluas menjadi dua bilangan bulat atau lebih: jika$${\displaystyle \operatorname {FPB} (a_{1},a_{2},\ldots ,a_{n})=d,}$$maka akan terdapat bilangan bulat ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ sehingga ${\displaystyle d=a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}}$ memiliki sifat berikut bahwa ${\displaystyle d}$ adalah bilangan bulat positif terkecil dari bentuk tersebut, serta setiap bilangan dari rumus tersebu merupakan kelipatan ${\displaystyle d}$.

Perumuman untuk polinomial

Artikel utama: Faktor persekutuan terbesar polinomial § Identitas Bézout dan algoritma FPB yang diperluas

Tak selamanya bahwa identitas Bézout berlaku untuk polinomial. Sebagai contoh, ketika mengerjakan gelanggang polinomial bilangan bulat, faktor persekutuan terbesar dari 2x dan x^2 adalah x, tetapi hasil pembagian persekutuan tersebut tidak mempunyai sebarang koefisien bilangan bulat ${\displaystyle p}$ dan ${\displaystyle q}$ yang memenuhi 2xp + x^2q = x.

Sayangnya, identitas Bézout's bekerja untuk polinomial univariat atas lapangan, yang dilakukan dengan cara yang sama untuk bilangan bulat. Koefisien Bézout dan faktor persekutuan terbesar dapat dihitung menggunakan algoritma Euklides diperluas (extended Euclidean algorithm).

Karena akar dari dua polinomial merupakan akar-akar dari faktor persekutuan terbesarnya, identitas Bézout dan teorema dasar aljabar mengimplikasikan hasil berikut: Untuk polinomial univariat f dan g dengan koefisien di suatu lapangan, terdapat polinomiial ${\displaystyle a}$ dan ${\displaystyle b}$ sehingga af + bg = 1 jika dan hanya jika f dan g tidak memiliki akar di sebarang lapangan tertutup secara aljabar (biasanya di lapangan bilangan kompleks).

Perumuman untuk PID

Identitas Bézout tidak hanya berlaku di gelanggang bilangan bulat, tetapi juga berlaku di PID yang lain. PID pada konteks ini berarti principle ideal domain. Jika R adalah PID, a dan b merupakan anggota R, seta d merupakan faktor persekutuan terbesar dari a dan b, maka akan ada anggota x dan y di R sehingga ${\displaystyle ax+by=d.}$ Hal ini dikarenakan bahwa ideal ${\displaystyle Ra+Rb}$ adalah principal dan sama dengan ${\displaystyle Rd.}$

identitas Bézout yang berlaku dalam suatu domain integral disebut domain Bézout.

Sejarah

Seorang matematikawan berkebangsaan Prancis yang bernama Étienne Bézout membuktikan identitas Bezout untuk polinomial.[1] Sayangnya, pernyataan untuk bilangan bulat ini sudah ditemukan dalam karya sebelumnya milik seorang matematikawan berkebangsaan Prancis lainnya yang bernama Claude Gaspard Bachet de Méziriac.[2][3][4]

Lihat pula

• Teorema AF+BG
• Teorema dasar aritmetika
• Lema Euklides

Catatan

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." Masalah ini, yaitu ${\displaystyle ax-by=1}$, adalah kasus istimewa dari persamaan Bézout, persamaan tersebut digunakan oleh Bachet untuk menyelesaikan masalah yang ditemukan di 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. 

Pranala luar

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