Lewati ke konten utama

Bagian 2.2 Algoritma Pembagian

Salah satu penerapan Prinsip Urutan Baik yang akan sering kita gunakan adalah algoritma pembagian.

Bukti.
Ini merupakan contoh sempurna dari jenis bukti keberadaan dan ketunggalan. Pertama-tama kita harus membuktikan bahwa bilangan \(q\) dan \(r\) benar-benar ada. Kemudian kita harus menunjukkan bahwa jika \(q'\) dan \(r'\) merupakan dua bilangan lain dengan sifat tersebut, maka \(q = q'\) dan \(r = r'\text{.}\)

Keberadaan \(q\) dan \(r\).

Misalkan
\begin{equation*} S = \{ a - bk : k \in {\mathbb Z} \text{ dan } a - bk \geq 0 \}\text{.} \end{equation*}
Jika \(0 \in S\text{,}\) maka \(b\) membagi \(a\text{,}\) dan kita dapat mengambil \(q = a/b\) dan \(r = 0\text{.}\) Jika \(0 \notin S\text{,}\) kita dapat menggunakan Prinsip Urutan Baik. Pertama-tama kita harus menunjukkan bahwa \(S\) tak kosong. Jika \(a \gt 0\text{,}\) maka \(a - b \cdot 0 \in S\text{.}\) Jika \(a \lt 0\text{,}\) maka \(a - b(2a) = a(1 - 2b) \in S\text{.}\) Dalam kedua kasus tersebut, \(S \neq \emptyset\text{.}\) Berdasarkan Prinsip Urutan Baik, \(S\) harus mempunyai anggota terkecil, misalkan \(r = a - bq\text{.}\) Oleh karena itu, \(a = bq + r\text{,}\) dengan \(r \geq 0\text{.}\) Sekarang kita tunjukkan bahwa \(r \lt b\text{.}\) Misalkan \(r \gt b\text{.}\) Maka
\begin{equation*} a - b(q + 1)= a - bq - b = r - b \gt 0\text{.} \end{equation*}
Dalam hal ini, \(a - b(q + 1)\) akan berada dalam himpunan \(S\text{.}\) Akan tetapi, \(a - b(q + 1) \lt a - bq\text{,}\) yang bertentangan dengan fakta bahwa \(r = a - bq\) merupakan anggota terkecil dari \(S\text{.}\) Jadi \(r \leq b\text{.}\) Karena \(0 \notin S\text{,}\) berlaku \(r \neq b\text{,}\) sehingga \(r \lt b\text{.}\)

Ketunggalan \(q\) dan \(r\).

