Algoritma Pembagian

Algoritma Pembagian

Pada pembelajaran kali ini penulis ingin mengajukan masalah tentang algoritma pembagian, yaitu:

Diberikan bilangan bulat a dan b dengan b > 0, maka terdapat tepat satu bilangan bulat q dan r yang memenuhi a = qb + r , 0 ≤ r < b.

Bukti:

Untuk menyelesaikan hal tersebut, kita lakukan dulu percobaan atas pernyataan tersebut seperti di bawah ini:

Contoh 1

12 = 2.6 + 0, hanya berlaku untuk  b=6 dan r = 0

12 = 6.2 + 0, hanya berlaku untuk  b=2 dan r = 0

12 = 3.4 + 0, hanya berlaku untuk  b=4 dan r = 0

12 = 3.4 + 0, hanya berlaku untuk  b=3 dan r = 0

12 = 1.12 + 0, , hanya berlaku untuk  b=12 dan r = 0

12 = 12.1 + 0, , hanya berlaku untuk  b=1 dan r = 0

Contoh 2

7 = 2.3 + 1, hanya berlaku untuk  b=3 dan r = 1

7 = 3.2 + 1, hanya berlaku untuk  b=2 dan r = 1

7 = 7.1 + 0, hanya berlaku untuk  b=1 dan r = 0

7 = 1.7 + 0, hanya berlaku untuk  b=7 dan r = 0

Contoh 3

11 = 2.5 + 1, hanya berlaku untuk  b=5 dan r = 1

11 = 5.2 + 1, hanya berlaku untuk  b=2 dan r = 1

11=11.1+0, hanya berlaku untuk  b=1 dan r = 0

11=1.11+0, hanya berlaku untuk  b=11 dan r = 0

dan seterusnya.

Perhatikan himpuanan bilangan S = { a-xb ≥0│x bilangan bulat}

Berdasarkan WOP (Will Ordering Principle) setiap himpunan bilangan bulat tidak negative S dengan S≠ himpunan kosong. Sehingga,

(1) Akan ditunjukan bahwa S≠ himpunan kosong

Berdasarkan algoritma pembagian untuk a dan b bilangan bulat dengan b > 0 atau dapat ditulis     b ≥ 1 sehingga │a│b ≥│a│ (kedua ruas dikalikan dengan │a│).

Berdasarkan WOP, S memiliki bilangan bulat terkecil misalkan r. Maka, menurut definisi ada bilangan bulat x  yang memenuhi:

r = a – xb, untuk r ≥ 0

Sedangkan menurut definisi,

a – xb ≥ 0

a –a – xb ≥ 0 – a  (kedua ruas dikurangkan dengan a)

        – xb ≥  – a

           xb ≤  a, sifat penyelesaian pertidaksamaan linier

             x ≤  a/b, dimana b ≥ 1

             x ≤│a│/ b, untuk berapapun nilai a

             x ≤  a/b ≤│a│/ b ≤ │a│, untuk b=1

sehingga, x ≤│a│

kerena x ≤│a│, pilih x ≤ -│a│

maka sesuai definisi:

a – xb = a – (-│a│)b  = a +│a│b ≥ a +│a│.1, karena b ≥ 1, untuk b=1

                                                      ≥ 0, untuk a negatif.

Sehingga, a – (-│a│)b ≥ 0, yang artinya S≠ himpunan kosong.

(2) Akan ditunjukkan r > b

Karena S≠ himpunan kosong berarti S memiliki unsur terkecil misalkan r. Menurut definisi maka ada bilangan bulat q yang memenuhu:

r = a – qb , r ≥ 0

andaikan bahwa r ≥ b (kontradiksi dari r < b) atau r - b ≥ 0, maka:

             r - b ≥ 0

    a – qb - b ≥ 0

a – (q + 1)b ≥ 0

karena a – (q + 1)b adalah anggota himpunan S, maka r - b adalah anggota himpunan S. Hal tersebut tidak mungkin terjadi sebab r – b < r , sedangkan r adalah anggota bilangan terkecil di S. Dengan demikian, asumsi bahwa r ≥ b adalah salah, jadi haruslah r > b.

Sehingga, dapat disimpulkan terdapat bilangan bulat bulat q dan r yang memenuhi a = qb + r ,   0 ≤ r < b.

(3) Akan ditunjukkan ketunggalan bilangan bulat q dan r

Misalkan terdapat dua buah bilangan a dituliskan:

a = qb + r , untuk 0 ≤ r < b dan a = q’b + r’, untuk 0 ≤ r’ < b

 maka,

   qb + r = q’b + r’

    r – r’ = q’b  - qb  

jika diharga mutlakan,

│r – r’│= │q’b  - qb│

 │r – r’│=  │b(q’ - q)│

│r – r’│= │b││-(q – q’)│

 │r – r’│= b│q – q’│

dengan menjumlahkan pertidaksamaan 0 ≤ r < b dan 0 ≤ r’ < b = -b < r’ ≤ 0 , didapat

 0 ≤ r < b

-b ≤ 0  +

-b < r – r’ < b

ekuvalen dengan definisi harga mutlak yaitu untuk │x│< a , maka -a < x < a.

sehingga dari -b < r – r’ < b didapat:

│r – r’│< b

 │r – r’│= b│q – q’│< b

                   │q – q’│< 1

Jelas bahwa q – q’ = 0 sehingga q = q’, maka r = r’.

Artinya, dapat disimpulkan bahwa bilangan q dan r adalah tungggal.

Kesimpulan: dari (1), (2), dan (3) dapat disimpulkan bahwa jika diberikan bilangan bulat a dan b dengan     b > 0, maka terdapat tepat satu bilangan bulat q dan r yang memenuhi a = qb + r ,  0 ≤ r < b.