Pengantar Teori Bilangan

Subbab 6.2 Pengantar Teori Bilangan

Kita telah menggunakan bilangan asli untuk menyelesaikan berbagai masalah. Himpunan bilangan ini tepat digunakan dalam matematika diskret karena banyaknya benda yang kita tangani selalu berupa bilangan bulat. Selama ini, bilangan asli menjadi alat bagi kita. Sekarang, mari kita luangkan waktu sejenak untuk menelaah alat tersebut. Penemuan matematis apa yang dapat kita peroleh tentang bilangan asli itu sendiri?

🔗

Inilah pertanyaan utama teori bilangan, cabang matematika yang luas, kuno, rumit, dan terutama, indah. Dalam sejarahnya, teori bilangan dikenal sebagai Ratu Matematika dan sangat lekat dengan matematika murni: teori ini dipelajari demi teori itu sendiri, bukan sebagai sarana untuk memahami penerapan di dunia nyata. Namun, keadaan ini telah berubah dalam beberapa tahun terakhir seiring ditemukannya berbagai penerapan teori bilangan. Contoh yang mungkin paling dikenal ialah kriptografi RSA, salah satu metode untuk mengenkripsi data di internet. Teori bilanganlah yang memungkinkan metode tersebut.

🔗

Pertanyaan seperti apa yang termasuk dalam ranah teori bilangan? Berikut sebuah contoh sebagai motivasi. Ingat bahwa dalam pembahasan tentang induksi, kita pernah bertanya:

🔗

Nilai ongkos kirim berapa saja yang dapat dibentuk secara tepat hanya dengan menggunakan perangko 5 sen dan 8 sen?
🔗

🔗

Kita berhasil membuktikan bahwa setiap nilai ongkos kirim yang lebih besar dari 27 sen dapat dibentuk. Anda mungkin bertanya-tanya apa yang terjadi jika nominal perangkonya diubah. Bagaimana jika kita memiliki perangko 4 sen dan 9 sen? Apakah ada suatu nilai tertentu yang membuat semua nilai sesudahnya dapat dibentuk? Sekali lagi, kita dapat mengganti dua perangko 4 sen dengan satu perangko 9 sen, atau tiga perangko 9 sen dengan tujuh perangko 4 sen. Dalam kedua kasus, kita dapat menambah nilai ongkos kirim sebesar satu sen. Dengan menggunakan fakta ini sebagai kasus induktif, kita dapat membuktikan bahwa setiap nilai ongkos kirim yang lebih besar dari 23 sen dapat dibentuk.

🔗

Bagaimana jika kita memiliki perangko 2 sen dan 4 sen? Kali ini kemungkinannya tampak kurang menjanjikan. Jika kita mengambil sejumlah perangko 2 sen dan sejumlah perangko 4 sen, apa yang dapat dikatakan tentang jumlah nilainya? Mungkinkah jumlah itu ganjil? Tampaknya tidak.

🔗

Mengapa pasangan 5 dan 8 berhasil, pasangan 4 dan 9 berhasil, tetapi pasangan 2 dan 4 tidak? Sifat apa yang dimiliki bilangan-bilangan ini? Jika Anda diberi sepasang bilangan, dapatkah Anda langsung menentukan apakah pasangan itu akan berhasil? Kita akan menjawab pertanyaan-pertanyaan ini dan pertanyaan lainnya setelah terlebih dahulu menyelidiki beberapa sifat bilangan yang lebih sederhana.

🔗

Subbagian Keterbagian

Bilangan asli mudah dijumlahkan dan dikalikan. Jika cakupan kita diperluas ke semua bilangan bulat, pengurangan juga menjadi mudah (kita memerlukan bilangan negatif agar dapat mengurangkan sembarang bilangan dari bilangan lain, bahkan bilangan yang lebih besar dari bilangan yang lebih kecil). Pembagian merupakan operasi pertama yang menimbulkan tantangan. Jika kita ingin memperluas himpunan bilangan agar setiap pembagian dapat dilakukan (mungkin dengan mengecualikan pembagian oleh 0), kita harus beralih ke bilangan rasional, yaitu himpunan semua bilangan yang dapat ditulis sebagai pecahan. Langkah itu akan membawa kita terlalu jauh, jadi pilihan tersebut tidak akan kita ambil.

🔗

Bahkan, fakta bahwa tidak setiap bilangan habis dibagi oleh bilangan lain justru menguntungkan. Fakta ini membantu kita memahami struktur bilangan asli dan membuka jalan menuju banyak pertanyaan serta penerapan yang menarik.

🔗

Untuk bilangan $a$ dan $b \ne 0\text{,}$ mungkin saja $a \div b$ menghasilkan bilangan bulat. Dalam hal ini, kita mengatakan bahwa $b$ membagi $a\text{;}$ secara simbolis, kita menulis $b \mid a\text{.}$ Jika ini berlaku, $b$ adalah pembagi atau faktor dari $a\text{,}$ sedangkan $a$ adalah kelipatan dari $b\text{.}$ Secara umum, $b \mid a$ berarti $a = bk$ untuk suatu bilangan bulat $k$ (artinya, $a$ merupakan suatu kelipatan dari $b$).

🔗

Relasi Keterbagian.

Untuk bilangan bulat $m$ dan $n\text{,}$ kita mengatakan “$m$ membagi $n$” dan menulis

\begin{equation*} m \mid n \end{equation*}

apabila $n = mk \text{ untuk suatu } k\in\Z\text{.}$ Dengan demikian, pernyataan-pernyataan berikut memiliki arti yang sama:

$m \mid n\text{.}$

🔗
$n = mk$ untuk suatu bilangan bulat $k\text{.}$

🔗
$m$ adalah faktor (atau pembagi) dari $n\text{.}$

🔗
$n$ adalah kelipatan dari $m\text{.}$

🔗

🔗

Perhatikan bahwa $m \mid n$ merupakan suatu pernyataan. Pernyataan itu bernilai benar atau salah. Sebaliknya, jika penyebutnya tak nol, $n \div m$ atau $n/m$ merupakan suatu bilangan. Untuk pembagi tak nol, jika kita ingin menyatakan bahwa $n/m$ bukan bilangan bulat, sehingga $m$ tidak membagi $n\text{,}$ kita dapat menulis $m \nmid n\text{.}$

🔗

Contoh 6.2.1.

Tentukan apakah setiap pernyataan berikut benar atau salah.

$\displaystyle 4 \mid 20$

🔗
$\displaystyle 20 \mid 4$

🔗
$\displaystyle 0 \mid 5$

🔗
$\displaystyle 5 \mid 0$

🔗
$\displaystyle 7 \mid 7$

🔗
$\displaystyle 1 \mid 37$

🔗
$\displaystyle -3 \mid 12$

🔗
$\displaystyle 8 \mid 12$

🔗
$\displaystyle 1642 \mid 136299$

🔗

🔗

Penyelesaian.

Benar. 4 “termuat dalam” 20 sebanyak lima kali tanpa sisa. Dengan kata lain, $20 \div 4 = 5\text{,}$ yang merupakan bilangan bulat. Kita juga dapat membenarkannya dengan mengatakan bahwa $20$ merupakan kelipatan 4: $20 = 4\cdot 5\text{.}$
🔗

🔗
Salah. Meskipun 20 merupakan kelipatan 4, $4$ bukan kelipatan 20.
🔗

🔗
Salah. Tidak ada nilai bulat bagi peubah dalam persamaan $5 = 0\cdot k\text{.}$
🔗

🔗
Benar. Bahkan, $x \mid 0$ benar untuk setiap $x\text{.}$ Alasannya, 0 merupakan kelipatan setiap bilangan: $0 = x\cdot 0\text{.}$
🔗

