contoh dan cara pengerjaan algoritma pembagian

pada bilangan-bilangan bulat a dan b, dengan b>o, terdapat bilangan bulat q dan r yang memenuhi

a= qb+r                        o≤r<b

Bilangan bulat q dan r disebut hasil bagi dan sisa dalam pembagian a oleh b.

Pembuktian: Kita mulai dengan menyediakan himpunan

S= {a-xb|x sebuah bilangan bulat; a=xb≥o}

Bukan bilangan kosong. Dalam hal ini perlu menunjukkan sebuah nilai x yang membuat a-xb tidak negative. Karena bilangan bulat b≥1, kita peroleh a|b≥|a| maka

a-(-|a|)b=a+|a|b≥a+|a|≥o

Sehingga untuk pilihan x=-|a|, a-xb akan terletak pada himpunan S. Hal ini merupakan aplikasi dari prinsip pengaturan yang baik, dimana himpunan S mengandung bilangan bulat terkecil; yang disebut r. Dengan definisi S, terdapat sebuah bilanagn bulat q yang memenuhi

r=a-qb,             o≤r

Kita menganggap bahwa r<b. jika tidak, maka r≥b dan

a-(q+1)b=(a-qb)-b=r-b≥o

Implikasinya ialah bilangan bulat a-(q+1)b memiliki bentuk yang layak untuk menjadi anggota S. Tetapi a-(q+1)b=r-b<r, akan membawa pada kontradiksi atas pilihan r sebagai anggota terkecil himpunan S. maka r<b.

Kemudian kita akan menuju pada tugas untuk menunjukkan keunikan q dan r. Anggap bahwa a memiliki dua bentuk, yaitu:

a=ab+r=q1b+r1

Dimana o≤r<b≤r1<b maka r1-r=b(q-q1) dan berdasarkan kenyataan bahwa nilai absolute sama dengan hasil dari nilai absolute.

(r1-r1=b|q-q1)

Dengan menambahkan bahwa pertidaksamaan –b<-r≤o dan o≤r1<b, kita peroleh –b<r1-r<b atau dalam bentuk yang sama, |r1-r|<b. maka b|q-q1|<b yang menghasilkan

o≤|q-q1|<1

karena |q-q1| merupakan bilangan bulat bukan negative, satu-satunya kemungkinan ialah |q-q1|=o, sehingga q=q1, akhirnya r=r1 merupakan buktinya.

Sebuah versi yang lebih umum dari Algoritma Pembagian diperoleh dengan mengganti larangan bahwa b positif dengan b≠o.

COROLLARY. Jika a dan b adalah bilangan bulat, dengan b≠o, maka terdapat bilangan bulat unik q dan r yaitu

a=qb+r             o≤r<|b|

Pembuktian: cukup dengan mempertimbangkan bahwa b adalah negative, maka |b|>o dan karena menghasilkan bilangan bulat q1 dan r1 yang unik dimana

a=a1|b|+r                      o≤r<|b|

Catatan bahwa |b|=-b, dapat kita ambil q=-q1 untuk memperoleh a=qb+r dengan o≤r<|b|