Identitas Bézout

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

Dalam matematika, identitas Bézout (atau disebut juga lema Bézout) adalah teorema yang menghubungkan antara sembarang dua bilangan bulat dengan faktor persekutuan terbesarnya, yang dinyatakan sebagai berikut:

Identitas Bézout — Diberikan dua bilangan bulat $a$ dan $b$ dengan faktor persekutuan terbesar $\operatorname {FPB} \!\left(a,\,b\right)$, maka terdapat suatu bilangan bulat $m$ dan $n$ sedemikian sehingga berlaku $$am+bn=\operatorname {FPB} \!\left(a,\,b\right)$$ Lebih lanjut, setiap bilangan bulat dengan bentuk $ap+bq$ merupakan kelipatan dari $\operatorname {FPB} \!\left(a,\,b\right)$.

Dalam identitas ini, faktor persekutuan terbesar dari $0$ dan $0$ didefinisikan sama dengan $0$. Bilangan bulat $p$ dan $q$ disebut sebagai koefisien Bézout dari $(a,\,b)$, dan nilai $p$ serta $q$ tidak tunggal. Sepasang koefisien Bézout dapat dicari menggunakan algoritma Euklides diperluas, yang menghasilkan salah satu dari dua pasang koefisien Bézout yang memenuhi pertidaksaman $$\left|p\right|\leq \left|{\dfrac {b}{\operatorname {FPB} \!\left(a,\,b\right)}}\right|\qquad \qquad \left|q\right|\leq \left|{\dfrac {a}{\operatorname {FPB} \!\left(a,\,b\right)}}\right|$$ Pertidaksamaan tersebut akan berubah menjadi persamaan hanya jika $a$ dan $b$ atau $b$ saling berkelipatan, yang berarti bahwa setidaknya salah satu dari "$a$ merupakan kelipatan dari $b$" atau "$b$ merupakan kelipatan dari $a$" bernilai benar.

Sebagai contoh, faktor persekutuan terbesar dari 15 dan 69 ialah 3, dan 3 dapat dinyatakan sebagai kombinasi dari 15 dan 69, yaitu $3=15\cdot (-9)+69\cdot 2$, dengan koefisien Bézout −9 dan 2.

Banyak teorema lain dalam teori bilangan dasar merupakan hasil dari identitas Bézout, seperti lema Euclid atau teorema sisa Tiongkok.

Daerah Bézout adalah daerah integral yang berlaku identitas Bézout. Oleh karena setiap daerah ideal utama merupakan daerah Bézout, maka setiap teorema yang dihasilkan dari identitas Bézout akan berlaku untuk setiap daerah ideal utama.

Struktur penyelesaian

Jika $a$ dan $b$ keduanya tidak bernilai nol, serta satu pasang koefisien Bézout $(p,\,q)$ telah ditemukan (misalnya dengan menggunakan algoritma Euklides diperluas), maka setiap pasang koefisien Bézout memiliki bentuk umum $$\left(p-k\cdot {\dfrac {b}{\operatorname {FPB} (a,\,b)}},\,q+k\cdot {\dfrac {a}{\operatorname {FPB} (a,\,b)}}\right)$$ dengan $k$ adalah sembarang bilangan bulat. Perhatikan bahwa pecahan ${\dfrac {a}{\operatorname {FPB} (a,\,b)}}$ dan ${\dfrac {b}{\operatorname {FPB} (a,\,b)}}$ merupakan bilangan bulat, berdasarkan definisi dari faktor persekutuan terbesar.

Jika $a$ dan $b$ keduanya tidak bernilai nol dan keduanya tidak saling berkelipatan, maka terdapat tepat dua pasang koefisien Bézout yang memenuhi pertidaksamaan $$\left|p\right|\leq \left|{\dfrac {b}{\operatorname {FPB} \!\left(a,\,b\right)}}\right|\qquad \qquad \left|q\right|\leq \left|{\dfrac {a}{\operatorname {FPB} \!\left(a,\,b\right)}}\right|$$ Jika $a$ dan $b$ keduanya bernilai positif, maka salah satu pasang koefisien Bézout ini akan memiliki nilai $p>0$ dan $q<0$, dan pasangan lainnya akan memiliki nilai $p<0$ dan $q>0$. Jika $a>0$ habis membagi $b$ (termasuk kasus $b=0$), maka salah satu dari koefisien Bézoutnya ialah $(1,\,0)$.

Bukti dari batas atas tersebut memanfaatkan sifat pembagian bersisa: diberikan dua bilangan bulat tak nol $c$ dan $d$. Jika $d$ tidak habis membagi $c$, maka

