Hendra Jaya Napitupulu | Pembagian Euclid

Pembagian Euclid

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

Tentu saja, jika $r = 0$ maka maknanya adalah tidak ada sisa bagi. Dalam bahasa sehari-hari istilah yang lazim digunakan adalah " $a$ habis dibagi oleh $b$ " atau " $b$ habis membagi $a$ ".

Agar lebih jelas, perhatikan contoh-contoh di bawah.

Contoh 1

Nyatakan pembagian $23$ oleh $4$ dalam pembagian Euclid.

Pembagian $23$ oleh $4$ dinyatakan sebagai $23 = 4 \cdot 5 + 3$
Hasil bagi (quotient) $q = 5$
Sisa bagi (remainder) $r = 3$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $23$ oleh $4$ pasti bisa dinyatakan dalam bentuk $23 = 4 \cdot q + r$ dimana $0 \leq r < 4$
Satu-satunya solusi yang memenuhi adalah $q = 5$ dan $r = 3$

Contoh 2

Nyatakan pembagian $−17$ oleh $5$ dalam pembagian Euclid.

Pembagian $−17$ oleh $5$ dinyatakan sebagai $−17 = 5 \cdot (−4) + 3$
Hasil bagi (quotient) $q = −4$
Sisa bagi (remainder) $r = 3$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $−17$ oleh $5$ pasti bisa dinyatakan dalam bentuk $−17 = 5 \cdot q + r$ dimana $0 \leq r < 5$
Satu-satunya solusi yang memenuhi adalah $q = −4$ dan $r = 3$

Contoh 3

Nyatakan pembagian $29$ oleh $−6$ dalam pembagian Euclid.

Pembagian $29$ oleh $−6$ dinyatakan sebagai $29 = (−6) \cdot (−4) + 5$
Hasil bagi (quotient) $q = −4$
Sisa bagi (remainder) $r = 5$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $29$ oleh $−6$ pasti bisa dinyatakan dalam bentuk $29 = (−6) \cdot q + r$ dimana $0 \leq r < 6$
Satu-satunya solusi yang memenuhi adalah $q = −4$ dan $r = 5$

Contoh 4

Nyatakan pembagian $−27$ oleh $−6$ dalam pembagian Euclid.

Pembagian $−27$ oleh $−6$ dinyatakan sebagai $−27 = (−6) \cdot 5 + 3$
Hasil bagi (quotient) $q = 5$
Sisa bagi (remainder) $r = 3$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $−27$ oleh $−6$ pasti bisa dinyatakan dalam bentuk $−27 = (−6) \cdot q + r$ dimana $0 \leq r < 6$
Satu-satunya solusi yang memenuhi adalah $q = 5$ dan $r = 3$

Contoh 5

Nyatakan pembagian $18$ oleh $−3$ dalam pembagian Euclid.

Pembagian $18$ oleh $−3$ dinyatakan sebagai $18 = (−3) \cdot (−6) + 0$
Hasil bagi (quotient) $q = −6$
Sisa bagi (remainder) $r = 0$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $18$ oleh $−3$ pasti bisa dinyatakan dalam bentuk $18 = (−3) \cdot q + r$ dimana $0 \leq r < 3$
Satu-satunya solusi yang memenuhi adalah $q = −6$ dan $r = 0$

Tambahan: karena $r = 0$ , berarti $18$ habis dibagi oleh $−3$

Contoh 6

Nyatakan pembagian $12$ oleh $4$ dalam pembagian Euclid.

Pembagian $12$ oleh $4$ dinyatakan sebagai $12 = 4 \cdot 3 + 0$
Hasil bagi (quotient) $q = 3$
Sisa bagi (remainder) $r = 0$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $12$ oleh $4$ pasti bisa dinyatakan dalam bentuk $12 = 4 \cdot q + r$ dimana $0 \leq r < 4$
Satu-satunya solusi yang memenuhi adalah $q = 3$ dan $r = 0$

Tambahan: Karena $r = 0$ , berarti $4$ habis membagi $12$

Contoh 7

Nyatakan pembagian $3$ oleh $10$ dalam pembagian Euclid.

Pembagian $3$ oleh $10$ dinyatakan sebagai $3 = 10 \cdot 0 + 3$
Hasil bagi (quotient) $q = 0$
Sisa bagi (remainder) $r = 3$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $3$ oleh $10$ pasti bisa dinyatakan dalam bentuk $3 = 10 \cdot q + r$ dimana $0 \leq r < 10$
Satu-satunya solusi yang memenuhi adalah $q = 0$ dan $r = 3$

Contoh 8