🔗
Benar. Bahkan, $x \mid x$ benar untuk setiap $x\text{.}$
🔗

🔗
Benar. 1 membagi setiap bilangan, termasuk 0.
🔗

🔗
Benar. Bilangan negatif juga berlaku tanpa masalah dalam relasi keterbagian. Di sini, $12 = -3 \cdot 4\text{.}$ Selain itu, $3 \mid -12$ dan $-3 \mid -12$ juga benar.
🔗

🔗
Salah. Baik 8 maupun 12 habis dibagi 4, tetapi ini tidak berarti bahwa $12$ habis dibagi $8\text{.}$
🔗

🔗
Salah. Lihat pembahasan berikut.
🔗

🔗

🔗

Contoh terakhir ini menimbulkan pertanyaan: Bagaimana kita dapat menentukan apakah $m \mid n\text{?}$ Tentu saja, jika Anda memiliki kalkulator yang tepercaya, Anda dapat menggunakannya untuk menghitung $n \div m\text{.}$ Jika hasilnya bukan bilangan bulat, Anda tahu bahwa $m \nmid n\text{.}$ Namun, cara ini terasa sedikit curang: kita belum memiliki pembagian, jadi apakah kita patut menggunakan pembagian untuk memeriksa keterbagian?

🔗

Meskipun kita belum benar-benar tahu cara membagi, kita tahu cara mengalikan. Kita dapat mencoba mengalikan $m$ dengan bilangan-bilangan yang semakin besar hingga hasilnya mendekati $n\text{.}$ Seberapa dekat? Kita ingin memastikan bahwa jika $m$ dikalikan dengan bilangan bulat berikutnya yang lebih besar, hasilnya akan melampaui $n\text{.}$

🔗

Sebagai contoh, mari gunakan cara ini untuk menentukan apakah $1642 \mid 136299\text{.}$ Mulailah dengan mencari kelipatan 1642:

\begin{equation*} 1642 \cdot 2 = 3284 \qquad 1642 \cdot 3 = 4926 \qquad 1642\cdot 4 = 6568 \qquad \cdots\text{.} \end{equation*}

🔗

Semua hasil ini masih jauh lebih kecil daripada 136299. Kita dapat melompat sedikit lebih jauh:

\begin{equation*} 1642 \cdot 50 = 82100 \qquad 1642 \cdot 80 = 131360 \qquad 1642 \cdot 85 = 139570\text{.} \end{equation*}

🔗

Jadi, kita perlu memeriksa bilangan di antara 80 dan 85. Cobalah 83:

\begin{equation*} 1642 \cdot 83 = 136286\text{.} \end{equation*}

🔗

Apakah ini hasil terbaik yang dapat kita peroleh? Seberapa jauh hasil ini dari 136299 yang kita inginkan? Dengan mengurangkan, kita memperoleh $136299 - 136286 = 13\text{.}$ Jadi, kita tahu bahwa pengali 84 tidak dapat digunakan karena hasilnya akan terlalu besar. Dengan kata lain, kita telah menemukan bahwa

\begin{equation*} 136299 = 83 \cdot 1642 + 13\text{.} \end{equation*}

🔗

Karena $13 \lt 1642\text{,}$ sekarang kita dapat memastikan bahwa $1642 \nmid 136299\text{.}$

🔗

Ternyata, proses yang kita lakukan di atas dapat diulangi untuk sembarang pasangan bilangan bulat dengan komponen kedua tidak nol. Dalam keadaan itu, kita selalu dapat menuliskan bilangan $a$ sebagai suatu kelipatan bilangan $b$ ditambah suatu sisa. Kita mengetahui hal ini karena sejak sekolah dasar kita telah mengenal pembagian dengan sisa. Cara di atas hanya menyatakannya dengan menggunakan perkalian. Karena sisa dapat ditemukan melalui suatu prosedur, fakta ini biasanya disebut algoritma pembagian:

🔗

Algoritma Pembagian.

Untuk sembarang bilangan bulat $a$ dan $b \ne 0\text{,}$ terdapat bilangan bulat $q,r$ yang unik sedemikian sehingga

\begin{equation*} a = qb + r \end{equation*}

dengan $r$ memenuhi $0 \le r \lt |b|\text{.}$

🔗

Gagasannya adalah bahwa kita selalu dapat mengambil kelipatan $b$ yang sesuai agar sisa $r$ sekecil mungkin. Kita juga mengizinkan kemungkinan $r = 0\text{;}$ dalam hal ini, berlaku $b \mid a\text{.}$

🔗

Subbagian Kelas Sisa

Algoritma pembagian menyatakan bahwa hanya ada $|b|$ kemungkinan sisa ketika membagi dengan $b \ne 0\text{.}$ Jika pembagi tak nol ini ditetapkan, kita dapat mengelompokkan bilangan bulat berdasarkan sisanya. Setiap kelompok disebut kelas sisa modulo $b$ (atau kadang-kadang kelas residu).

🔗

Contoh 6.2.2.

Deskripsikan kelas-kelas sisa modulo $5\text{.}$

🔗

Penyelesaian.

Kita ingin mengelompokkan bilangan berdasarkan sisa pembagiannya oleh $5\text{.}$ Berdasarkan algoritma pembagian, kita tahu bahwa akan ada tepat 5 kelas sisa karena hanya ada 5 kemungkinan nilai $r$ ($0 \le r \lt 5$).

🔗

Mula-mula, perhatikan $r = 0\text{.}$ Di sini, kita mencari semua bilangan yang habis dibagi $5$ karena $a = 5q+0\text{.}$ Dengan kata lain, kita mencari kelipatan 5. Kita memperoleh himpunan tak berhingga

\begin{equation*} \{\ldots, -15, -10, -5, 0, 5, 10, 15, 20, \ldots\}\text{.} \end{equation*}

🔗

Perhatikan bahwa kita juga menyertakan bilangan bulat negatif.

🔗

Selanjutnya, perhatikan $r = 1\text{.}$ Bilangan bulat apa yang bersisa 1 ketika dibagi 5? Jelas bahwa 1, 6, dan 11 memenuhi. Bagaimana dengan bilangan negatif? Di sini kita harus berhati-hati: $-6$ TIDAK bersisa 1. Kita dapat menulis $-6 = -2\cdot 5 + 4$ atau $-6 = -1 \cdot 5 - 1\text{,}$ tetapi hanya salah satunya yang merupakan penerapan algoritma pembagian yang “benar”, yaitu $r = 4\text{,}$ karena $r$ harus tak negatif. Jadi, untuk memperoleh $r = 1\text{,}$ kita justru memiliki $-4\text{,}$ $-9\text{,}$ dan seterusnya. Dengan demikian, kita memperoleh kelas sisa

\begin{equation*} \{\ldots, -14, -9, -4, 1, 6, 11, 16, 21, \ldots\}\text{.} \end{equation*}

🔗

Masih ada tiga kelas lagi. Kelas-kelas sisa untuk $2\text{,}$ $3\text{,}$ dan $4$ berturut-turut adalah

\begin{equation*} \{\ldots, -13, -8, -3, 2, 7, 12, 17, 22,\ldots\} \end{equation*}

\begin{equation*} \{\ldots, -12, -7, -2, 3, 8, 13, 18, 23, \ldots\} \end{equation*}

\begin{equation*} \{\ldots, -11, -6, -1, 4, 9, 14, 19, 24, \ldots\}\text{.} \end{equation*}

🔗

