Bezout Identity

<<Algoritama Eucledian
Sebelum kita sampai pada karakteristik ketiga dari gcd, kita harus bisa melakukan algoritma Euclidean ke belakang. Ini kadang dikenal sebagai identitas Bezout. Kalau di Indonesia dikenal dengan nama Kombinasi Lanjar (Linier Combination).

Teorema Bezout Identity.

Misalkan \(a\) dan \(b\) adalah dua buah bilangan bulat positif, maka terdapat bilangan bulat \(x\) dan \(y\) sedemikian sehingga \(GCD(a,b) = ax + by\).

Algoritma Euclidean

<<GCD
Di dalam Pembagi Persekutuan Terbesar telah diperlihatkan bahwa untuk mencari GCD dari dua buah bilangan bulat a dan b, mula-mula kita mendaftarkan semua pembagi dari masing-masing a dan b, lalu memilih pembagi persekutuan yang bernilai paling besar.

Pada bagian ini akan diberikan metode untuk menemukan GCD, yang dikenal dengan nama Algoritma Euclidean. Algoritma ini sudah dikenal sejak lama. Euclid, penemu algoritma ini adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.

Algoritma Euclidean didasarkan pada Teorema Algoritma Pembagian  secara berturut-turut sampai kita menemukan sisa pembagian bernilai 0. Secara formal algoritma Euclidean dirumuskan sebagai berikut:

Misalkan a dan b adalah bilangan bulat positif dengan \(a\geq b\). Misalkan \(r_{0}=a\) dan \(r_{1}=b\). Lakukan secara berturut-turut Teorema Algoritma Pembagian untuk memperoleh :

\(r_{0} = r_{1}q_{1}+r_{2}\)             \(0\leq r_{2}\leq r_{1} \)

\(r_{1} = r_{2}q_{2}+r_{3}\)             \(0\leq r_{3}\leq r_{2} \)

.

.

.

\(r_{n-2} = r_{n-1}q_{n-1}+r_{n}\)    \(0\leq r_{n}\leq r_{n-1} \)

\(r_{n-1} = r_{n}q_{n}+0\)

Menurut Teorema Algoritma Euclidean,

\(GCD(a,b)=GCD(r_{0},r_{1})=GCD(r_{1},r_{2})=...=GCD(r_{n-2},r_{n-1})=GCD(r_{n-1},r_{n})=GCD(r_{n},0)=r_{n}\)

Extended GCD.

Bezout Identity>>

Pembagi Persekutuan Terbesar

<<Algoritma Pembagian

Pembagi Persekutuan Terbesar (PBB) atau Faktor Persekutuan Terbesar (FPB) atau bisa juga disebut Pembagi Bersama Terbesar, dalam bahasa Inggris disebut The Greatest Common Divisor (GCD).

Dua buah bilangan bulat dapat memiliki faktor pembagi yang sama. Faktor pembagi bersama yang terpenting adalah GCD. Misalnya 45 memiliki faktor pembagi 1, 3, 5, 9, 15 dan 45 sendiri; sedangkan 36 memiliki faktor pembagi 1, 2, 3, 4, 9, 12, 18, dan 36 sendiri. Faktor pembagi bersama dari 45 dan 36 adalah 1, 3, dan 9. Yang terbesar adalah 9 sehingga disimpulkan GCD(45,36) = 9

Untuk mencari GCD pada Sagemath dapat dilakukan dengan cara di bawah ini.

Definisinya adalah sebagai berikut :

Misalkan \(a\) dan \(b\) adalah dua buah bilangan bulat tidak 0. GCD dari \(a\) dan \(b\) adalah bilangan bulat terbesar \(d\) sedemikian hingga \(d|a\) dan \(d|b\) . Dalam hal ini dinyatakan sebagai \(GCD(a,b) = d\).

Sifat-sifat dari GCD dinyatakan dalam Teorema di bawah ini:

Misalkan a, b, dan c adalah bilangan bulat.

Jika \(c\) adalah GCD dari \(a\) dan \(b\), maka \(c|a+b\). 

Jika \(c\) adalah GCD dari \(a\) dan \(b\), maka \(c|a-b\). 

Jika \(c|a\), maka \(c|ab\).

Algoritma Eucledian>>

Algoritma Pembagian

Jika kita membagi bilangan bulat a dengan b (bilangan bulat positif), Maka kita akan selalu mendapatkan bilangan bulat sisa r yang tidak negatif, namun kurang dari b. 

Teorema Algoritma Pembagian.   
Untuk  \(a,b \in Z\) dan \(b > 0\) kita dapat menulis \(a = kb + r\) dengan  \(0 \leq r < b\)

Sesuai Algoritma Pembagian di atas, sangat mudah untuk melakukan pembagian pada contoh bilangan yang tidak terlalu besar seperti contoh berikut  :
 \(a = 13\) dan \(b = 3\),
\[13 = 4.3 + 1\] sehingga \(q = 4\) dan \(r = 1\)
Untuk pembagian bilangan bulat yang lebih besar maka kita bisa menggunakan bantuan Sagemath sebagai berikut :

Jika ingin mengetahui tentang fungsi \(divmod\), ketik saja \(divmod?\) di dalam Sage Cell seperti di bawah ini.

GCD>>