1. terdapat tepat satu pasang bilangan bulat $(q,\,r)$ sedemikian sehingga $c=dq+r$ dengan $0<r<|d|$, dan
2. terdapat tepat satu pasang bilangan bulat $(q',\,r')$ sedemikian sehingga $c=dq'+r'$ dengan $-|d|<r'<0$.

Bukti batas koefisien

Misalkan $x$ dan $y$ merupakan penyelesaian dari identitas Bézout $$ax+by=\operatorname {FPB} (a,\,b)$$ dengan $ab\neq 0$. Telah diketahui sebelumnya bahwa bentuk umum dari setiap koefisien Bézout ialah $${\begin{aligned}p&=x-k\cdot {\dfrac {b}{\operatorname {FPB} (a,\,b)}}\\q&=y+k\cdot {\dfrac {a}{\operatorname {FPB} (a,\,b)}}\end{aligned}}$$ dengan $k\in \mathbb {Z}$. Akan ditunjukkan bahwa terdapat suatu nilai $k$ sedemikian sehingga $$\left|p\right|\leq \left|{\dfrac {b}{\operatorname {FPB} \!\left(a,\,b\right)}}\right|\qquad \qquad \left|q\right|\leq \left|{\dfrac {a}{\operatorname {FPB} \!\left(a,\,b\right)}}\right|$$ Didefinisikan $A={\tfrac {a}{\operatorname {FPB} (a,\,b)}}$ dan $B={\tfrac {b}{\operatorname {FPB} (a,\,b)}}$. Berdasarkan sifat pembagian bersisa, maka terdapat suatu pasangan bilangan bulat $(h,\,s)$ sedemikian sehingga $x$ dapat dinyatakan sebagai $$x=hB+s$$ dengan $0\leq s<|B|$. Akibatnya, $${\begin{aligned}p&=x-k\cdot {\dfrac {b}{\operatorname {FPB} (a,\,b)}}\\&=hB+s-kB\\&=s+(h-k)B\end{aligned}}$$ Dengan argumentasi serupa, maka berdasarkan sifat pembagian bersisa, terdapat suatu pasangan bilangan bulat $(h',\,s')$ sedemikian sehingga $y$ dapat dinyatakan sebagai $$y=h'A+s'$$ dengan $-|A|<s'\leq 0$. Akibatnya, $${\begin{aligned}q&=y+k\cdot {\dfrac {a}{\operatorname {FPB} (a,\,b)}}\\&=h'A+s'+kA\\&=s'+(h'+k)A\end{aligned}}$$ Oleh karena $x$ dan $y$ merupakan penyelesaian dari identitas Bézout $ax+by=\operatorname {FPB} (a,\,b)$, maka $${\begin{aligned}\operatorname {FPB} (a,\,b)&=ax+by\\&=a(hB+s)+b(h'A+s')\\&=a\left(h\cdot {\dfrac {b}{\operatorname {FPB} (a,\,b)}}+s\right)+b\left(h'\cdot {\dfrac {a}{\operatorname {FPB} (a,\,b)}}+s'\right)\\&={\dfrac {ab}{\operatorname {FPB} (a,\,b)}}\left(h+h'\right)+as+bs'\end{aligned}}$$ Berdasarkan persamaan $s=x-hB$ dan $s'=y-h'B$, maka $s$ dan $s'$ merupakan koefisien Bézout dari $(a,\,b)$. Dengan kata lain, $${\begin{aligned}as+bs'&=\operatorname {FPB} (a,\,b)\\as+bs'&={\dfrac {ab}{\operatorname {FPB} (a,\,b)}}\left(h+h'\right)+as+bs'\\0&={\dfrac {ab}{\operatorname {FPB} (a,\,b)}}\left(h+h'\right)\\0&=h+h'\\h'&=-h\end{aligned}}$$ Akibatnya, diperoleh $${\begin{aligned}p&=s+(h-k)B\\q&=s'+(h'+k)A\\&=s'-(h-k)A\end{aligned}}$$ sehingga dengan memilih $k=h$, maka $p=s$ dan $q=s'$. Berdasarkan batas dari $s$ dan $s'$, maka $${\begin{aligned}0\leq s&<|B|\\|s|&<|B|\\|p|&<\left|{\dfrac {b}{\operatorname {FPB} (a,\,b)}}\right|\\\\-|A|<s'&\leq 0\\|s'|&<|A|\\|q|&<\left|{\dfrac {a}{\operatorname {FPB} (a,\,b)}}\right|\end{aligned}}$$ Pasangan koefisien Bézout lainnya dapat diperoleh dengan memilih $k=h+1$. Pada kasus $a\neq 0$ dan $b=0$, maka koefisien Bézout dapat dipilih $p={\tfrac {a}{|a|}}$ dan $q=0$, sedangkan pada kasus $a=0$ dan $b\neq 0$, maka koefisien Bézout dapat dipilih $p=0$ dan $q={\tfrac {b}{|b|}}$.

Jika suatu pasang koefisien Bézout $x$ dan $y$ dari $(a,\,b)$ telah diperoleh, maka dua pasangan koefisien Bézout minimal tersebut dapat diperoleh dengan memilih nilai $k$ pada rumus sebelumnya sebagai salah satu dari dua bilangan bulat terdekat dari $x\cdot {\tfrac {\operatorname {FPB} (a,\,b)}{b}}$, yaitu $k=\left\lfloor x\cdot {\tfrac {\operatorname {FPB} (a,\,b)}{b}}\right\rfloor$ atau $k=\left\lceil x\cdot {\tfrac {\operatorname {FPB} (a,\,b)}{b}}\right\rceil$, dengan $\lfloor \cdot \rfloor$ menyatakan fungsi lantai dan $\lceil \cdot \rceil$ menyatakan fungsi atap.

Algoritma Euklides diperluas selalu menghasilkan salah satu dari dua pasangan koefisien Bézout minimal tersebut.

Contoh

Misalkan $a=12$ dan $b=42$, maka diperoleh $\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{array}{rccccccl}&&\vdots \\12&\cdot &({\color {blue}{-17}})&+&42&\cdot &\color {blue}{5}&=6\\12&\cdot &({\color {blue}{-10}})&+&42&\cdot &\color {blue}{3}&=6\\12&\cdot &({\color {red}{-3}})&+&42&\cdot &\color {red}{1}&=6\\12&\cdot &\color {red}{4}&+&42&\cdot &({\color {red}{-1}})&=6\\12&\cdot &\color {blue}{11}&+&42&\cdot &({\color {blue}{-3}})&=6\\12&\cdot &\color {blue}{18}&+&42&\cdot &({\color {blue}{-5}})&=6\\&&\vdots \end{array}}$$

Perhatikan bahwa ${\tfrac {18}{42/6}}\in \left[2,\,3\right]$. Jika $(x,\,y)=(18,\,-5)$ adalah pasangan asli dari koefisien Bézout, maka pasangan koefisien Bézout minimalnya dapat diperoleh dengan memilih $k=2$ atau $k=3$, yaitu $(18-2\cdot 7,\,-5+2\cdot 2)=(4,\,-1)$ atau $(18-3\cdot 7,\,-5+3\cdot 2)=(-3,\,1)$.

Bukti

Diambil sembarang dua bilangan bulat tak nol $a$ dan $b$, dan didefinisikan himpunan $H=\left\{ap+bq\mid p,\,q\in \mathbb {Z} \right\}\cap \mathbb {N}$ Himpunan $H$ tidak kosong, sebab salah satu dari $a$ ataupun $-a$ merupakan anggota dari $H$ (dengan $p=\pm 1$ dan $q=0$). Oleh karena $H$ merupakan himpunan bagian dari bilangan asli yang tak kosong, maka berdasarkan prinsip urutan rapi, himpunan $H$ memiliki elemen terkecil, yaitu $d=ax+by$. Untuk membuktikan bahwa $d$ merupakan faktor persekutuan terbesar dari $a$ dan $b$, maka

1. harus dibuktikan bahwa $d$ merupakan faktor persekutuan dari $a$ dan $b$, dan
2. untuk sebarang faktor persekutuan lainnya $c$, maka berlaku $c\leq d$.

Pembagian bersisa dari $a$ oleh $d$ dapat dinyatakan sebagai $$a=k\cdot d+s$$ dengan $0\leq s<d$. Perhatikan bahwa $${\begin{aligned}a&=kd+s\\s&=a-kd\\&=a-k(ax+by)\\&=a-akx+bky\\&=a(1-kx)-b(ky)\end{aligned}}$$ Berdasarkan persamaan di atas, maka$s$ merupakan bilangan dengan bentuk umum $ap+bq$, sehingga $s\in H\cup \left\{0\right\}$. Oleh karena $0\leq s<d$ dan $d$ adalah bilangan asli terkecil pada himpunan $H$, maka $s\not \in H$, yang membuat nilai $s$ menjadi 0. Akibatnya, $d$ merupakan faktor dari $a$. Dengan cara yang serupa, maka $d$ juga faktor dari $b$, sehingga $d$ adalah faktor persekutuan dari $a$ dan $b$.

Diambil sebarang faktor persekutuan dari $a$ dan $b$, sebut saja $c$. Berdasarkan definisi dari faktor bilangan, maka terdapat suatu bilangan bulat $a'$ dan $b$ sedemikian sehingga $a=ca'$ dan $b=cb'$. Perhatikan bahwa $${\begin{aligned}d&=ax+by\\&=(ca')x+(cb')y\\&=c(a'x+b'y)\end{aligned}}$$ yang menunjukkan bahwa $c$ habis membagi $d$. Oleh karena $d>0$, maka berlaku $c\leq d$.

Perumuman

Perumuman untuk tiga (atau lebih) bilangan bulat

Identitas Bézout dapat diperumum untuk lebih dari dua bilangan bulat:

Perumuman identitas Bézout — Diberikan bilangan bulat $a_{1}$, $a_{2}$, $a_{3}$, $\ldots$, $a_{k}$, maka terdapat suatu bilangan bulat $n_{1}$, $n_{2}$, $n_{3}$, $\ldots$, $n_{k}$ sedemikian sehingga berlaku $$a_{1}n_{1}+a_{2}n_{2}+a_{3}n_{3}+\ldots +a_{k}n_{k}=\operatorname {FPB} (a_{1},\,a_{2},\,a_{3},\,\ldots ,\,a_{k})$$ Lebih lanjut,

1. $\operatorname {FPB} (a_{1},\,a_{2},\,a_{3},\,\ldots ,\,a_{k})$ merupakan bilangan asli terkecil yang memiliki bentuk tersebut.
2. setiap bilangan bulat dengan bentuk $a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}+\ldots +a_{k}x_{k}$ merupakan kelipatan dari $\operatorname {FPB} (a_{1},\,a_{2},\,a_{3},\,\ldots ,\,a_{k})$.

Perumuman untuk polinomial

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

Identitas Bézout tidak selalu berlaku untuk polinomial. Sebagai contoh, dalam gelanggang polinomial dengan koefisien bilangan bulat, perhatikan bahwa faktor persekutuan terbesar dari $3x$ dan $x^{2}$ ialah $x$. Namun, tidak ada polinomial dengan koefisien bilangan bulat $p(x)$ dan $q(x)$ yang memenuhi $$3x\cdot p(x)+x^{2}\cdot q(x)=x$$

Untungnya, identitas Bézout tetap berlaku untuk polinomial univariat atas lapangan, persis seperti pada himpunan bilangan bulat. Koefisien Bézout dan faktor persekutuan terbesar dapat dicari dengan menggunakan algoritma Euklides diperluas.

Oleh karena akar-akar persekutuan dari dua polinomial merupakan akar-akar dari faktor persekutuan terbesar dari kedua polinomial tersebut, maka identitas Bézout dan teorema dasar aljabar mengakibatkan hasil berikut:

Identitas Bézout pada polinomial — Diberikan polinomial univariat $a(x)$ dan $b(x)$ atas suatu lapangan. Terdapat suatu polinomial univariat $f(x)$ dan $g(x)$ sedemikian sehingga $$a(x)\cdot f(x)+b(x)\cdot g(x)=1$$ jika dan hanya jika $f(x)$ dan $g(x)$ tidak memiliki akar persekutuan pada setiap lapangan tertutup aljabar (umumnya lapangan bilangan kompleks).

Perumuman dari hasil ini untuk sembarang banyaknya polinomial dengan sembarang banyaknya variabel ialah Nullstellensatz Hilbert.

Perumuman untuk daerah ideal utama

Seperti yang telah disinggung pada bagian pengantar dari artikel ini, identitas Bézout tidak hanya berlaku pada gelanggang bilangan bulat, tetapi pada sembarang daerah ideal utama.

Identitas Bézout pada daerah ideal utama — Diberikan daerah ideal utama $R$, maka untuk sembarang $a$, $b\in R$, terdapat suatu elemen $x$, $y\in R$ sedemikian sehingga $$ax+by=\operatorname {FPB} (a,\,b)$$ Hal ini dimungkinkan sebab ideal $Ra+Rb$ merupakan ideal utama dan sama dengan ideal $R\cdot \operatorname {FPB} (a,\,b)$.

Daerah integral yang berlaku identitas Bézout disebut sebagai daerah Bézout.

Sejarah dan pengatributan

Matematikawan Prancis, Étienne Bézout (1730–1783), membuktikan identitas Bezout untuk polinomial. Pernyataan untuk bilangan bulat sudah dapat ditemukan dalam karya milik seorang matematikawan Prancis sebelumnya, Claude Gaspard Bachet de Méziriac. Andrew Granville menelusuri pengatributan nama Bézout dengan identitas persamaan tersebut ke Bourbaki, dengan argumen bahwa hal tersebut merupakan atribusi yang salah, sebab identitas tersebut bersifat implisit pada Elements karya Euclid.

Lihat juga

• Teorema AF+BG
• Persamaan Diophantus
• Lema Euclid
• Teorema dasar aritmetika

Pranala luar

• (Inggris) Kalkulator daring untuk identitas Bézout.
• Weisstein, Eric W. "Identitas Bézout". MathWorld.