Perhatikan bahwa dalam contoh di atas, setiap bilangan bulat berada tepat dalam satu kelas sisa. Secara teknis, kita mengatakan bahwa kelas-kelas sisa modulo $b$ membentuk partisi dari himpunan bilangan bulat.

Kita dapat mengembangkan teori matematis tentang partisi, membuktikan pernyataan mengenai semua partisi secara umum, lalu menerapkan hasil tersebut pada kasus yang sedang kita bahas.

Fakta terpenting tentang partisi ialah bahwa suatu relasi ekuivalensi dapat didefinisikan dari sebuah partisi: relasi ini menghubungkan pasangan-pasangan bilangan dan berperilaku seperti relasi “sama dengan” dalam semua hal yang penting.

Sekali lagi, terdapat teori matematis tentang relasi ekuivalensi yang berlaku pada jauh lebih banyak kasus daripada yang kita bahas di sini. Lihat Subbagian .

🔗

Terlepas dari semua istilah teknis yang menarik tadi, gagasannya sebenarnya sangat sederhana. Jika dua bilangan berada dalam kelas sisa yang sama, keduanya dapat dianggap sama dalam arti tertentu. Artinya, keduanya sama jika ditinjau dari pembagian oleh $b$. Pada kasus $b = 5$ di atas, bilangan $8$ dan $23$ memang bukan bilangan yang sama, tetapi keduanya sama jika ditinjau dari pembagian oleh 5 karena sama-sama bersisa $3\text{.}$

🔗

Pembagi yang digunakan sangat menentukan: $8$ dan $23$ sama jika ditinjau dari pembagian oleh $5\text{,}$ tetapi tidak sama jika ditinjau dari pembagian oleh $7\text{,}$ karena $8$ bersisa 1 ketika dibagi 7, sedangkan 23 bersisa 2.

🔗

Dengan mempertimbangkan semua hal ini, mari kita perkenalkan suatu notasi. Kita ingin mengatakan bahwa $8$ dan 23 pada dasarnya sama, meskipun keduanya tidak sama. Menulis $8 = 23$ tentu keliru. Sebagai gantinya, kita menulis $8 \equiv 23\text{.}$ Namun, pernyataan ini tidak selalu benar. Pernyataan itu berlaku jika kita sedang mempertimbangkan pembagian oleh 5, sehingga pembagi tersebut perlu dicantumkan dalam notasi. Jadi, yang sebenarnya kita tulis adalah

\begin{equation*} 8 \equiv 23 \pmod{5} \end{equation*}

yang dibaca, “8 kongruen dengan 23 modulo 5” (atau cukup “mod 5”). Tentu saja, kita kemudian dapat mengamati bahwa

\begin{equation*} 8 \not\equiv 23 \pmod{7}\text{.} \end{equation*}

🔗

Kongruensi Modulo $n$.

Untuk modulus positif, kita mengatakan bahwa $a$ kongruen dengan $b$ modulo $n$, dan menulis

\begin{equation*} a \equiv b \pmod{n} \end{equation*}

apabila $a$ dan $b$ memiliki sisa yang sama ketika dibagi $n\text{.}$ Dengan kata lain, apabila $a$ dan $b$ berada dalam kelas sisa yang sama modulo $n\text{.}$

🔗

Banyak buku mendefinisikan kongruensi modulo $n$ dengan cara yang sedikit berbeda. Buku-buku tersebut menyatakan bahwa $a \equiv b \pmod{n}$ jika dan hanya jika $n \mid a-b\text{.}$ Dengan kata lain, dua bilangan kongruen modulo $n$ jika selisihnya merupakan kelipatan $n\text{.}$ Jadi, definisi mana yang benar? Ternyata tidak menjadi soal karena keduanya ekuivalen.

🔗

Untuk mengetahui alasannya, perhatikan dua bilangan $a$ dan $b$ yang kongruen modulo $n\text{.}$ Maka $a$ dan $b$ memiliki sisa yang sama ketika dibagi $n\text{.}$ Kita peroleh

\begin{equation*} a = q_1 n + r \qquad\qquad b = q_2 n + r\text{.} \end{equation*}

🔗

Di sini, kedua $r$ tersebut benar-benar sama. Perhatikan hasil yang diperoleh ketika kita mengambil selisih $a$ dan $b\text{:}$

\begin{equation*} a-b = q_1n + r - (q_2n + r) = q_1n - q_2 n = (q_1-q_2)n\text{.} \end{equation*}

🔗

Jadi, $a-b$ merupakan kelipatan $n\text{,}$ atau secara ekuivalen, $n \mid a-b\text{.}$

🔗

Sebaliknya, jika mula-mula kita mengasumsikan $n \mid a-b\text{,}$ sehingga $a-b = kn\text{,}$ perhatikan apa yang terjadi jika setiap suku dibagi $n\text{.}$ Pembagian $a$ oleh $n$ akan menyisakan suatu nilai, demikian pula pembagian $b$ oleh $n\text{.}$ Akan tetapi, pembagian $kn$ oleh $n$ akan bersisa 0. Selisih kedua sisa itu harus merupakan kelipatan modulus, sedangkan nilai mutlaknya lebih kecil daripada modulus. Satu-satunya kemungkinan adalah selisih 0; artinya, kedua sisa tersebut sama.

🔗

Dengan demikian, kita memperoleh:

🔗

Kongruensi dan Keterbagian.

Untuk sembarang bilangan bulat $a$ dan $b\text{,}$ serta bilangan bulat positif $n\text{,}$ berlaku

\begin{equation*} a \equiv b \pmod{n} \qquad \text{ jika dan hanya jika } \qquad n \mid (a-b)\text{.} \end{equation*}

🔗

Beralih antara kongruensi dan persamaan biasa juga akan berguna. Fakta di atas membantu kita melakukannya. Kita tahu bahwa $a \equiv b \pmod{n}$ jika dan hanya jika $n \mid a-b\text{,}$ yang pada gilirannya berlaku jika dan hanya jika $a-b = kn$ untuk suatu bilangan bulat $k\text{.}$ Dengan menyusun ulang persamaan itu, kita memperoleh $a = b + kn\text{.}$ Dengan kata lain, jika $a$ dan $b$ kongruen modulo $n\text{,}$ maka $a$ sama dengan $b$ ditambah suatu kelipatan $n\text{.}$ Hal ini sesuai dengan pengamatan sebelumnya bahwa semua bilangan dalam suatu kelas sisa tertentu mempunyai selisih yang sama terhadap kelipatan-kelipatan $n\text{.}$

🔗

Kongruensi dan Kesamaan.

Untuk sembarang bilangan bulat $a$ dan $b\text{,}$ serta bilangan bulat positif $n\text{,}$ berlaku

\begin{equation*} a \equiv b \pmod{n} \qquad \text{ jika dan hanya jika } \qquad a = b + kn \mbox{ untuk suatu bilangan bulat } k\text{.} \end{equation*}

🔗

Subbagian Sifat-Sifat Kongruensi

Sebelumnya kita mengatakan bahwa, dalam banyak hal penting, kongruensi modulo $n$ berperilaku sama seperti kesamaan. Secara khusus, kita dapat membuktikan bahwa kongruensi modulo $n$ merupakan relasi ekuivalensi, yang mengharuskan kita memeriksa tiga fakta berikut:

🔗

Kongruensi Modulo $n$ Merupakan Relasi Ekuivalensi.

Untuk sembarang bilangan bulat $a\text{,}$ $b\text{,}$ dan $c\text{,}$ serta sembarang bilangan bulat positif $n\text{,}$ pernyataan berikut berlaku:

🔗

$a \equiv a \pmod{n}\text{.}$

🔗
Jika $a \equiv b \pmod{n}\text{,}$ maka $b \equiv a \pmod{n}\text{.}$
🔗

