Page 33 - Teori Bilangan
P. 33
Selanjutnya akan dibahas algoritma pembagian. Istilah
algoritma pembagian tidak menunjukkan adanya algoritma.
Diberikan teorema algoritma pembagian sebagai berikut.
Teorema 3.10
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