Ketunggalan \(q\) dan \(r\text{.}\) Misalkan terdapat bilangan bulat \(r\text{,}\) \(r'\text{,}\) \(q\text{,}\) dan \(q'\) sedemikian sehingga
\begin{equation*} a = bq + r, 0 \leq r \lt b \quad \text{dan}\quad a = bq' + r', 0 \leq r' \lt b\text{.} \end{equation*}
Maka \(bq + r = bq' + r'\text{.}\) Andaikan \(r' \geq r\text{.}\) Dari persamaan terakhir diperoleh \(b(q - q') = r' - r\text{;}\) oleh karena itu, \(b\) harus membagi \(r' - r\) dan \(0 \leq r'- r \leq r' \lt b\text{.}\) Hal ini hanya mungkin jika \(r' - r = 0\text{.}\) Jadi, \(r = r'\) dan \(q = q'\text{.}\)
Misalkan \(a\) dan \(b\) bilangan bulat. Jika \(b = ak\) untuk suatu bilangan bulat \(k\text{,}\) kita tulis \(a \mid b\text{.}\) Suatu bilangan bulat \(d\) disebut pembagi bersama dari \(a\) dan \(b\) jika \(d \mid a\) dan \(d \mid b\text{.}\) Faktor persekutuan terbesar (FPB) dari bilangan bulat \(a\) dan \(b\) adalah bilangan bulat positif \(d\) sedemikian sehingga \(d\) merupakan pembagi bersama dari \(a\) dan \(b\text{,}\) dan jika \(d'\) adalah pembagi bersama lain dari \(a\) dan \(b\text{,}\) maka \(d' \mid d\text{.}\) Kita tulis \(d = \gcd(a, b)\text{;}\) sebagai contoh, \(\gcd( 24, 36) = 12\) dan \(\gcd(120, 102) = 6\text{.}\) Dua bilangan bulat \(a\) dan \(b\) disebut relatif prima jika \(\gcd( a, b ) = 1\text{.}\)

Bukti.
Misalkan
\begin{equation*} S = \{ am + bn : m, n \in {\mathbb Z} \text{ dan } am + bn \gt 0 \}\text{.} \end{equation*}
Jelas bahwa himpunan \(S\) tak kosong; maka, berdasarkan Prinsip Urutan Baik, \(S\) harus mempunyai anggota terkecil, misalkan \(d = ar + bs\text{.}\) Kita menyatakan bahwa \(d = \gcd( a, b)\text{.}\) Tuliskan \(a = dq + r'\) dengan \(0 \leq r' \lt d\text{.}\) Jika \(r' \gt 0\text{,}\) maka
\begin{align*} r'& = a - dq\\ & = a - (ar + bs)q\\ & = a - arq - bsq\\ & = a( 1 - rq ) + b( -sq )\text{,} \end{align*}
yang berada dalam \(S\text{.}\) Namun, hal ini bertentangan dengan fakta bahwa \(d\) merupakan anggota terkecil dari \(S\text{.}\) Jadi, \(r' = 0\) dan \(d\) membagi \(a\text{.}\) Argumen serupa menunjukkan bahwa \(d\) membagi \(b\text{.}\) Oleh karena itu, \(d\) merupakan pembagi bersama dari \(a\) dan \(b\text{.}\)
Misalkan \(d'\) merupakan pembagi bersama lain dari \(a\) dan \(b\text{,}\) dan kita ingin menunjukkan bahwa \(d' \mid d\text{.}\) Jika kita mengambil \(a = d'h\) dan \(b = d'k\text{,}\) maka
\begin{equation*} d = ar + bs = d'hr + d'ks = d'(hr + ks)\text{.} \end{equation*}
Jadi \(d'\) harus membagi \(d\text{.}\) Dengan demikian, \(d\) harus merupakan satu-satunya faktor persekutuan terbesar dari \(a\) dan \(b\text{.}\)

Subbagian 2.2.1 Algoritma Euklides

Salah satu kegunaan Teorema 2.2.2 adalah memungkinkan kita menghitung faktor persekutuan terbesar dari dua bilangan bulat.

Contoh 2.2.4.

Mari kita hitung faktor persekutuan terbesar dari \(945\) dan \(2415\text{.}\) Pertama, perhatikan bahwa
\begin{align*} 2415 & = 945 \cdot 2 + 525\\ 945 & = 525 \cdot 1 + 420\\ 525 & = 420 \cdot 1 + 105\\ 420 & = 105 \cdot 4 + 0\text{.} \end{align*}
Dengan menelusuri langkah-langkah tersebut secara terbalik, \(105\) membagi \(420\text{,}\) \(105\) membagi \(525\text{,}\) \(105\) membagi \(945\text{,}\) dan \(105\) membagi \(2415\text{.}\) Jadi, \(105\) membagi baik \(945\) maupun \(2415\text{.}\) Jika \(d\) merupakan pembagi bersama lain dari \(945\) dan \(2415\text{,}\) maka \(d\) juga harus membagi \(105\text{.}\) Oleh karena itu, \(\gcd( 945, 2415 ) = 105\text{.}\)
Jika kita menelusuri barisan persamaan di atas secara terbalik, kita juga dapat memperoleh bilangan \(r\) dan \(s\) sedemikian sehingga \(945 r + 2415 s = 105\text{.}\) Perhatikan bahwa
\begin{align*} 105 & = 525 + (-1) \cdot 420\\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\ & = 2 \cdot 525 + (-1) \cdot 945\\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\ & = 2 \cdot 2415 + (-5) \cdot 945\text{.} \end{align*}
Jadi \(r = -5\) dan \(s= 2\text{.}\) Perhatikan bahwa \(r\) dan \(s\) tidak tunggal, karena \(r = 41\) dan \(s = -16\) juga memenuhi.
Untuk menghitung \(\gcd(a,b) = d\text{,}\) kita menggunakan pembagian berulang untuk memperoleh barisan menurun bilangan bulat positif \(r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}\) yaitu,
\begin{align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ & \aatavdots{=}\\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\ r_{n - 1} & = r_n q_{n + 1}\text{.} \end{align*}
Untuk mencari \(r\) dan \(s\) sedemikian sehingga \(ar + bs = d\text{,}\) kita mulai dengan persamaan terakhir ini dan menyubstitusikan hasil yang diperoleh dari persamaan-persamaan sebelumnya:
\begin{align*} d & = r_n\\ & = r_{n - 2} - r_{n - 1} q_n\\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}\\ & \aatavdots{=}\\ & = ra + sb\text{.} \end{align*}
Algoritma yang baru saja kita gunakan untuk mencari faktor persekutuan terbesar \(d\) dari dua bilangan bulat \(a\) dan \(b\text{,}\) serta menuliskan \(d\) sebagai kombinasi linear dari \(a\) dan \(b\text{,}\) dikenal sebagai algoritma Euklides.

Subbagian 2.2.2 Bilangan Prima

Misalkan \(p\) bilangan bulat sedemikian sehingga \(p \gt 1\text{.}\) Bilangan \(p\) disebut bilangan prima, atau cukup dikatakan \(p\) prima, jika satu-satunya bilangan positif yang membagi \(p\) adalah \(1\) dan \(p\) itu sendiri. Bilangan bulat \(n \gt 1\) yang tidak prima disebut komposit.

Bukti.
Misalkan \(p\) tidak membagi \(a\text{.}\) Kita harus menunjukkan bahwa \(p \mid b\text{.}\) Karena \(\gcd( a, p ) = 1\text{,}\) terdapat bilangan bulat \(r\) dan \(s\) sedemikian sehingga \(ar + ps = 1\text{.}\) Jadi,
\begin{equation*} b = b(ar + ps) = (ab)r + p(bs)\text{.} \end{equation*}
Karena \(p\) membagi baik \(ab\) maupun dirinya sendiri, \(p\) harus membagi \(b = (ab)r + p(bs)\text{.}\)

Bukti.
Kita akan membuktikan teorema ini dengan kontradiksi. Misalkan hanya terdapat berhingga banyaknya bilangan prima, yaitu \(p_1, p_2, \ldots, p_n\text{.}\) Misalkan \(P = p_1 p_2 \cdots p_n + 1\text{.}\) Maka \(P\) harus habis dibagi oleh suatu \(p_i\) untuk \(1 \leq i \leq n\text{.}\) Dalam hal ini, \(p_i\) harus membagi \(P - p_1 p_2 \cdots p_n = 1\text{,}\) suatu kontradiksi. Jadi, \(P\) prima atau terdapat bilangan prima tambahan \(p \neq p_i\) yang membagi \(P\text{.}\)

Bukti.

Ketunggalan.

Untuk menunjukkan ketunggalan, kita akan menggunakan induksi pada \(n\text{.}\) Teorema ini tentu benar untuk \(n = 2\) karena dalam hal ini \(n\) prima. Sekarang andaikan hasil tersebut berlaku untuk setiap bilangan bulat \(m\) sedemikian sehingga \(1 \leq m \lt n\text{,}\) dan
\begin{equation*} n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l\text{,} \end{equation*}
dengan \(p_1 \leq p_2 \leq \cdots \leq p_k\) dan \(q_1 \leq q_2 \leq \cdots \leq q_l\text{.}\) Berdasarkan Lema 2.2.5, berlaku \(p_1 \mid q_i\) untuk suatu \(i = 1, \ldots, l\) dan \(q_1 \mid p_j\) untuk suatu \(j = 1, \ldots, k\text{.}\) Karena semua \(p_i\) dan \(q_i\) adalah prima, berlaku \(p_1 = q_i\) dan \(q_1 = p_j\text{.}\) Jadi, \(p_1 = q_1\) karena \(p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}\) Berdasarkan hipotesis induksi,
\begin{equation*} n' = p_2 \cdots p_k = q_2 \cdots q_l \end{equation*}
mempunyai faktorisasi tunggal. Jadi, \(k = l\) dan \(q_i = p_i\) untuk \(i = 1, \ldots, k\text{.}\)

Keberadaan.

Untuk menunjukkan keberadaan, misalkan terdapat suatu bilangan bulat yang tidak dapat ditulis sebagai hasil kali bilangan-bilangan prima. Misalkan \(S\) himpunan semua bilangan tersebut. Berdasarkan Prinsip Urutan Baik, \(S\) mempunyai bilangan terkecil, misalkan \(a\text{.}\) Jika satu-satunya faktor positif dari \(a\) adalah \(a\) dan \(1\text{,}\) maka \(a\) prima, suatu kontradiksi. Jadi, \(a = a_1 a_2\) dengan \(1 \lt a_1 \lt a\) dan \(1 \lt a_2 \lt a\text{.}\) Tidak berlaku \(a_1\in S\) maupun \(a_2 \in S\text{,}\) karena \(a\) merupakan elemen terkecil dalam \(S\text{.}\) Jadi,
\begin{align*} a_1 & = p_1 \cdots p_r\\ a_2 & = q_1 \cdots q_s\text{.} \end{align*}
Oleh karena itu,
\begin{equation*} a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s\text{.} \end{equation*}
Jadi \(a \notin S\text{,}\) suatu kontradiksi.

Subbagian 2.2.3 Catatan Sejarah

Bilangan prima pertama kali dipelajari oleh orang Yunani kuno. Dua hasil penting dari zaman kuno adalah bukti Euklides bahwa terdapat tak hingga banyaknya bilangan prima dan Saringan Eratosthenes, suatu metode untuk menghitung semua bilangan prima yang lebih kecil daripada bilangan bulat positif tetap \(n\text{.}\) Salah satu masalah dalam teori bilangan adalah mencari fungsi \(f\) sedemikian sehingga \(f(n)\) prima untuk setiap bilangan bulat \(n\text{.}\) Pierre Fermat (1601?–1665) menduga bahwa \(2^{2^n} + 1\) prima untuk setiap \(n\text{,}\) tetapi kemudian Leonhard Euler (1707–1783) menunjukkan bahwa
\begin{equation*} 2^{2^5} + 1 = 4{,}294{,}967{,}297 \end{equation*}
merupakan bilangan komposit. Salah satu dari banyak dugaan mengenai bilangan prima yang belum terbukti adalah Dugaan Goldbach. Dalam sebuah surat kepada Euler pada tahun 1742, Christian Goldbach mengemukakan dugaan bahwa setiap bilangan bulat genap selain \(2\) tampaknya merupakan jumlah dua bilangan prima: \(4 = 2 + 2\text{,}\) \(6 = 3 + 3\text{,}\) \(8 =3 + 5\text{,}\) \(\ldots\text{.}\) Meskipun dugaan tersebut telah diperiksa untuk bilangan-bilangan hingga \(4 \times 10^{18}\text{,}\) dugaan itu masih belum terbukti secara umum. Karena bilangan prima memegang peranan penting dalam kriptografi kunci publik, saat ini terdapat minat yang sangat besar untuk menentukan apakah suatu bilangan besar merupakan bilangan prima.
Sblm.Paling AtasLanjut