🔗
Jika $a \equiv b \pmod{n}$ dan $b \equiv c \pmod{n}\text{,}$ maka $a \equiv c \pmod{n}\text{.}$
🔗

🔗

🔗

Dengan kata lain, kongruensi modulo $n$ bersifat refleksif, simetris, dan transitif, sehingga merupakan relasi ekuivalensi.

🔗

Luangkan waktu sejenak untuk meyakinkan diri bahwa setiap sifat di atas memang berlaku bagi kongruensi. Cobalah menjelaskan masing-masing sifat dengan menggunakan definisi berdasarkan sisa maupun definisi berdasarkan keterbagian.

🔗

Selanjutnya, perhatikan perilaku kongruensi ketika kita melakukan aritmetika dasar. Kita sudah tahu bahwa jika dua bilangan yang kongruen dikurangkan, hasilnya akan kongruen dengan 0 (yakni merupakan kelipatan $n$). Bagaimana jika suatu bilangan yang kongruen dengan 1 dijumlahkan dengan bilangan yang kongruen dengan 2? Apakah hasilnya akan kongruen dengan 3?

🔗

Kongruensi dan Aritmetika.

Misalkan $a \equiv b \pmod{n}$ dan $c \equiv d \pmod{n}\text{.}$ Maka pernyataan berikut berlaku:

🔗

$a+c \equiv b+d \pmod{n}\text{.}$

🔗
$a-c \equiv b-d \pmod{n}\text{.}$

🔗
$ac \equiv bd \pmod{n}\text{.}$

🔗

🔗

Fakta-fakta di atas mungkin tampak ditulis dengan cara yang agak janggal, tetapi gagasannya sederhana. Jika kita memiliki kongruensi yang benar lalu menambahkan hal yang sama pada kedua ruas, hasilnya tetap merupakan kongruensi yang benar. Ini terdengar seolah-olah kita menyatakan:

🔗

Jika $a \equiv b \pmod{n}\text{,}$ maka $a+c \equiv b+c \pmod{n}\text{.}$
🔗

🔗

Tentu saja pernyataan ini juga benar; ini merupakan kasus khusus ketika $c = d\text{.}$ Namun, hasil yang kita miliki berlaku secara lebih umum. Anggaplah kongruensi berarti “pada dasarnya sama.” Jika kita memiliki dua bilangan yang pada dasarnya sama, lalu menambahkan sesuatu yang juga pada dasarnya sama pada kedua ruas, hasilnya akan tetap pada dasarnya sama.

🔗

Hal ini tampak masuk akal. Namun, apakah benar demikian? Mari kita buktikan fakta pertama:

🔗

Bukti.

Misalkan $a \equiv b \pmod{n}$ dan $c \equiv d \pmod{n}\text{.}$ Ini berarti $a = b + kn$ dan $c = d + jn$ untuk bilangan bulat $k$ dan $j\text{.}$ Jumlahkan kedua persamaan ini:

\begin{equation*} a+c = b+d + kn + jn\text{.} \end{equation*}

🔗

Namun, $kn + jn = (k+j)n\text{,}$ yang merupakan kelipatan $n\text{.}$ Jadi, $a+c = b+d + (j+k)n\text{,}$ atau dengan kata lain, $a+c \equiv b+d \pmod{n}\text{.}$

🔗

Dua fakta lainnya dapat dibuktikan dengan cara serupa.

🔗

Salah satu akibat penting dari fakta-fakta mengenai kongruensi ini ialah bahwa pada dasarnya kita dapat mengganti sembarang bilangan dalam suatu kongruensi dengan bilangan lain yang kongruen dengannya. Berikut beberapa contoh untuk melihat bagaimana (dan mengapa) hal itu berlaku:

🔗

Contoh 6.2.3.

Tentukan sisa pembagian $3491$ oleh $9\text{.}$

🔗

Penyelesaian.

Kita dapat menggunakan pembagian bersusun, tetapi ada cara lain. Kita ingin menemukan $x$ sedemikian sehingga $x \equiv 3491 \pmod{9}\text{.}$ Sekarang, $3491 = 3000 + 400 + 90 + 1\text{.}$ Tentu saja, $90 \equiv 0 \pmod 9\text{,}$ sehingga kita dapat mengganti 90 dalam penjumlahan itu dengan 0. Mengapa hal ini dibenarkan? Sebenarnya, kita mengurangkan sesuatu yang “sama” dari kedua ruas:

\begin{equation*} \begin{aligned}x \amp \equiv 3000 + 400 + 90 + 1 \pmod 9 \\ - ~~ 0 \amp \equiv 90 \pmod 9 \\ x \amp \equiv 3000 + 400 + 0 + 1\pmod 9. \end{aligned} \end{equation*}

🔗

Selanjutnya, perhatikan bahwa $400 = 4 \cdot 100$ dan $100 \equiv 1 \pmod 9$ (karena $9 \mid 99$). Jadi, kita dapat mengganti 400 hanya dengan 4. Sekali lagi, kita menggunakan pernyataan bahwa unsur-unsur yang kongruen dapat saling menggantikan, tetapi sebenarnya kita menggunakan sifat 3 dalam aritmetika kongruensi: kita tahu bahwa $100 \equiv 1 \pmod{9}\text{,}$ sehingga dengan mengalikan kedua ruas dengan $4\text{,}$ kita memperoleh $400 \equiv 4 \pmod 9\text{.}$

🔗

Dengan cara serupa, kita dapat mengganti 3000 dengan 3 karena $1000 = 1 + 999 \equiv 1 \pmod 9\text{.}$ Dengan demikian, kongruensi semula menjadi

\begin{equation*} x \equiv 3 + 4 + 0 + 1 \pmod 9 \end{equation*}

\begin{equation*} x \equiv 8 \pmod 9\text{.} \end{equation*}

Jadi, pembagian $3491$ oleh 9 bersisa 8.

🔗

Contoh di atas semestinya meyakinkan Anda bahwa uji keterbagian oleh 9 yang terkenal memang benar: jumlah digit suatu bilangan bulat tak negatif dalam representasi desimal habis dibagi 9 jika dan hanya jika bilangan semula habis dibagi 9. Bahkan, sekarang kita mengetahui sesuatu yang lebih kuat: setiap bilangan bulat tak negatif kongruen dengan jumlah digit desimalnya modulo 9.

Hal ini juga berlaku untuk 3, tetapi tentu tidak berlaku untuk sembarang modulus secara umum.

🔗

Mari kita coba contoh lain.

🔗

Contoh 6.2.4.

Tentukan sisa pembagian $3^{123}$ oleh 7.

🔗

Penyelesaian.

Tentu saja, kita menggunakan kongruensi karena ingin mencari $x$ tak negatif terkecil sedemikian sehingga $x \equiv 3^{123} \pmod 7\text{.}$ Mula-mula, tuliskan $3^{123} = (3^3)^{41}\text{.}$ Kita peroleh:

\begin{equation*} 3^{123} = 27^{41} \equiv 6^{41} \pmod 7\text{,} \end{equation*}

karena $27 \equiv 6 \pmod 7\text{.}$ Perhatikan pula bahwa $6^2 = 36$ kongruen dengan 1 modulo 7. Dengan demikian, kita dapat menyederhanakannya lebih lanjut:

\begin{equation*} 6^{41} = 6\cdot (6^2)^{20} \equiv 6 \cdot 1^{20} \pmod 7\text{.} \end{equation*}

🔗

Namun, $1^{20} = 1\text{,}$ sehingga kita selesai:

\begin{equation*} 3^{123} \equiv 6 \pmod 7\text{.} \end{equation*}

