Pembagi Persekutuan Terbesar

Pembagi Persekutuan Terbesar

Definisi: Misalkan a dan b adalah bilangan-bilangan bulat dengan salah satu diantaranya tidak sama dengan nol. Pembagi persekutuan terbesar dari a dan b dinotasikan dengan ppb(a,b) adalah bilangan bulat positif d yang memenuhi:

1) d|a dan d|b

2) Jika a|c dan b|c , maka c ≤ d

Masalah: Misalkan a dan b adalah bilangan-bilangan bulat dengan tidak keduanya nol, maka ada bilangan bulat x dan y sehingga ppb(a,b) = ax + by.

Bukti:

Perhatikan himpunan bilangan S semua kombinasi linier positif dari a dan b:

S = {au + bv | au + bv > 0; u,v adalah bilangan bulat}.

Himpunan S adalah himpunan tidak kosong, sebagai contoh untuk a≠0 maka bilangan bulat |a| = au + b.0 merupakan anggota S dengan memilih u=1 atau u=-1. 

Karena S bukan himpunan kosong maka berdasarkan  Well Ordering Principle (WOP) S harus memuat bilangan terkecil misalkan adalah d. Akibatnya, berdasarkan definisi bilangan S maka terdapat bilangan x dan y sehingga d = ax + by dengan x dan y adalah bilangan bulat. Sehingga mengakibatkan d= ppb(a,b).

Dengan menggunakan algoritma pembagian, kita dapat memperoleh bilangan-bilangan bulat q dan r sehingga a= qr + r, untuk 0 ≤ r < d. Kemudian r dapat ditulisdengan:

r = a – qd = a – q(ax + by)

                = a – qax – qby

               =a(1-qx) + b(-qy)

>>> Andaikan r ≠ 0, maka mengakibatkan r ada pada himpunan S. Akan tetapi, d merupakan bilangan terkecil di S sehingga d < r. Artinya, pernyataan bahwa r > d dan d < 0 tidak mungkin terjadi. Sehingga menurut prinsip trikotomi maka r = 0 atau  a = qd ataupun d|b.

>>> Analogi dengan menggunakan pengandaian dan cara yang sama kita dapat menunjukkan bahwa d|b. Dengan demikian, d merupakan pembagi persekutuan dari a dan b.

>>> Kemudian misalkan  c adalah sembarang pembegi persekutuan positif a dan b, dengan kata lain c|a dan c|b diperoleh c|(as+bt) untuk sembarang bilangan positif s dan t. Karena as dan bt adalah anggota dari himpunan S untuk setiap s, t, dan d elemen S maka c|d. Berdasarkan teorema c = |c| ≤ |d| = d, sehingga karena d|a,b|b dan untuk sembarang c  dari a dan b mengakibatkan  c ≤ d maka menurut definisi d=ppb(a,b).