Pembagian Euclid
Pada setiap pembagian bilangan bulat \( a \) oleh bilangan bulat \( b \) dimana \( b \ne 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 = bq + r\) dan \( 0 \le r \lt \lvert b \rvert \)
Tentu saja, jika \( r = 0 \) maka maknanya adalah tidak ada sisa bagi. Istilah yang biasa digunakan adalah "\( a \) habis dibagi oleh \( b \)" atau "\( b \) habis membagi \( a \)".
Agar lebih jelas, perhatikan contoh-contoh di bawah.
bukti
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 \ne 0 \), pasti ada tepat satu pasangan bilangan bulat \( (q, r) \) yang memenuhi \( a = bq + r \) dan \( 0 \le r \lt \lvert b \rvert \)
Maksudnya "tunggal" adalah bukti uniqeness, yaitu:
Pada setiap pembagian bilangan bulat \( a \) oleh bilangan bulat \( b \) dimana \( b \ne 0 \), pasti ada tepat satu pasangan bilangan bulat \( (q, r) \) yang memenuhi \( a = bq + r \) dan \( 0 \le r \lt \lvert b \rvert \)
Bukti Ada
Mula-mula, lupakan dulu batasan (constraint) \( 0 \le r \lt \lvert b \rvert \)
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.
\( \begin{align*} a &= bq_1 + r_1\\ a &= bq_2 + r_2\\ a &= bq_3 + r_3\\ &\cdots \\ a &= bq_n + r_n \end{align*} \)
Sekarang, simpan semua \( r \) ke dalam sebuah himpunan. Katakanlah nama himpunan ini \( R \), yaitu \( R = \{r_1, r_2, r_3, \cdots, r_n \} \)
Lalu, masukkan kembali batasan pertama \( r \ge 0 \) dengan cara membuang semua \( r \) yang lebih kecil dari \( 0 \). Sekarang semua anggota himpunan \( R \) pasti lebih besar atau sama dengan \( 0 \).
Himpunan R tidak kosong
Setelah membuang semua \( r \) negatif, mungkinkah himpunan \( R \) kosong? Tidak mungkin. Di bawah ini akan dibuktikan bahwa selalu ada \( r \) tidak negatif yang memenuhi \( a = bq + r \).
\( r = a - bq\)
Jika \( a \ge 0 \), ambil \( q = 0 \)
Diperoleh \( r = a \) dan \( r \) pasti tidak negatif.
Jika \( a \lt 0 \) dan \( b \gt 0 \), ambil \( q = a \)
Diperoleh \( r = -a \cdot (b - 1) \)
Karena \( a \lt 0 \) maka \( -a \) pasti positif.
Karena \( b \gt 0 \) dan \( b \in \mathbb{Z} \) maka \( (b - 1) \) pasti tidak negatif.
Karena \( r \) adalah perkalian bilangan positif dan bilangan tidak negatif, maka \( r \) pasti tidak negatif.
Jika \( a \lt 0 \) dan \( b \lt 0 \), ambil \( q = -a \)
Diperoleh \( r = a \cdot (b + 1) \)
Karena \( a \lt 0 \) maka \( a \) pasti negatif.
Karena \( b \lt 0 \) dan \( b \in \mathbb{Z} \) maka \( (b + 1) \) pasti tidak positif.
Karena \( r \) adalah perkalian bilangan negatif dan bilangan yang tidak positif, maka \( r \) pasti tidak negatif.
Bagaimana dengan kasus \( b = 0 \)? Karena pembagian dengan \( 0 \) tidak bisa didefinisikan, maka Pembagian Euclid pun tidak berlaku untuk \( b = 0 \). Kasus ini tidak perlu diperiksa.
Karena di semua kasus selalu bisa diambil bilangan bulat \( q \) sedemikian sehingga \( r \) tidak negatif, maka dapat disimpulkan bahwa himpunan \( R \) pasti tidak kosong.
Prinsip terurut rapi
Karena sekarang semua anggota himpunan \( R \) adalah bilangan bulat tidak negatif dan himpunan \( R \) tidak kosong, maka menurut prinsip terurut rapi, himpunan \( R \) pasti punya anggota himpunan terkecil. Katakanlah anggota himpunan yang terkecil ini namanya \( r_k \)
Di bawah akan dibuktikan bahwa \( r_k \lt \lvert b \rvert \) dengan menggunakan teknik kontradiksi.
Karena \( b \ne 0 \), maka pembagian akan dibagi ke dua kasus:
- Kasus \( b \) positif
- Kasus \( b \) negatif
Kasus 1: kasus b positif
Asumsikan \( r_k \ge b \) dimana \( b \gt 0 \)
Karena \( a = bq_k + r_k \) dan \( r_k \gt b \) , maka:
\(
\begin{align*}
a - bq_k &\ge b\\
a - bq_k - b &\ge 0\\
a - b(q_k + 1) &\ge 0
\end{align*}
\)
Misalkan \( q_k + 1 = q_j \) maka \( a - bq_j \ge 0 \)
Misalkan \( r_j = a - bq_j \) maka \( r_j \ge 0 \)
Karena \( a = bq_j + r_j \) dan \( r_j \ge 0 \) maka \( r_j \) pasti anggota himpunan \( R \) juga.
Sekarang, akan ditunjukkan bahwa \( r_j \lt r_k \)
Karena \( b \gt 0 \) maka:
\(
\begin{align*}
-b &\lt 0 \\
a - bq_k - b &\lt a - bq_k \\
r_j &\lt r_k
\end{align*}
\)
Terbukti sudah \( r_j \lt r_k \)
Berarti \( r_k \) bukan anggota himpunan terkecil. Terjadi kontradiksi. Dengan demikian, asumsi awal \( r_k \ge b \) salah.
Kasus 2: kasus b negatif
Asumsikan \( r_k \ge -b \) dimana \( b \lt 0 \)
Karena \( a = bq_k + r_k \) dan \( r_k \ge - b \), maka:
\(
\begin{align*}
a - bq_k &\ge -b\\
a - bq_k + b &\ge 0\\
a - b(q_k - 1) &\ge 0
\end{align*}
\)
Misalkan \( q_k - 1 = q_j \) maka \( a - bq_j \ge 0 \)
Misalkan \( r_j = a - bq_j \) maka \( r_j \ge 0 \)
Karena \( a = bq_j + r_j \) dan \( r_j \ge 0 \) maka \( r_j \) pasti anggota himpunan \( R \) juga.
Sekarang akan ditunjukkan bahwa \( r_j \lt r_k \)
Karena \( b \lt 0 \) maka:
\(
\begin{align*}
b &\lt 0 \\
a - bq_k + b &\lt a - bq_k \\
r_j &\lt r_k
\end{align*}
\)
Terbukti sudah \( r_j \lt r_k \)
Berarti \( r_k \) bukan anggota himpunan terkecil. Terjadi kontradiksi juga. Dengan demikian, asumsi awal \( r_k \ge -b \) salah.
Lengkaplah sudah bukti pertama. Pasti ada pasangan bilangan bulat \( (q, r) \) yang memenuhi \( a = bq + r \) dan \( 0 \le r \lt \lvert b \rvert \)
Bukti Tunggal
Misalkan ada dua pasangan bilangan bulat yang memenuhi, yaitu \( (q_1, r_1) \) dan \( (q_2, r_2) \)
Karena
\(
\begin{align*}
a &= bq_1 + r_1 \\
a &= bq_2 + r_2
\end{align*}
\)
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 \( \lvert b \rvert \) pasti juga habis membagi \( r_2 - r_ 1 \)
Karena \(r_1 \) dan \( r_2 \) keduanya bilangan bulat positif yang lebih kecil dari \( \lvert b \rvert \) maka \( \lvert r_2 - r_1 \rvert \) pasti juga lebih kecil dari \( \lvert b \rvert \)
\( \begin{align*} \lvert r_2 - r_1 \rvert &\lt \lvert b \rvert \\ \\ - \lvert b \rvert \lt r_2 - r_1 &\lt \lvert b \rvert \end{align*} \)
Mungkinkah \( \lvert b \rvert \) membagi habis bilangan yang lebih kecil darinya?
Mungkin saja. Ada satu kemungkinan dimana \( \lvert b \rvert \) habis membagi bilangan yang lebih kecil darinya, yaitu pada saat \( \lvert b \rvert \) membagi \( 0 \). Artinya, satu-satunya kemungkinan dimana \( \lvert b \rvert \) 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 \ne 0 \) maka \( q_1 = q_2 \)
Dari hasil-hasil di atas, ternyata \( 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 = bq + r \) dan \( 0 \le r \lt \lvert b \rvert \)
Contoh
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 \le r \lt 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 \le r \lt 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 \le r \lt 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 \le r \lt 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 \le r \lt 3 \)
- Satu-satunya solusi yang memenuhi adalah \( q = -6 \) dan \( r = 0 \)
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 + 3 \) dimana \( 0 \le r \lt 4 \)
- Satu-satunya solusi yang memenuhi adalah \( q = 3 \) dan \( r = 0 \)
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 \le r \lt 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 \le r \lt 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 \le r \lt 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 \le r \lt 10 \)
- Satu-satunya solusi yang memenuhi adalah \( q = -1 \) dan \( r = 7 \)
Contoh 11
Nyatakan pembagian \( 0 \) oleh \( 3 \) dalam pembagian Euclid.
Pembagian \( 0 \) oleh \( 3 \) dinyatakan sebagai \( 0 = 3 \cdot 0 + 0 \)
Hasil bagi (quotient) \( q = 0 \)
Sisa bagi (remainder) \( r = 0 \)
Makna paragraf di atas menurut teorema Pembagian Euclid adalah:
- Pembagian \( 0 \) oleh \( 3 \) pasti bisa dinyatakan dalam bentuk \( 0 = 3 \cdot q + r \) dimana \( 0 \le r \lt 3 \)
- Satu-satunya solusi yang memenuhi adalah \( q = 0 \) dan \( r = 0 \)