🔗

Dalam contoh di atas, kita menggunakan fakta bahwa untuk setiap eksponen bilangan bulat tak negatif, jika $a \equiv b \pmod n\text{,}$ maka $a^p \equiv b^p \pmod n\text{.}$ Ini hanyalah penerapan sifat 3 secara berulang.

🔗

Sejauh ini, kita telah melihat cara menjumlahkan, mengurangkan, dan mengalikan dalam kongruensi. Bagaimana dengan pembagian? Ada alasan mengapa kita menunda pembahasannya. Ternyata, kita tidak dapat begitu saja melakukan pembagian. Dengan kata lain, meskipun $ad \equiv bd \pmod n\text{,}$ kita belum tentu memiliki $a \equiv b \pmod n\text{.}$ Sebagai contoh, perhatikan

\begin{equation*} 18 \equiv 42 \pmod 8\text{.} \end{equation*}

🔗

Kongruensi ini benar. Sekarang, $18$ dan $42$ sama-sama habis dibagi 6. Namun,

\begin{equation*} 3 \not\equiv 7 \pmod 8\text{.} \end{equation*}

🔗

Meskipun pembagian tadi tidak berlaku, perhatikan bahwa $3 \equiv 7 \pmod 4\text{.}$ Kita tidak dapat membagi $8$ dengan 6, tetapi kita dapat membagi 8 dengan faktor persekutuan terbesar dari $8$ dan $6\text{.}$ Apakah hal ini selalu berlaku?

🔗

Misalkan $ad \equiv bd \pmod n\text{.}$ Dengan kata lain, kita memiliki $ad = bd + kn$ untuk suatu bilangan bulat $k\text{.}$ Tentu saja, $ad$ habis dibagi $d\text{,}$ demikian pula $bd\text{.}$ Jadi, $kn$ juga harus habis dibagi $d\text{.}$ Jika $n$ dan $d$ tidak memiliki faktor persekutuan selain 1, kita harus memiliki $d \mid k\text{.}$ Namun, secara umum, jika kita mencoba membagi $kn$ dengan $d\text{,}$ kita tidak tahu apakah hasilnya akan berupa kelipatan bulat dari $n\text{.}$ Sebagian faktor dari $n$ mungkin ikut terbagi. Agar aman, mari kita bagi $n$ sebanyak mungkin. Ambil faktor terbesar yang dimiliki bersama oleh $d$ dan $n\text{,}$ lalu coret faktor tersebut dari $n\text{.}$ Faktor-faktor $d$ yang tersisa akan berasal dari $k\text{,}$ sehingga tidak ada masalah.

🔗

Faktor terbesar yang dimiliki bersama oleh $d$ dan $n$ disebut $\gcd(d,n)\text{,}$ yaitu faktor persekutuan terbesar (FPB). Dalam contoh di atas, $\gcd(6,8) = 2$ karena faktor terbesar yang dimiliki bersama oleh 6 dan 8 adalah 2.

🔗

Kongruensi dan Pembagian.

Misalkan keempat peubah dalam kongruensi berikut berupa bilangan bulat dan modulusnya positif: $ad \equiv bd \pmod n\text{.}$ Maka $a \equiv b \pmod{\frac{n}{\gcd(d,n)}}\text{.}$

🔗

Jika $d$ dan $n$ tidak memiliki faktor persekutuan selain 1, maka $\gcd(d,n) = 1\text{,}$ sehingga $a \equiv b \pmod n\text{.}$

🔗

Contoh 6.2.5.

Sederhanakan kongruensi berikut dengan menggunakan pembagian: (a) $24 \equiv 39 \pmod 5$ dan (b) $24 \equiv 39 \pmod{15}\text{.}$

🔗

Penyelesaian.

(a) $24$ dan $39$ sama-sama habis dibagi $3\text{,}$ sedangkan $3$ dan $5$ tidak memiliki faktor persekutuan selain 1, sehingga kita memperoleh

\begin{equation*} 8 \equiv 13 \pmod 5\text{.} \end{equation*}

🔗

(b) Sekali lagi, kita dapat membagi dengan 3. Namun, jika pembagian dilakukan begitu saja, kita memperoleh $8 \equiv 13 \pmod{15}\text{,}$ yang tidak lagi benar. Sebagai gantinya, kita juga harus membagi modulus 15 dengan faktor persekutuan terbesar dari $3$ dan $15\text{,}$ yaitu $3\text{.}$ Kita kembali memperoleh

\begin{equation*} 8 \equiv 13 \pmod 5\text{.} \end{equation*}

🔗

Subbagian Menyelesaikan Kongruensi

Setelah memiliki beberapa aturan aljabar yang mengatur relasi kongruensi, kita dapat mencoba mencari nilai peubah yang tidak diketahui dalam suatu kongruensi. Sebagai contoh, adakah nilai $x$ yang memenuhi

\begin{equation*} 3x + 2 \equiv 4 \pmod{5}\text{,} \end{equation*}

dan jika ada, berapakah nilainya?

🔗

Dalam contoh ini, karena modulusnya kecil, kita dapat mencoba setiap nilai $x$ yang mungkin. Sebenarnya hanya ada 5 nilai yang perlu dipertimbangkan karena setiap bilangan bulat yang memenuhi kongruensi dapat diganti dengan bilangan bulat lain yang kongruen dengannya modulo 5. Di sini, ketika $x = 4\text{,}$ kita memperoleh $3x + 2 = 14\text{,}$ yang memang kongruen dengan 4 modulo 5. Ini berarti bahwa $x = 9\text{,}$ $x = 14\text{,}$ $x = 19\text{,}$ dan seterusnya juga merupakan solusi karena, sebagaimana kita lihat di atas, mengganti suatu bilangan dalam kongruensi dengan bilangan yang kongruen tidak mengubah nilai kebenaran kongruensi tersebut.

🔗

Jadi, dalam contoh ini, cukup hitung $3x + 2$ untuk nilai-nilai $x \in \{0,1,2,3,4\}\text{.}$ Hasilnya berturut-turut adalah 2, 5, 8, 11, dan 14; hanya 14 yang kongruen dengan 4.

🔗

Mari kita lihat pula cara menyelesaikannya menggunakan aturan aljabar kongruensi. Jika modulusnya lebih besar, pendekatan ini jauh lebih sederhana daripada cara coba-coba. Pertama, kita tahu bahwa 2 dapat dikurangkan dari kedua ruas:

\begin{equation*} 3x \equiv 2 \pmod{5}\text{.} \end{equation*}

🔗

Kemudian, untuk membagi kedua ruas dengan 3, mula-mula kita tambahkan 0 pada kedua ruas. Tentu saja, pada ruas kanan kita ingin menuliskan 0 tersebut sebagai 10 (ya, $10$ memang setara dengan 0 karena keduanya kongruen modulo 5). Ini menghasilkan

\begin{equation*} 3x \equiv 12 \pmod{5}\text{.} \end{equation*}

🔗

Sekarang, bagi kedua ruas dengan 3. Karena $\gcd(3,5) = 1\text{,}$ kita tidak perlu mengubah modulus:

\begin{equation*} x \equiv 4 \pmod{5}\text{.} \end{equation*}

🔗

Perhatikan bahwa hasil ini sebenarnya memberikan solusi umum: bukan hanya $x = 4\text{,}$ melainkan $x$ dapat berupa sembarang bilangan yang kongruen dengan 4. Kita dapat membiarkannya dalam bentuk ini, atau menulis “$x = 4 + 5k$ untuk sembarang bilangan bulat $k\text{.}$”

🔗

Contoh 6.2.6.

