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

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

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

Perumuman

Untuk tiga bilangan bulat atau lebih

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

Sejarah

Seorang matematikawan berkebangsaan Prancis yang bernama Étienne Bézout membuktikan identitas Bezout untuk polinomial. 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.

Lihat pula

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

Pranala luar

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