Hendra Jaya Napitupulu | Algoritma Pembagian

Algoritma Pembagian

Pada setiap bilangan bulat $a$ dan $b$ dimana $b \neq 0$ , pasti ada tepat satu pasangan bilangan bulat $(q, r)$ , $q$ adalah hasil bagi (quotient) dan $r$ adalah sisa bagi (remainder), yang memenuhi $a = b q + r$ dan $0 \leq r < |b|$

Contoh 1

Pasangan bilangan bulat $(23, 4)$ dapat dinyatakan sebagai $23 = 4 \cdot 5 + 3$
Hasil bagi (quotient) $q = 5$
Sisa bagi (remainder) $r = 3$ dan $0 \leq 3 < 4$

Contoh 2

Pasangan bilangan bulat $(−17, 5)$ dapat dinyatakan sebagai $−17 = 5 \cdot (−4) + 3$
Hasil bagi (quotient) $q = −4$
Sisa bagi (remainder) $r = 3$ dan $0 \leq 3 < 5$

Contoh 3

Pasangan bilangan bulat $(29, −6)$ dapat dinyatakan sebagai $29 = (−6) \cdot (−4) + 5$
Hasil bagi (quotient) $q = −4$
Sisa bagi (remainder) $r = 5$ dan $0 \leq 5 < 6$

Contoh 4

Pasangan bilangan bulat $(−27, −6)$ dapat dinyatakan sebagai $−27 = (−6) \cdot 5 + 3$
Hasil bagi (quotient) $q = 5$
Sisa bagi (remainder) $r = 3$ dan $0 \leq 3 < 6$

Contoh 5

Pasangan bilangan bulat $(18, −3)$ dapat dinyatakan sebagai $18 = (−3) \cdot 6 + 0$
Hasil bagi (quotient) $q = 6$
Sisa bagi (remainder) $r = 0$ dan $0 \leq 0 < 3$

Bukti

Ada dua hal yang harus dibuktikan, yaitu ada dan tunggal.

Maksudnya "ada" adalah bukti existence, yaitu:
Pada setiap bilangan bulat $a$ dan $b$ dimana $b \neq 0$ , pasti ada tepat satu pasangan bilangan bulat $(q, r)$ yang memenuhi $a = b q + r$ dan $0 \leq r < |b|$

Maksudnya "tunggal" adalah bukti uniqeness, yaitu:
Pada setiap bilangan bulat $a$ dan $b$ dimana $b \neq 0$ , pasti ada tepat satu pasangan bilangan bulat $(q, r)$ yang memenuhi $a = b q + r$ dan $0 \leq r < |b|$

Bukti Ada

Mula-mula, lupakan dulu batasan (constraint) $0 \leq r < |b|$

Karena tidak ada batasan, maka ada tak terhingga banyaknya cara menuliskan bilangan bulat $a$ , yaitu dengan mengambil nilai $q$ yang berbeda-beda. Akibatnya, ada tak terhingga banyaknya $r$ seperti di bawah ini.

$a = b q_{1} + r_{1}$
$a = b q_{2} + r_{2}$
$a = b q_{3} + r_{3}$
...
$a = b q_{n} + r_{n}$

Sekarang, simpan semua $r$ ke dalam sebuah himpunan. Katakanlah nama himpunan ini R, yaitu $R = {r_{1}, r_{2}, r_{3}, \dots, r_{n}}$

Lalu, masukkan kembali batasan pertama $r \geq 0$ dengan cara membuang semua $r$ yang lebih kecil dari $0$ . Sekarang semua anggota himpunan R pasti lebih besar atau sama dengan $0$ .

Karena sudah diberi batas bawah, maka sekarang himpunan R pasti punya anggota himpunan terkecil. Katakanlah anggota himpunan yang terkecil ini namanya $r_{k}$

Di bawah akan dibuktikan bahwa $r_{k} < |b|$ dengan menggunakan teknik kontradiksi.

Kasus 1

Misalkan $r_{k} \geq b$ dimana $b \geq 0$

Karena $a = b q_{k} + r_{k}$ dan $r_{k} \geq b$ , maka:
$a - b q_{k} \geq b$
$a - b q_{k} - b \geq 0$
$a - b (q_{k} + 1) \geq 0$

Misalkan $q_{k} + 1 = q_{j}$ maka

$a - b q_{j} \geq 0$

Karena $a$ bisa dituliskan sebagai $a = b q_{j} + r_{j}$ dan karena $a - b q_{j} \geq 0$ maka $r_{j} \geq 0$

Akibatnya $r_{j}$ juga anggota himpunan R dan $r_{j} < r_{k}$ . Artinya $r_{k}$ bukan anggota himpunan terkecil. Terjadi kontradiksi.

Kasus 2

Misalkan $r_{k} \geq −b$ dimana $b < 0$

Karena $a = b q_{k} + r_{k}$ dan $r_{k} \geq −b$ , maka:
$a - b q_{k} \geq −b$
$a - b q_{k} + b \geq 0$
$a - b (q_{k} - 1) \geq 0$

Misalkan $q_{k} - 1 = q_{j}$ maka

$a - b q_{j} \geq 0$

Karena $a$ bisa dituliskan sebagai $a = b q_{j} + r_{j}$ dan karena $a - b q_{j} \geq 0$ maka $r_{j} \geq 0$

Akibatnya $r_{j}$ juga anggota himpunan R dan $r_{j} < r_{k}$ . Artinya $r_{k}$ bukan anggota himpunan terkecil. Terjadi kontradiksi juga.

Dengan demikian, bukti pertama sudah selesai. Pasti ada pasangan bilangan bulat $(q, r)$ yang memenuhi $a = b q + r$ dan $0 \leq r < |b|$

Bukti Tunggal

Misalkan ada dua pasangan bilangan bulat yang memenuhi, yaitu $(q_{1}, r_{1})$ dan $(q_{2}, r_{2})$

Karena
$a = b q_{1} + r_{1}$
$a = b q_{2} + r_{2}$

Maka $b (q_{1} - q_{2}) = r_{2} - r_{1}$

Maknanya, $b$ habis membagi $r_{2} - r_{1}$

Karena $b$ habis membagi $r_{2} - r_{1}$ maka $|b|$ pasti juga habis membagi $r_{2} - r_{1}$

Karena $|b| > r_{2} \geq 0$ dan $|b| > r_{1} \geq 0$ maka $|b| > r_{2} - r_{1} > −|b|$

Mungkinkah $|b|$ membagi habis bilangan yang lebih kecil darinya?

Mungkin saja. Ada satu kemungkinan dimana $|b|$ habis membagi bilangan yang lebih kecil darinya, yaitu pada saat $|b|$ membagi $0$ .

Artinya, satu-satunya kemungkinan dimana $|b|$ habis membagi $r_{2} - r_{1}$ adalah pada saat $r_{2} = r_{1}$

Karena $r_{2} = r_{1}$ maka $q_{2} = q_{1}$

Artinya, tidak mungkin ada lebih dari satu pasangan bilangan bulat $(q, r)$ yang memenuhi

Dengan demikian, bukti kedua sudah selesai. Pasti ada tepat satu pasangan bilangan bulat $(q, r)$ yang memenuhi $a = b q + r$ dan $0 \leq r < |b|$