Selesaikan kongruensi berikut untuk $x\text{.}$

🔗

$7x \equiv 12 \pmod{13}\text{.}$

🔗
$84x - 38 \equiv 79 \pmod{15}\text{.}$

🔗
$20x \equiv 23 \pmod{14}\text{.}$

🔗

🔗

Penyelesaian.

Di sini, kita hanya perlu membagi kedua ruas dengan 7. Tambahkan 13 berulang kali pada ruas kanan sampai kita memperoleh kelipatan 7 (menambahkan 13 sama dengan menambahkan 0, sehingga langkah ini sah). Kita memperoleh $25\text{,}$ $38\text{,}$ $51\text{,}$ $64\text{,}$ $77$ – berhasil. Jadi, kita memiliki:

\begin{equation*} \begin{aligned}7x \amp \equiv 12 \pmod{13} \\ 7x \amp \equiv 77 \pmod{13} \\ x \amp \equiv 11 \pmod{13}. \end{aligned} \end{equation*}

🔗

🔗
Di sini, karena terdapat bilangan yang lebih besar daripada modulus, kita dapat mereduksinya sebelum menerapkan operasi aljabar apa pun. Kita memiliki $84 \equiv 9 \pmod{15}\text{,}$ $38 \equiv 8 \pmod{15}\text{,}$ dan $79 \equiv 4 \pmod{15}\text{.}$ Dengan demikian,

\begin{equation*} \begin{aligned}84x - 38 \amp \equiv 79 \pmod{15} \\ 9x - 8 \amp \equiv 4 \pmod{15} \\ 9x \amp \equiv 12 \pmod{15} \\ 9x \amp \equiv 72 \pmod{15}. \end{aligned} \end{equation*}

Kita memperoleh 72 dengan menambahkan $0 \equiv 60 \pmod{15}$ pada kedua ruas kongruensi. Sekarang, bagi kedua ruas dengan 9. Namun, karena $\gcd(9, 15) = 3\text{,}$ modulusnya juga harus dibagi 3:

\begin{equation*} x \equiv 8 \pmod 5\text{.} \end{equation*}

Jadi, solusinya adalah nilai-nilai yang kongruen dengan 8, atau secara ekuivalen dengan 3, modulo 5. Ini berarti bahwa, dalam arti tertentu, terdapat 3 solusi modulo 15: 3, 8, dan 13. Kita dapat menuliskan solusinya sebagai berikut:

\begin{equation*} x \equiv 3 \pmod{15}; ~~ x \equiv 8 \pmod{15}; ~~x \equiv 13 \pmod{15}\text{.} \end{equation*}

🔗

🔗
Mula-mula, lakukan reduksi modulo 14:

\begin{equation*} 20x \equiv 23 \pmod{14} \end{equation*}

\begin{equation*} 6x \equiv 9 \pmod{14}\text{.} \end{equation*}

Sekarang kita dapat membagi kedua ruas dengan 3 atau mencoba menambah 9 dengan suatu kelipatan 14 agar memperoleh kelipatan 6. Jika kita membagi dengan 3, kita memperoleh

\begin{equation*} 2x \equiv 3 \pmod{14}\text{.} \end{equation*}

Sekarang, cobalah menambahkan kelipatan 14 pada 3 dengan harapan memperoleh bilangan yang dapat dibagi 2. Cara ini tidak akan berhasil! Setiap kali kita menambahkan 14 pada ruas kanan, hasilnya akan tetap ganjil. Kita tidak akan pernah memperoleh bilangan genap, sehingga tidak akan pernah dapat membaginya dengan 2. Jadi, kongruensi tersebut tidak memiliki solusi.

🔗

🔗

🔗

Kongruensi terakhir di atas menunjukkan bagaimana suatu kongruensi dapat tidak memiliki solusi. Sebenarnya, kita dapat langsung mengetahuinya. Perhatikan kongruensi semula:

\begin{equation*} 20x \equiv 23 \pmod{14}\text{.} \end{equation*}

🔗

Jika ditulis sebagai persamaan, kita memperoleh

\begin{equation*} 20x = 23 + 14k\text{,} \end{equation*}

atau secara ekuivalen $20x - 14k = 23\text{.}$ Kita dapat dengan mudah melihat bahwa persamaan ini tidak memiliki solusi bilangan bulat. Ruas kiri akan selalu genap, sedangkan ruas kanan ganjil. Masalah serupa muncul jika ruas kiri selalu habis dibagi oleh suatu bilangan yang tidak membagi ruas kanan.

🔗

Jadi, secara umum, untuk kongruensi

\begin{equation*} ax \equiv b \pmod{n}\text{,} \end{equation*}

jika $a$ dan $n$ habis dibagi oleh suatu bilangan yang tidak membagi $b\text{,}$ kongruensi tersebut tidak memiliki solusi. Bahkan, kita hanya perlu memeriksa FPB dari $a$ dan $n\text{.}$ Dengan demikian, pernyataan ini dapat ditulis secara lebih ringkas sebagai berikut:

🔗

Kongruensi Tanpa Solusi.

Jika $\gcd(a,n) \nmid b\text{,}$ maka $ax \equiv b \pmod{n}$ tidak memiliki solusi.

🔗

Subbagian Menyelesaikan Persamaan Diofantin Linear

Matematika diskret membahas situasi ketika banyaknya benda berupa bilangan bulat. Jadi, ketika ingin menyelesaikan persamaan, kita biasanya mencari solusi berupa bilangan bulat. Persamaan yang solusinya hanya dicari dalam bilangan bulat pertama kali dipelajari pada abad ketiga oleh matematikawan Yunani Diofantos dari Aleksandria, sehingga disebut persamaan Diofantin. Contoh persamaan Diofantin yang mungkin paling terkenal ialah $a^2 + b^2 = c^2\text{.}$ Solusi bilangan bulat dari persamaan ini disebut tripel Pythagoras. Secara umum, menyelesaikan persamaan Diofantin itu sulit (bahkan, dapat dibuktikan bahwa tidak ada algoritma umum untuk menentukan apakah suatu persamaan Diofantin memiliki solusi; hasil ini dikenal sebagai Teorema Matiyasevich). Kita akan membatasi pembahasan pada persamaan Diofantin linear, yang jauh lebih mudah ditangani.

🔗

Persamaan Diofantin.

Persamaan polinomial berkoefisien bilangan bulat dalam satu peubah atau lebih disebut persamaan Diofantin jika hanya solusi bilangan bulat yang dicari. Persamaan Diofantin linear berbentuk $a_1x_1 + a_2x_2 + \cdots + a_nx_n = b$ untuk konstanta $a_1,\ldots, a_n, b\text{.}$

🔗

Solusi persamaan Diofantin adalah solusi persamaan yang seluruh komponennya berupa bilangan bulat.

🔗

Kita telah memiliki alat yang diperlukan untuk menyelesaikan persamaan Diofantin linear. Sebagai contoh utama, kita akan membahas persamaan

\begin{equation*} 51x + 87y = 123\text{.} \end{equation*}

🔗

Strategi umumnya adalah mengubah persamaan menjadi kongruensi, lalu menyelesaikan kongruensi tersebut.

⁴

Ini tentu bukan satu-satunya cara yang dapat digunakan. Teknik yang lebih umum ialah menerapkan algoritma Euklides. Cara kita dapat sedikit lebih cepat dan disajikan di sini terutama untuk memberikan variasi.

Mari kita kerjakan contoh ini untuk melihat prosesnya.

🔗