Nyatakan pembagian $−4$ oleh $−22$ dalam pembagian Euclid.

Pembagian $−4$ oleh $−22$ dinyatakan sebagai $−4 = (−22) \cdot 1 + 18$
Hasil bagi (quotient) $q = 1$
Sisa bagi (remainder) $r = 18$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $−4$ oleh $−22$ pasti bisa dinyatakan dalam bentuk $−4 = (−22) \cdot q + r$ dimana $0 \leq r < 22$
Satu-satunya solusi yang memenuhi adalah $q = 1$ dan $r = 18$

Contoh 9

Nyatakan pembagian $−25$ oleh $90$ dalam pembagian Euclid.

Pembagian $−25$ oleh $90$ dinyatakan sebagai $−25 = 90 \cdot (−1) + 65$
Hasil bagi (quotient) $q = −1$
Sisa bagi (remainder) $r = 65$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $−25$ oleh $90$ pasti bisa dinyatakan dalam bentuk $−25 = 90 \cdot q + r$ dimana $0 \leq r < 90$
Satu-satunya solusi yang memenuhi adalah $q = −1$ dan $r = 65$

Contoh 10

Nyatakan pembagian $17$ oleh $−10$ dalam pembagian Euclid.

Pembagian $17$ oleh $−10$ dinyatakan sebagai $17 = (−10) \cdot (−1) + 7$
Hasil bagi (quotient) $q = −1$
Sisa bagi (remainder) $r = 7$

Makna paragraf di atas menurut teorema Pembagian Euclid adalah:

Pembagian $17$ oleh $−10$ pasti bisa dinyatakan dalam bentuk $17 = (−10) \cdot q + r$ dimana $0 \leq r < 10$
Satu-satunya solusi yang memenuhi adalah $q = −1$ dan $r = 7$

Bukti

Dari sekian banyak contoh yang diberikan di atas, rasanya Teorema Pembagian Euclid benar. Tetapi seribu contoh bukan bukti. Pembuktian secara umum harus diberikan agar teorema ini boleh diterima kebenarannya. Pembuktian secara umum (general) dan ketat (rigour) diberikan di bawah.

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

Maksudnya "ada" adalah bukti existence, yaitu:
Pada setiap pembagian bilangan bulat $a$ oleh bilangan bulat $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 pembagian bilangan bulat $a$ oleh bilangan bulat $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 b tidak negatif

Asumsikan $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 juga dinyatakan sebagai $a = b q_{j} + r_{j}$ dan karena $a - b q_{j} \geq 0$ maka $r_{j} \geq 0$

Karena $r_{j} \geq 0$ maka $r_{j}$ pasti anggota himpunan R.

Sekarang, akan ditunjukkan bahwa $r_{j} < r_{k}$

$r_{j} < r_{k}$
$a - b q_{j} < a - b q_{k}$
$a - b (q_{k} + 1) < a - b q_{k}$
$a - b q_{k} - b < a - b q_{k}$
$−b < 0$

Terbukti sudah $r_{j} < r_{k}$

Berarti $r_{k}$ bukan anggota himpunan terkecil. Terjadi kontradiksi. Dengan demikian, asumsi awal $r_{k} \geq b$ salah.

Kasus b negatif

Asumsikan $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 juga dinyatakan sebagai $a = b q_{j} + r_{j}$ dan karena $a - b q_{j} \geq 0$ maka $r_{j} \geq 0$

Karena $r_{j} \geq 0$ maka $r_{j}$ pasti anggota himpunan R.

Sekarang akan ditunjukkan bahwa $r_{j} < r_{k}$

$r_{j} < r_{k}$
$a - b q_{j} < a - b q_{k}$
$a - b (q_{k} - 1) < a - b q_{k}$
$a - b q_{k} + b < a - b q_{k}$
$b < 0$

Terbukti sudah $r_{j} < r_{k}$

Berarti $r_{k}$ bukan anggota himpunan terkecil. Terjadi kontradiksi juga. Dengan demikian, asumsi awal $r_{k} \geq −b$ salah.

Lengkaplah sudah bukti pertama. 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_{1} = r_{2}$

Karena $r_{1} = r_{2}$ maka $b (q_{1} - q_{2}) = 0$

Karena $b \neq 0$ maka $q_{1} = q_{2}$

Sampai disini sudah diperoleh $q_{1} = q_{2}$ dan $r_{1} = r_{2}$

Artinya, dua buah pasangan $(q_{1}, r_{1})$ dan $(q_{2}, r_{2})$ adalah pasangan yang sama.

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|$

Last updated: 8 August 2026