Page 33 - E-MODUL TEORI BILANGAN
P. 33
Selanjutnya akan dibahas algoritma pembagian. Istilah
algoritma pembagian tidak menunjukkan adanya algoritma.
Diberikan teorema algoritma pembagian sebagai berikut.
Jika , ∈ dan > 0 maka ada bilangan-bilangan , ∈
yang masing-masing tunggal sehingga q = rp + s dengan 0 ≤
< .
Jika p bukan faktor dari q, maka s memenuhi ketidaksamaan
0 < < . Dari pernyataan = + , 0 ≤ < , r disebut
hasil bagi (quotient), s disebut sisa (remainder), q disebut
yang dibagi (dividend) dan p disebut pembagi (divisor).
Bukti:
Dengan p, q ∈ Z dapat dibentuk suatu barisan aritmatika (q -
rp) dengan r ∈ Z, yaitu …, q - 3p, q - 2p, q - p, q, q + 2p, q +
3p, … yang mempunyai bentuk umum q – rp.
Ambil suatu himpunan A yang unsur-unsurnya adalah suku
barisan yang tidak negatif, yaitu:
A = q − rp r ∈ Z, q − rp ≥ 0}
Karena A ⊂ N dan N adalah himpunan terurut rapi. Menurut
prinsip terurut rapi, A memiliki unsur terkecil, misalnya s.
Karena s ∈ A, maka s = q – rp, untuk suatu r ∈ Z sehingga q
= rp + s. Jadi, jika p, q ∈ Z dan p > 0, maka ada r, s ∈ Z
sehingga q = rp +s.
27