Pertama, periksa apakah persamaan mungkin tidak memiliki solusi karena suatu pembagi dari $51$ dan $87$ tidak membagi $123\text{.}$ Sebenarnya, kita hanya perlu memeriksa apakah $\gcd(51, 87) \mid 123\text{.}$ FPB ini adalah 3, dan memang $3 \mid 123\text{.}$ Pada tahap ini, sebaiknya kita mengeluarkan faktor persekutuan terbesar tersebut. Jadi, kita akan menyelesaikan:

\begin{equation*} 17x + 29y = 41\text{.} \end{equation*}

🔗

Sekarang, perhatikan bahwa jika solusi memang ada, maka untuk nilai $x$ dan $y$ tersebut, kedua ruas persamaan harus memiliki sisa yang sama, apa pun pembagi yang digunakan. Secara khusus, jika kedua ruas dibagi 17, sisanya harus sama. Dengan demikian, kita dapat menulis

\begin{equation*} 17x + 29y \equiv 41 \pmod{17}\text{.} \end{equation*}

🔗

Kita memilih 17 karena $17x$ akan bersisa 0. Hal ini memungkinkan kita mereduksi kongruensi menjadi kongruensi dengan satu peubah saja. Kita juga dapat beralih ke kongruensi modulo 29, tetapi biasanya ada alasan yang baik untuk memilih bilangan yang lebih kecil karena pilihan ini memungkinkan kita mereduksi koefisien yang lain. Dalam kasus ini, kita mereduksi kongruensi sebagai berikut:

\begin{equation*} \begin{aligned}17x + 29y \amp \equiv 41 \pmod{17} \\ 0x + 12y \amp \equiv 7 \pmod{17} \\ 12 y \amp \equiv 24 \pmod{17} \\ y \amp \equiv 2 \pmod{17}. \end{aligned} \end{equation*}

🔗

Pada tahap ini, kita tahu bahwa $y = 2 + 17k$ akan memenuhi kongruensi tersebut untuk sembarang bilangan bulat $k\text{.}$ Jika tidak melakukan kesalahan, kita dapat menyubstitusikannya kembali ke persamaan Diofantin semula untuk mencari $x\text{:}$

\begin{equation*} \begin{aligned}17x + 29(2 + 17k) \amp = 41\\ 17x \amp = -17 - 29\cdot 17k\\ x \amp = -1-29k. \end{aligned} \end{equation*}

🔗

Sekarang kita telah menemukan semua solusi persamaan Diofantin tersebut. Untuk setiap $k\text{,}$ $x = -1-29k$ dan $y = 2 + 17k$ akan memenuhi persamaan. Kita dapat memeriksanya untuk beberapa kasus. Jika $k = 0\text{,}$ solusinya adalah $(-1,2)\text{,}$ dan memang $-17 + 2\cdot 29 = 41\text{.}$ Jika $k = 3\text{,}$ solusinya adalah $(-88, 53)\text{.}$ Jika $k = -2\text{,}$ kita memperoleh $(57, -32)\text{.}$

🔗

Sebagai rangkuman, untuk menyelesaikan $ax + by = c$ dengan kedua koefisien tak nol, kita dapat mengubah tanda peubah jika perlu agar kedua koefisien positif, lalu melakukan langkah-langkah berikut.

🔗

Bagi kedua ruas persamaan dengan $\gcd(a,b)$ (jika ruas kanan tidak menjadi bilangan bulat, persamaan tidak memiliki solusi). Untuk langkah-langkah selanjutnya, asumsikan bahwa $ax + by = c$ sudah direduksi dengan cara ini.
🔗

🔗
Pilih yang lebih kecil di antara $a$ dan $b$ (di sini, asumsikan yang lebih kecil adalah $b$), lalu ubah menjadi kongruensi modulo $b\text{:}$

\begin{equation*} ax + by \equiv c \pmod{b}\text{.} \end{equation*}

Bentuk ini akan tereduksi menjadi kongruensi dengan satu peubah, yaitu $x\text{:}$

\begin{equation*} ax \equiv c \pmod{b}\text{.} \end{equation*}

🔗

🔗
Selesaikan kongruensi sebagaimana dilakukan pada bagian sebelumnya. Tuliskan solusi sebagai persamaan, misalnya

\begin{equation*} x = n + kb\text{.} \end{equation*}

🔗

🔗
Substitusikan hasil ini ke persamaan Diofantin semula, lalu selesaikan untuk $y\text{.}$
🔗

🔗
Jika kita ingin mengetahui solusi dalam rentang tertentu (misalnya, $0 \le x, y \le 20$), pilih berbagai nilai $k$ hingga semua solusi yang diminta ditemukan.
🔗

🔗

🔗

Berikut contoh lainnya:

🔗

Contoh 6.2.7.

Bagaimana Anda dapat membentuk nilai US$6,37 hanya dengan perangko 5 sen dan 8 sen? Berapakah jumlah perangko paling sedikit dan paling banyak yang dapat digunakan?

🔗

Penyelesaian.

Pertama, kita memerlukan persamaan Diofantin. Kita akan menggunakan satuan sen. Misalkan $x$ adalah banyaknya perangko $5$ sen dan $y$ adalah banyaknya perangko 8 sen. Kita memperoleh:

\begin{equation*} 5x + 8y = 637\text{.} \end{equation*}

🔗

Ubah menjadi kongruensi dan selesaikan:

\begin{equation*} \begin{aligned}8y \amp \equiv 637 \pmod{5}\\ 3y \amp \equiv 2 \pmod 5\\ 3y \amp \equiv 12 \pmod 5\\ y \amp \equiv 4 \pmod 5. \end{aligned} \end{equation*}

🔗

Dengan demikian, $y = 4 + 5k\text{.}$ Selanjutnya, $5x + 8(4+5k) = 637\text{,}$ sehingga $x = 121 - 8k\text{.}$

🔗

Ini menyatakan bahwa salah satu cara membentuk nilai US$6,37 adalah menggunakan 121 perangko 5 sen dan 4 perangko 8 sen. Untuk mencari jumlah perangko paling sedikit dan paling banyak, cobalah berbagai nilai $k\text{.}$

🔗

$k$	$(x,y)$	Jumlah perangko

-1	(129, -1)	tidak mungkin
0	(121, 4)	125
1	(113, 9)	122
2	(105, 14)	119
$\vdots$	$\vdots$	$\vdots$

Hasil ini tidak mengejutkan. Jumlah perangko terbanyak diperoleh ketika kita menggunakan sebanyak mungkin perangko 5 sen, sedangkan jumlah perangko paling sedikit mengharuskan kita menggunakan sesedikit mungkin perangko 5 sen. Untuk meminimalkan banyaknya perangko 5 sen, kita ingin memilih $k$ agar $121-8k$ sekecil mungkin (tetapi tetap tak negatif). Ketika $k = 15\text{,}$ kita memiliki $x = 1$ dan $y = 79\text{.}$

🔗

Jadi, untuk membentuk nilai US$6,37, Anda dapat menggunakan sedikitnya 80 perangko (1 perangko 5 sen dan 79 perangko 8 sen) atau sebanyak-banyaknya 125 perangko (121 perangko 5 sen dan 4 perangko 8 sen).

🔗

Dengan metode ini, selama Anda dapat menyelesaikan kongruensi linear dalam satu peubah, Anda dapat menyelesaikan persamaan Diofantin linear dalam dua peubah. Namun, adakalanya penyelesaian kongruensi linear memerlukan banyak pekerjaan. Sebagai contoh, misalkan Anda perlu menyelesaikan

\begin{equation*} 13x \equiv 6 \pmod{51}\text{.} \end{equation*}

🔗

