Misalkan $m \in \mathbb{N}$ dan $a, b \in \mathbb{Z}.$ $a$ dikatakan kongruen dengan $b$ modulo $m$ jika dan hanya jika $m \mid (a-b)$, atau ditulis $a \equiv b~(\text{mod}~m).$ Contoh 1: $34 \equiv 4~(\text{mod}~6)$ $($baca: $34$ kongruen dengan $4$ modulo $6),$ artinya $34$ dan $4$ dibagi $6$ bersisa sama, atau $6 \mid (34-4).$ Contoh 2: $7 \equiv -8~(\text{mod}~5)$ (baca: $7$ kongruen dengan $-8$ modulo $5$), lebih tepat dipahami dalam model keterbagian $5 \mid (7+8)$, atau bisa juga $7$ dan $-8$ dibagi $5$ menghasilkan sisa yang sama. Show
Kongruensi atau kesetaraan diformulasikan pertama kali oleh Carl Friedrich Gauss pada tahun 1790 dengan definisi $x \equiv r ~(\text{mod}~d)$ jika dan hanya jika $x-r = kd$ untuk suatu bilangan bulat $k.$ Sifat Distributif ModuloMisalkan $a, b \in \mathbb{Z}$ dan $n \in \mathbb{N}.$ Sifat distribusi modulo berikut berlaku. Sifat Keterhubungan ModuloBerikut ini merupakan beberapa sifat keterhubungan modulo yang sering dipakai untuk menyelesaikan soal kongruensi.
Berikut ini merupakan beberapa teorema yang sering dipakai dalam penyelesaian persoalan kongruensi modulo. Fermat, Euler, dan WilsonTeorema Kecil Fermat Teorema kecil Fermat (Fermat’s little theorem) adalah salah satu teorema dalam bidang teori bilangan yang merupakan bentuk khusus dari Teorema Euler. Teorema ini diformulasikan pada tahun 1640. Teorema ini disebut “teorema kecil” Fermat untuk membedakan “Teorema Terakhir” beliau. Kata “Fermat” diambil dari nama matematikawan Prancis, Pierre de Fermat (1607–1665). Teorema Kecil FermatMisalkan $p$ merupakan bilangan prima dan $a$ merupakan bilangan bulat. Dengan demikian, $a^p-a$ selalu habis dibagi oleh $p.$ Contoh: Teorema Euler Dalam teori bilangan, teorema Euler (Euler’s theorem) adalah generalisasi dari teorema kecil Fermat yang berkaitan dengan kongruensi modulo bilangan bulat. Kata “Euler” diambil dari nama matematikawan Swiss, Leonhard Euler (1707–1783). Teorema EulerMisalkan $n$ merupakan bilangan bulat positif dan $a$ merupakan bilangan bulat yang relatif prima dengan $n.$ Dengan demikian, Contoh: Teorema: Fungsi Phi EulerMisalkan $n$ adalah bilangan bulat positif dan bentuk faktorisasi primanya dinyatakan oleh $$n = a_1^{p_1} \cdot a_2^{p_2} \cdots a_i^{p_i}$$Banyaknya bilangan yang relatif prima dengan $n$ dinyatakan oleh $$\phi(n) = n \cdot \left(1-\dfrac{1}{a_1}\right) \cdot \left(1-\dfrac{1}{a_2}\right) \cdots \left(1-\dfrac{1}{a_i}\right).$$ Teorema Wilson Berapakah sisa pembagian dari Dalam buku yang dipublikasikan tahun 1770, seorang matematikawan Inggris bernama Edward Waring (1736–1798) menyatakan bahwa muridnya menemukan suatu konjektur, yaitu $(p-1)!+1$ habis dibagi oleh $p$ untuk setiap bilangan prima $p.$ Namun, tidak ada dari keduanya yang dapat membuktikan kebenaran Konjektur tersebut. Pada tahun 1771, Joseph Lagrange (1736–1813) berhasil membuktikan konjektur ini sehingga menjadi teorema. Meskipun demikian, teorema ini diberi nama teorema Wilson karena John Wilson (1741–1793) mencetuskannya terlebih dahulu. Uniknya, catatan sejarah membuktikan bahwa Leibniz mengetahui teorema ini semasa hidupnya, tetapi ia tidak pernah memublikasikannya. Selain itu, jauh di antara semuanya, matematikawan Arab, Ibn al-Haytham (965–1040) telah mengetahui dan membuktikan teorema ini. Teorema WilsonJika $p$ merupakan bilangan prima, maka $(p-1)! \equiv -1~(\text{mod}~p).$ Contoh: Invers Modulo Jika $a$ dan $m$ relatif prima dengan $m > 1,$ maka $a~(\text{mod}~m)$ memiliki invers. Bilangan bulat $a^{-1}$ disebut invers dari $a~(\text{mod}~m)$ jika $aa^{-1} \equiv 1~(\text{mod}~m).$ Untuk menemukan $a^{-1},$ kita harus membuat kombinasi linear dengan menggunakan algoritma Euclid dan pembalikannya seperti contoh-contoh berikut. Contoh 1:Carilah invers dari $4~(\text{mod}~7).$ Jelas bahwa $\text{FPB}(4, 7) = 1$ sehingga $(4, 7)$ relatif prima dan 4~(\text{mod}~7)$ memiliki invers. Contoh 2:Carilah invers dari $7~(\text{mod}~23).$ Jelas bahwa $\text{FPB}(7, 23) = 1$ sehingga $(7, 23)$ relatif prima dan $7~(\text{mod}~23)$ memiliki invers. Contoh 3:Carilah invers dari $14~(\text{mod}~48).$ Dapat diperiksa bahwa $\text{FPB}(14, 48) \neq 1$ sehingga $(14, 48)$ tidak relatif prima. Jadi, $14~(\text{mod}~48)$ tidak memiliki invers. Today QuoteJika kamu ingin menggapai mimpimu, carilah orang yang sudah berhasil menggapai mimpi itu dan belajarlah darinya. Baca: Materi, Soal, dan Pembahasan – Algoritma Euclid Berikut ini beberapa soal mengenai kongruensi modulo yang telah disertakan pembahasannya. Bagian PIlihan Ganda Soal Nomor 1Didefinisikan notasi $\left[x\right]_y = x~(\text{mod}~y)$. Nilai dari $$\left[8\right]_3 + \left[16\right]_5 + \left[24\right]_7 + \left[32\right]_9 + \left[40\right]_{11}$$adalah $\cdots \cdot$ Pembahasan Perhatikan bahwa $x~(\text{mod}~y)$ memiliki arti sisa hasil bagi $x$ setelah dibagi $y.$ Karena [collapse] Soal Nomor 2Sisa hasil bagi $2+7+12+\cdots+1.002$ oleh $5$ adalah $\cdots \cdot$ Pembahasan $2+7+12+\cdots+1.002$ merupakan deret aritmetika dengan banyak suku $n = 201.$ [collapse] Soal Nomor 3Hasil dari $(1+2+3+65+66+67+79$ $+80+81+99)~\text{mod}~4$ adalah $\cdots \cdot$ Pembahasan Cara yang lazim dipakai adalah jumlahkan dulu semua sukunya, lalu cari sisa hasil baginya oleh $4$, tetapi ini bisa jadi tidak efektif. Alternatif lain yang dapat digunakan adalah cari sisa hasil bagi oleh $4$ pada masing-masing suku pada deret, kemudian dijumlahkan. [collapse] Baca: Materi, Soal, dan Pembahasan – Persamaan Diophantine Soal Nomor 4Angka satuan dari $7^{2020}$ adalah $\cdots \cdot$ Pembahasan Cara 1: Menggunakan Pola [collapse] Soal Nomor 5Angka satuan dari $7^{7^7}$ adalah $\cdots \cdot$ Pembahasan Pertama, akan dicari dulu angka satuan dari $7^7$. [collapse] Soal Nomor 6Sisa hasil bagi $9^{42}-5^{42}$ oleh $7$ adalah $\cdots \cdot$ Pembahasan Dengan menggunakan sifat kongruensi modulo, diperoleh [collapse] Soal Nomor 7Angka satuan dari $357^5 \cdot 117^9$ adalah $\cdots \cdot$ Pembahasan Angka satuan dapat dicari dengan menggunakan modulo $10$. [collapse] Soal Nomor 8Sisa hasil bagi $4^{18} \cdot 19^{80}$ oleh $9$ adalah $\cdots \cdot$ Pembahasan Pertama, kita tentukan dulu sisa pembagian perpangkatan $4$ oleh $9.$ Dalam hal ini, $4^1 = 4$ dibagi $9,$ sisanya $4,$ $4^2 = 16$ dibagi $9,$ sisanya $7,$ dan seterusnya, atau dalam notasi modulo ditulis [collapse] Soal Nomor 9Banyak bilangan bulat di antara $1.000$ dan $3.000$ yang kongruen dengan $5~(\text{mod}~7)$ adalah $\cdots \cdot$ Pembahasan Misalkan $x \in \mathbb{Z}$ dengan $1.000 < x < 3.000$ dan $x \equiv 5~(\text{mod}~7).$ [collapse] Soal Nomor 10Sisa hasil bagi $17 + 177 + 1777 + \cdots + 1\underbrace{777\cdots7}_{\text{sebanyak 20 kali}}$ oleh $8$ adalah $\cdots \cdot$ Pembahasan Perhatikan bahwa [collapse] Soal Nomor 11Jika $8^{79} \equiv x~(\text{mod}~5)$ dan $0 \leq x \leq 4$, maka nilai $x = \cdots \cdot$ Pembahasan Perhatikan bahwa [collapse] Baca Juga: Perhitungan Modulo pada ISBN Soal Nomor 12Sisa hasil bagi $(1^2+2^2+3^2+\cdots+99^2)$ oleh $9$ adalah $\cdots \cdot$ Pembahasan Perhatikan bahwa [collapse] Soal Nomor 13Banyak nilai $n$ yang memenuhi $n \equiv -n~(\text{mod}~12)$ dengan $40 \leq n \leq 80$ adalah $\cdots \cdot$ Pembahasan Bentuk kongruensi $n \equiv -n~(\text{mod}~12)$ memiliki arti bahwa terdapat suatu bilangan bulat $k$ sehingga $$k = \dfrac{n-(-n)}{12} = \dfrac{2n}{12} = \dfrac16n.$$Agar $k$ bulat, $n$ haruslah bilangan berkelipatan $6$. Karena $40 \leq n \leq 80$, nilai $n$ yang memenuhi adalah anggota dari $$\{42, 48, 54, 60, 66, 72, 78\}.$$Jadi, banyak nilai $n$ yang memenuhi adalah $\boxed{7}$ [collapse] Soal Nomor 14Bilangan bulat positif terkecil $n$ yang memenuhi $617n \equiv 943n~(\text{mod}~18)$ adalah $\cdots \cdot$ Pembahasan Bentuk kongruensi $617n \equiv 943n~(\text{mod}~18)$ memiliki arti bahwa terdapat suatu bilangan bulat $k$ sehingga $$k = \dfrac{617n-943n}{18} = \dfrac{-326n}{18} = -\dfrac{163}{9}n.$$Agar $k$ bulat, $n$ haruslah bilangan berkelipatan $9.$ Bilangan bulat positif terkecil yang merupakan kelipatan $9$ adalah $\boxed{9}$ [collapse] Soal Nomor 15Sisa hasil bagi $11^{12}$ oleh $13$ adalah $\cdots \cdot$ Pembahasan Karena $13$ merupakan bilangan prima, dengan menggunakan teorema kecil Fermat, diperoleh [collapse] Soal Nomor 16Sisa hasil bagi dari $2^{2.017} + 0^{2.017} + 1^{2.017} + 7^{2.017}$ oleh $2.017$ adalah $\cdots \cdot$ Pembahasan Perhatikan bahwa $2017$ merupakan bilangan prima. [collapse] Soal Nomor 17Martha menuliskan senyawa glukosa (C6H12O6) berulang kali: “C6H12O6C6H12O6…”. Huruf atau angka yang dituliskan Martha pada urutan ke-$2^{2020}$ adalah $\cdots \cdot$ Pembahasan Martha menuliskan barisan karakter yang berulang setiap $7$ suku. Oleh karena itu, kita akan mencari sisa hasil bagi dari $2^{2020}$ oleh $7.$ [collapse] Soal Nomor 18Jika $2^{13.131}$ dibagi oleh $3^9$, maka sisanya adalah $\cdots \cdot$ Pembahasan Gunakan teorema Euler. Perhatikan bahwa untuk $n = 3^9,$ banyaknya bilangan bulat positif yang kurang dari $n$ dan relatif prima dengannya dinyatakan oleh [collapse] Bagian Uraian Soal Nomor 1Tentukan nilai kebenaran masing-masing pernyataan berikut. Pembahasan Perhatikan bahwa $x \equiv r ~(\text{mod}~d)$ jika dan hanya jika $x-r = kd$ untuk suatu bilangan bulat $k.$ [collapse] Soal Nomor 2Periksa kebenaran dari pernyataan berikut ini. Pembahasan Jawaban a) [collapse] Soal Nomor 3Carilah semua bilangan bulat di antara $-100$ dan $100$ (eksklusif) yang kongruen dengan $5 ~(\text{mod}~9).$ Pembahasan Misalkan $n$ merupakan bilangan bulat dengan $n \equiv 5 ~(\text{mod}~9).$ Menurut definisi, $n = 9k + 5$ untuk suatu bilangan bulat $k.$ Karena $-100 < n < 100,$ nilai minimum dan maksimum dari $k$ berturut-turut adalah $k_{\text{min}} = -11$ dan $k_{\text{maks}} = 10.$ Untuk masing-masing bilangan bulat $k$ dengan $-11\le k \le 10,$ diperoleh nilai $n$ yang memenuhi kriteria yang diminta, yaitu anggota dari $\{-94, -85, -76, \cdots, 86, 95\}.$ [collapse] Soal Nomor 4Diketahui barisan bilangan Pembahasan Diketahui barisan bilangan [collapse] Soal Nomor 5Dua bilangan asli dibagi $16$ berturut-turut menghasilkan sisa $11$ dan $14.$ Carilah sisa jika jumlah kedua bilangan asli tersebut Pembahasan Alternatif 1: Tanpa Modulo Alternatif 2: Dengan Modulo [collapse] Soal Nomor 6Tentukan himpunan bilangan bulat nonnegatif yang anggotanya kongruen dengan $122 ~(\text{mod}~7).$ Pembahasan Misalkan $n$ merupakan bilangan bulat nonnegatif yang kongruen dengan $122 ~(\text{mod}~7),$ atau ditulis $n \equiv 122 ~(\text{mod}~7).$ Ini berarti terdapat suatu bilangan bulat $k$ sehingga $n = 7k + 122.$ Nilai minimum $k$ agar $n \ge 0$ adalah $k_{\text{min}} = -17.$ Nilai $n$ ketika $k \in \{-17, -16, -15, \cdots\}$ dinyatakan sebagai anggota himpunan berikut. [collapse] Soal Nomor 7Tentukan himpunan bilangan bulat yang anggotanya habis dibagi $5$ dan kongruen dengan $2~(\text{mod}~6).$ Pembahasan Misalkan $n$ merupakan bilangan bulat yang habis dibagi $5$ dan kongruen dengan $2~(\text{mod}~6),$ atau ditulis $n \equiv 2 ~(\text{mod}~6).$ Ini berarti terdapat suatu bilangan bulat $k$ sehingga $n = 6k + 2.$ Agar $n$ habis dibagi $5,$ nilai $k$ yang mungkin adalah anggota dari $\{k \mid k=5m-2, m \in \mathbb{Z}\}.$ Dengan menggunakan nilai-nilai $k$ tersebut, nilai-nilai $n$ dituliskan sebagai anggota himpunan $\{\cdots, 20, 50, 80, 110, \cdots\}.$ [collapse] Soal Nomor 8Carilah bilangan bulat positif yang habis dibagi $7$ yang kongruen dengan $2 ~(\text{mod}~9).$ Pembahasan Misalkan $n$ merupakan bilangan bulat positif yang habis dibagi $7$ dan kongruen dengan $2~(\text{mod}~9),$ atau ditulis $n \equiv 2 ~(\text{mod}~9).$ Ini berarti terdapat suatu bilangan bulat $k$ sehingga $n = 9k+2.$ Agar $n$ positif dan habis dibagi $7,$ nilai $k$ yang mungkin adalah anggota dari $\{k \mid k=7m-1, m \in \mathbb{N}\}.$ Dengan menggunakan nilai-nilai $k$ tersebut, nilai-nilai $n$ dituliskan sebagai anggota himpunan $\{56, 119, 182, 245 \cdots\}.$ [collapse] Soal Nomor 9Berapakah sisa hasil bagi $$(34-14\times 25)\times (23 \times 18 + 87)$$oleh $5$? Pembahasan Dengan menggunakan sifat distributif modulo, diperoleh [collapse] Soal Nomor 10Carilah sisa setiap bilangan berikut jika dibagi oleh $5$. Pembahasan Jawaban a) [collapse] Soal Nomor 11Carilah sisa hasil baginya. Pembahasan Jawaban a) [collapse] Soal Nomor 12Buktikan bahwa jika $a \equiv 19~(\text{mod}~30),$ maka $3a \equiv 7~(\text{mod}~10).$ Pembahasan Misalkan $a \equiv 19~(\text{mod}~30).$ Dengan menggunakan sifat modulo, diperoleh [collapse] Soal Nomor 13Carilah semua solusi persamaan linear kongruensi berikut. Pembahasan Jawaban a) [collapse] Soal Nomor 14Carilah invers dari setiap ekspresi modulo berikut. Pembahasan Jawaban a) [collapse] Baca: Materi, Soal, dan Pembahasan – Teorema Sisa Cina Soal Nomor 15Tentukan sisa pembagian dari $\left(2.020\right)^{2.015^{2.014^{\cdots^{3^{2^{1}}}}}}$ oleh $101.$ Pembahasan Perhatikan bahwa $2020 \div 101 = 20$. Dengan menggunakan sifat distributif modulo, diperoleh [collapse] Soal Nomor 16Berapa sisa hasil bagi $$5 \times 55 \times 555 \times \underbrace{555\cdots55}_{5.555~\text{kali}}$$ oleh $100$? Pembahasan Dengan menggunakan sifat-sifat kongruensi modulo, diperoleh [collapse] Soal Nomor 17Diberikan $a_n = 6^n + 8^n$. Tentukan sisa pembagian $a_{2015}$ setelah dibagi oleh $49.$ Pembahasan Kita akan mencari $(6^{2015} + 8^{2015})~(\text{mod}~49).$ [collapse] Soal Nomor 18Tentukan banyaknya bilangan $n \in \{1, 2, 3, \cdots, 2009\}$ sehingga $4n^6 + n^3 + 5$ habis dibagi $7.$ Pembahasan Analisis setiap nilai $n$ yang kongruen dengan sisa hasil bagi oleh $7$ yang mungkin, yaitu $\{0, 1, 2, 3, 4, 5, 6\}$. [collapse] Soal Nomor 19Barisan Fibonacci adalah barisan dengan rumus $F_1 = F_2 = 1$ dan $F_{n+2} = F_{n+1} + F_n$ untuk setiap bilangan asli $n \geq 1.$ Tentukan sisanya jika $F_{2020}$ dibagi $5.$ Pembahasan Soal ini mengacu pada periode Pisano, yaitu periode barisan Fibonacci yang mengalami perulangan untuk modulo bilangan tertentu, dinotasikan $\pi(n) = k$ untuk modulo $n$ dan $k$ sebagai periode perulangannya. [collapse] Soal Nomor 20Buktikan bahwa jika bilangan bulat $a_1, a_2$, $\cdots, a_9$ tidak habis dibagi $3,$ maka $$a_1^2+a_2^2+\cdots+a_9^2 \equiv 0~(\text{mod}~3).$$ Pembahasan Misalkan bilangan bulat $a_1, a_2$, $\cdots, a_9$ tidak habis dibagi $3.$ Jika suatu bilangan bulat $x$ tidak habis dibagi $3,$ maka akan ada 2 kemungkinan, yaitu $x \equiv 1~(\text{mod}~3)$ atau $x \equiv 2~(\text{mod}~3),$ tetapi $x^2 \equiv 1^2 \equiv 2^2 \equiv 1~(\text{mod}~3).$ |