Identitas Bézout: Perbedaan antara revisi

Di dasarDalam [[teori bilangan]] elementer, i'''Identitasdentitas Bézout''' atau disebut juga '''Lemmalema Bézout''') adalah sebagai berikut [[teorema]] sebagai berikut:{{math_theorem
| name = Identitas Bézout
| math_statement = Misalkan ''<math a ''</math> dan ''<math> b ''</math> menjadiadalah [[bilangan bulat]] dengan [[pembagi persekutuan terbesar]] ''<math> d ''</math>. KemudianMaka, ada bilangan bulat ''<math> x ''</math> dan ''<math> y ''</math> seperti bilangan <math> ax + by = d </math>{{nowrap|''ax'' + ''by'' &#61; ''d''}}. Lebih umumumumnya lagi, bilangan bulat dari formulirbentuk <math> {{nowrap|''ax'' + ''by''}} </math> persis kelipatan ''<math> d'' </math>.
}}

Bilangan bulat '' <math>x ''</math> dan '' <math>y ''</math> disebut '' 'koefisien Bézout' '' untuk <math>('' a '', '' b '')</math>; mereka tidak uniktunggal. Sepasang koefisien Bézout dapat dihitung dengan [[algoritma Euklides diperpanjangdiperluas]]. Jika '' <math>a ''</math> dan '' <math>b ''</math> tidak nol, [[Algoritme Euklides|algoritma Euclidean yangEuklides]] diperluas menghasilkan salah satu dari dua pasangan sedemikian rupa sehingga <math>|x|\le \left |\frac{b}{d}\right |</math> dan <math>|y|\le\left |\frac{a}{d}\right |</math> (kesetaraan dapat terjadi hanya jika salah satu dari <math>a</math> dan <math>b</math> adalah kelipatan dari yang lain).

== Struktur solusipenyelesaian ==

KetikaJika <math>a</math> dan <math>b</math> tidaknol dan satu pasang koefisien Bézout {{<math|>(''x'', ''y'')}}</math> telah dihitung (misalnya, menggunakan [[algoritma Euklides diperpanjangdiperluas]]), semua pasangan dapat direpresentasikandiwakilkan dalam bentuk

:<math>\left(x-k\frac{b}{\gcd(a,b)},\ y+k\frac{a}{\gcd(a,b)}\right),</math>,

di mana {{<math | '' >k ''}}</math> adalah bilangan bulat sembarang dan pecahan disederhanakan menjadi bilangan bulat.

:<math> |x| \le \left |\frac{b}{\gcd(a,b)}\right |\quad</math> \text{and}\quaddan <math>|y| \le \left |\frac{a}{\gcd(a,b)}\right |,</math>

dan kesetaraan hanya dapat terjadi jika salah satu dari {{<math|''>a''}}</math> dan {{<math|''>b''}}</math> membagi yang lain.

Ini bergantung pada properti [[Divisi Euclidean]]: diberikan dua bilangan bulat '' <math>c ''</math> dan '' <math>d ''</math>, jika '' <math>d ''</math> tidak membagi '' <math>c ''</math>, maka terdapat tepat satu pasang {{<math|>(''q'',''r'')}}</math> sepertisehingga yang {{<math|1=''>c'' = ''dq'' + ''r''}}</math> dan {{<math|1=>0 < ''r'' < {{!}}''|d''{{!}}}}|</math>, dan satuada lagi seperti itusehingga {{<math|1=''>c'' = ''dq'' + ''r''}}</math> dan {{<math|1=>-{{!}}''|d''{{!}}| < ''r'' < 0}}</math>.

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

Algoritma ExtendedEuklides Euclideandiperluas selalu menghasilkan salah satu dari dua pasangan minimal ini.

Misalkan, ''<math>a'' = 12</math> dan ''<math>b'' = 42</math>, <math>\gcd (12, 42) = 6</math>. Kemudian kita memiliki identitas Bézout berikut, dengan koefisien Bézout ditulis dengan warna merah untuk pasangan minimal dan biru untuk pasangan lainnya.

Jika {{<math|1=>(x, y) = (18, -5)}}</math> adalah pasangan asli dari koefisien Bézout <math>\frac{18}{42/6} \in [2, 3]</math> menghasilkan pasangan minimal melalui {{<math|1=''>k'' = 2}}</math>, masing-masing {{<math|1=''>k'' = 3}}</math>: {{<math|1=>(18 -2⋅7 2 \cdot 7, -5 +2⋅2 2 \cdot 2) = (4, -1)}}</math>, dan {{<math|1=>(18 -3⋅7 3 \cdot 7, -5 +3⋅2 3 \cdot 2) = (-3, 1)}}</math>. [[DomainRanah Bézout]] adalah [[domainranah integral]] tempat memegang identitas Bézout. Secara khusus, identitas Bézout berlaku di [[domainranah ideal utama]]. Setiap teorema yang dihasilkan dari identitas Bézout dengan demikian benar di semua domainranah ini.

Diberikan bilangan bulat bukantaknol nol {{mvar|<math>a}}</math> dan {{mvar|<math>b}}</math>, misalkan <math>S=\{ax+by \mid x,y\in\mathbb{Z} \text{ dan } ax+by>0\}.</math> Himpunan {{mvar | <math>S}}</math> tidak kosong karena berisi salah satunya {{mvar|<math>a}}</math> atau {{<math|–''>-a''}}</math> (dengan {{<math|1=''>x'' = ±\pm 1}}</math> dan {{<math|1=''>y'' = 0}}</math>). Karena {{mvar | <math>S}}</math> adalah himpunan bilangan bulat positif yang tidak kosongtakkosong, iaini memiliki elemenunsur minimum <math>d = as + bt</math>, dengan [[Prinsipprinsip urutan keteraturanrapi]]. Untuk membuktikan bahwa {{mvar | <math>d}}</math> adalah pembagi persekutuan terbesar dari {{mvar | <math>a}}</math> dan {{mvar|<math>b}}</math>, kita harus membuktikan bahwa {{mvar | <math>d}}</math> adalah pembagi persekutuan dari {{mvar | <math>a}}</math> dan {{mvar | <math>b}}</math>, dan bahwa untuk suatu pembagi persekutuan lainnya {{mvar | <math>c}}</math> termasuk bilangan {{<math|''>c'' ≤\le ''d''}}</math>.

[[Divisi EuklideanEuklides]] dari {{mvar | <math>a}}</math> oleh {{mvar | <math>d}}</math> boleh ditulis

:<math>a=dq+r\quad\text{</math> dengan}\quad <math>0\le r<d.</math>.

Sisa {{mvar | <math>r}}</math> ada di <math>S\cup \{0\}</math>, lantaran

lalu jikamaka bilangan bulat <math>x_1, x_2, \ldots, x_n</math> seperti yang

memiliki propertisifat berikut:

* '' <math>d ''</math> adalah bilangan bulat positif terkecil dari bentuk ini;

* setiap angka dari formulir ini adalah kelipatan '' <math>d ''</math>.

* [[LemmaLema Euklides|Lema Euklidean]]