Anda dapat terus menambahkan 51 pada ruas kanan sampai memperoleh kelipatan 13: hasilnya adalah 57, 108, 159, 210, 261, 312, dan 312 merupakan bilangan pertama dalam daftar ini yang habis dibagi 13. Cara ini berhasil, tetapi benar-benar terlalu merepotkan. Sebagai gantinya, kita dapat mengubahnya kembali menjadi persamaan Diofantin:

\begin{equation*} 13x = 6 + 51k\text{.} \end{equation*}

🔗

Sekarang, selesaikan persamaan ini seperti yang telah dilakukan dalam bagian ini. Tuliskan sebagai kongruensi modulo 13:

\begin{equation*} \begin{aligned}0 \amp \equiv 6 + 51k \pmod{13}\\ -12k \amp \equiv 6 \pmod{13}\\ 2k \amp \equiv -1 \pmod{13}\\ 2k \amp \equiv 12 \pmod{13}\\ k \amp \equiv 6 \pmod{13}. \end{aligned} \end{equation*}

sehingga $k = 6 + 13j\text{.}$ Sekarang, kembali dan tentukan $x\text{:}$

\begin{equation*} \begin{aligned}13x \amp = 6 + 51(6+13j)\\ x \amp = 24 + 51j. \end{aligned} \end{equation*}

🔗

Tentu saja, Anda dapat beralih bolak-balik antara kongruensi dan persamaan Diofantin sebanyak yang diperlukan. Jika Anda hanya menggunakan teknik ini, pada dasarnya Anda akan mereplikasi algoritma Euklides, yaitu cara yang lebih baku untuk menyelesaikan persamaan Diofantin.

🔗

Latihan Latihan

1.

Misalkan $a\text{,}$ $b\text{,}$ dan $c$ adalah bilangan bulat. Buktikan bahwa jika $a \mid b\text{,}$ maka $a \mid bc\text{.}$

🔗

2.

Misalkan $a\text{,}$ $b\text{,}$ dan $c$ adalah bilangan bulat. Buktikan bahwa jika $a \mid b$ dan $a \mid c\text{,}$ maka $a \mid b+c$ dan $a \mid b-c\text{.}$

🔗

3.

Tuliskan kelas-kelas sisa untuk $n = 4\text{.}$

🔗

4.

Berapakah bilangan bulat positif $n$ terbesar sedemikian sehingga $16$ dan $25$ berada dalam kelas sisa yang sama modulo $n\text{?}$ Tuliskan kelas sisa yang memuat keduanya dan berikan contoh bilangan yang lebih besar dari 100 dalam kelas tersebut.

🔗

5.

Misalkan $a\text{,}$ $b\text{,}$ serta $c,d$ semuanya bilangan bulat; misalkan pula $n$ bilangan bulat positif. Buktikan bahwa jika $a \equiv b \pmod{n}$ dan $c \equiv d \pmod{n}\text{,}$ maka $a-c \equiv b-d \pmod{n}\text{.}$

🔗

6.

Tentukan sisa pembagian $3^{456}$ oleh

2.
🔗

🔗
5.
🔗

🔗
7.
🔗

🔗
9.
🔗

🔗

🔗

7.

Ulangi latihan sebelumnya, kali ini dengan menentukan sisa pembagian $2^{2019}$ oleh bilangan-bilangan yang sama.

🔗

8.

Tentukan kongruensi berikut yang memiliki solusi, lalu temukan semua solusinya (mulai dari 0 hingga satu kurang dari modulusnya) dengan cara coba-coba.

$4x \equiv 5 \pmod 6\text{.}$

🔗
$6x \equiv 3 \pmod 9\text{.}$

🔗
$x^2 \equiv 2 \pmod 4\text{.}$

🔗

🔗

9.

Tentukan kongruensi berikut yang memiliki solusi, lalu temukan semua solusinya (mulai dari 0 hingga satu kurang dari modulusnya) dengan cara coba-coba.

$4x \equiv 5 \pmod 7\text{.}$

🔗
$6x \equiv 4 \pmod 9\text{.}$

🔗
$x^2 \equiv 2 \pmod 7\text{.}$

🔗

🔗

10.

Selesaikan kongruensi $5x + 8 \equiv 11 \pmod{22}\text{.}$ Artinya, nyatakan solusi umumnya.

🔗

11.

Selesaikan kongruensi $6x \equiv 4 \pmod{10}\text{.}$

🔗

12.

Selesaikan kongruensi $4x \equiv 24 \pmod{30}\text{.}$

🔗

13.

Selesaikan kongruensi $341x \equiv 2941 \pmod{9}\text{.}$

🔗

Petunjuk.

Mula-mula, reduksikan setiap bilangan modulo 9; ini dapat dilakukan dengan menjumlahkan digit-digit bilangan tersebut.

🔗

14.

Saya sedang memikirkan suatu bilangan. Jika bilangan saya dikalikan 7, lalu ditambah 5, dan hasilnya dibagi 11, sisanya adalah 2. Berapakah sisa yang diperoleh jika bilangan semula dibagi 11?

🔗

15.

Selesaikan persamaan Diofantin linear berikut menggunakan aritmetika modular (nyatakan solusi umumnya).

\begin{equation*} 6x + 10y = 32\text{.} \end{equation*}

🔗

16.

Selesaikan persamaan Diofantin linear berikut menggunakan aritmetika modular (nyatakan solusi umumnya).

\begin{equation*} 17x + 8y = 31\text{.} \end{equation*}

🔗

17.

Selesaikan persamaan Diofantin linear berikut menggunakan aritmetika modular (nyatakan solusi umumnya).

\begin{equation*} 35x + 47y = 1\text{.} \end{equation*}

🔗

18.

Anda memiliki sebuah botol berkapasitas 13 oz dan sebuah botol berkapasitas 20 oz yang hendak digunakan untuk menakar tepat 2 oz. Anda hanya boleh mengisi sebuah botol sampai penuh, menuang air dari satu botol ke botol lain sampai botol pertama kosong atau botol kedua penuh, dan mengosongkan sebuah botol. Namun, persediaan air Anda terbatas. Jika air sudah masuk ke salah satu botol lalu dibuang, air itu hilang dan tidak dapat digunakan lagi. Berapa volume air paling sedikit yang harus tersedia pada awalnya agar tugas ini tetap dapat diselesaikan?

🔗

Petunjuk.

Selesaikan persamaan Diofantin $13x + 20 y = 2$ (mengapa?). Kemudian tentukan nilai $k$ (parameter dalam solusi) yang optimal.

🔗

Sblm Top Lnjt

\(k\)	\((x,y)\)	Jumlah perangko

-1	(129, -1)	tidak mungkin
0	(121, 4)	125
1	(113, 9)	122
2	(105, 14)	119
\(\vdots\)	\(\vdots\)	\(\vdots\)

Subbab 6.2 Pengantar Teori Bilangan

Subbagian Keterbagian

Relasi Keterbagian.

Contoh 6.2.1.

Algoritma Pembagian.

Subbagian Kelas Sisa

Contoh 6.2.2.

Kongruensi Modulo \(n\).

Kongruensi dan Keterbagian.

Kongruensi dan Kesamaan.

Subbagian Sifat-Sifat Kongruensi

Kongruensi Modulo \(n\) Merupakan Relasi Ekuivalensi.

Kongruensi dan Aritmetika.

Bukti.

Contoh 6.2.3.

Contoh 6.2.4.

Kongruensi dan Pembagian.

Contoh 6.2.5.

Subbagian Menyelesaikan Kongruensi

Contoh 6.2.6.

Kongruensi Tanpa Solusi.

Subbagian Menyelesaikan Persamaan Diofantin Linear

Persamaan Diofantin.

Contoh 6.2.7.

Latihan Latihan

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.