Misalkan $m$ merupakan bilangan asli. Bilangan bulat $a$ dikatakan kongruen (congruent) dengan bilangan bulat $b$ modulo $m$ jika dan hanya jika $m \mid (a-b)$, dan 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.
Kongruensi (congruence) 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 Modulo
Misalkan $a, b \in \mathbb{Z}$ dan $m \in \mathbb{N}.$ Sifat distributif modulo berikut berlaku.
$$\begin{aligned} 1. &~(a\pm b)~(\text{mod}~m) \equiv (a~(\text{mod}~m) \pm b ~(\text{mod}~m))~(\text{mod}~m). \\ 2. &~(ab)~(\text{mod}~m) \equiv (a~(\text{mod}~m) \cdot b~(\text{mod}~m))~(\text{mod}~m). \\ 3. &~a^b ~(\text{mod}~m) \equiv ((a~(\text{mod}~m))^b)~(\text{mod}~m)~\text{untuk}~b~\text{bilangan}~\text{bulat nonnegatif}. \end{aligned}$$
Sifat Keterhubungan Modulo
Berikut ini merupakan beberapa sifat keterhubungan modulo yang sering dipakai untuk menyelesaikan soal kongruensi.
- $a \equiv a ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m),$ maka $b \equiv a ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m)$ dan $b \equiv c ~(\text{mod}~m)$, maka $a \equiv c ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m)$, maka $ac \equiv bc ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m)$, maka $a+c \equiv b+c ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m)$ dan $c \equiv d ~(\text{mod}~m)$, maka $a+c \equiv b+d ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m)$ dan $c \equiv d ~(\text{mod}~m)$, maka $a-c \equiv b-d ~(\text{mod}~m).$
- Jika $a \equiv b ~(\text{mod}~m)$ dan $d \mid m,$ $d > 0,$ maka $a \equiv b ~(\text{mod}~d).$
- Jika $a \equiv b ~(\text{mod}~m)$ dan $c \equiv d ~(\text{mod}~m)$, maka $ac \equiv bd ~(\text{mod}~m).$
- $(am + b)^n \equiv b^n ~(\text{mod}~m)$ untuk setiap $n \in \mathbb{N}.$
- Jika $a \equiv b ~(\text{mod}~m)$, maka $a^n \equiv b^n ~(\text{mod}~m)$ untuk setiap bilangan asli $n.$
- Jika $a \equiv a ~(\text{mod}~m)$ dan $f$ merupakan fungsi polinomial dengan $$f(x) = \displaystyle \sum_{i=0}^n a_ix^i = a_nx^n + a_{n-1}x^{n-1}+a_{n-2}x^{n-2} + \cdots + a_2x^2 + a_1x + a_0$$ dan $a_i \in \mathbb{Z}$ untuk setiap $i \in \{0, 1, 2, \cdots, n\},$ maka $f(a) \equiv f(b)~(\text{mod}~m).$
Berikut ini merupakan beberapa teorema yang sering dipakai dalam penyelesaian persoalan kongruensi modulo.
Teorema 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 Fermat
Contoh:
Karena $11$ adalah bilangan prima, $2^{11}-2 = 2046$ habis dibagi $11$ berdasarkan teorema kecil Fermat.
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 Euler
$$a^{\phi(n)} \equiv 1~(\text{mod}~n)$$dengan $\phi(n)$ ($\phi$ dibaca phi) adalah fungsi phi Euler (Euler’s totient function), yaitu fungsi yang digunakan untuk menghitung banyaknya bilangan bulat positif kurang dari $n$ yang relatif prima dengan $n.$
Contoh:
Misalkan $a$ relatif prima dengan $10.$ Bilangan bulat positif yang kurang dari $10$ dan relatif prima dengan $10$ ada $4$, yakni anggota dari $\{1, 3, 7, 9\},$ sehingga $\phi(10) = 4$. Berdasarkan teorema Euler, diperoleh
$$a^4 \equiv 1~(\text{mod}~10).$$Dengan kata lain, angka satuan dari $a^4$ selalu $1.$
Teorema: Fungsi Phi Euler
Teorema Wilson
Berapakah sisa pembagian dari
$$\begin{aligned} & 1!~\text{dibagi}~2 \\ & 2!~\text{dibagi}~3 \\ & 4!~\text{dibagi}~5 \\ & 6!~\text{dibagi}~7 \\ & 10!~\text{dibagi}~11 \\ & 12!~\text{dibagi}~13 \end{aligned}$$dan seterusnya?
Dalam buku yang dipublikasikan pada 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 Wilson
Contoh:
Karena $13$ prima, haruslah $12! \equiv -1~(\text{mod}~13).$ Dengan kata lain, $12!$ dibagi $13$ sisanya adalah $12.$
Karena $41$ prima, haruslah $40! \equiv -1~(\text{mod}~41).$ Dengan kata lain, $40!$ dibagi $41$ sisanya adalah $40.$
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 Euclides 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.
Pertama, kita gunakan algoritma Euclid seolah-olah mencari FPB dari $4$ dan $7.$
$$\begin{aligned} 7 & = 1 \times 4 + 3 \\ 4 & = 1 \times 3 + 1 \\ 3 & = 1 \times 3 + 0 \end{aligned}$$Lakukan pembalikan algoritma seolah-olah mencari identitas Bézout.
$$\begin{aligned} 1 & = 4-1 \times 3 \\ & = 4-1 \times (7-1 \times 4) \\ & = \color{blue}{2} \times 4-1 \times 7 \end{aligned}$$Koefisien dari $4$ pada bentuk kombinasi linear terakhir merupakan invers yang kita cari. Jadi, $a^{-1} = 2$ dan jika diperiksa,
$$4(2) \equiv 8 \equiv 1~(\text{mod}~7)$$merupakan pernyataan yang benar.
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.
Pertama, kita gunakan algoritma Euclides seolah-olah mencari FPB dari $7$ dan $23.$
$$\begin{aligned} 23 & = 3 \times 7 + 2 \\ 7 & = 3 \times 2 + 1 \\ 2 & = 2 \times 1 + 0 \end{aligned}$$Lakukan pembalikan algoritma seolah-olah mencari identitas Bézout.
$$\begin{aligned} 1 & = 7-3 \times 2 \\ & = 7-3 \times (23-3 \times 7) \\ & = \color{blue}{10} \times 7-3 \times 23 \end{aligned}$$Koefisien dari $7$ pada bentuk kombinasi linear terakhir merupakan invers yang kita cari. Jadi, $a^{-1} = 10$ dan jika diperiksa,
$$7(10) \equiv 70 \equiv 1~(\text{mod}~23)$$merupakan pernyataan yang benar.
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 Quote
Baca: Materi, Soal, dan Pembahasan – Algoritma Euclides
Berikut ini beberapa soal mengenai kongruensi modulo yang telah disertakan pembahasannya.
Bagian PIlihan Ganda
Soal Nomor 1
Didefinisikan 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$
A. $12$ C. $18$ E. $21$
B. $15$ D. $20$
Perhatikan bahwa $x~(\text{mod}~y)$ memiliki arti sisa hasil bagi $x$ setelah dibagi $y.$ Karena
$$\begin{aligned} 8 & = 2 \times 3 + \color{red}{2} \\ 16 & = 3 \times 5 + \color{red}{1} \\ 24 & = 3 \times 7 + \color{red}{3} \\ 32 & = 3 \times 9 + \color{red}{5} \\ 40 & = 3 \times 11 + \color{red}{7}, \end{aligned}$$diperoleh
$$\begin{aligned} & \left[8\right]_3 + \left[16\right]_5 + \left[24\right]_7 + \left[32\right]_9 + \left[40\right]_{11} \\ & = 2+1+3+5+7 = 18. \end{aligned}$$Jadi, hasil dari penjumlahan sisa hasil baginya adalah $\boxed{18}.$
(Jawaban C)
Soal Nomor 2
Sisa hasil bagi $2+7+12+\cdots+1.002$ oleh $5$ adalah $\cdots \cdot$
A. $0$ C. $4$ E. $8$
B. $2$ D. $6$
$2+7+12+\cdots+1.002$ merupakan deret aritmetika dengan banyak suku $n = 201.$
Masing-masing suku pada deret tersebut bersisa $2$ jika dibagi $5.$ Dengan menggunakan sifat kongruensi modulo, diperoleh
$$\begin{aligned} 2+7+12+\cdots+1.002 & \equiv \underbrace{2+2+2+\cdots+2}_{\text{ada}~201} \\ & = 2(201) \\ & = 402 \\ & \equiv \color{blue}{2} ~(\text{mod}~5). \end{aligned}$$Jadi, sisa hasil bagi deret tersebut oleh $5$ adalah $\boxed{2}.$
(Jawaban B)
Soal Nomor 3
Hasil dari $(1+2+3+65+66+67+79$ $+80+81+99)~\text{mod}~4$ adalah $\cdots \cdot$
A. $0$ C. $2$ E. $4$
B. $1$ D. $3$
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.
$$\begin{aligned} (1+2+3+65+66+67+79+80+81+99) & \equiv (1+2+3+1+2+3+3+0+1+3) \\ & = 19 \\ & \equiv 3~(\text{mod}~4) \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{3}.$
(Jawaban D)
Baca: Materi, Soal, dan Pembahasan – Persamaan Diophantine
Soal Nomor 4
Angka satuan dari $7^{2.020}$ adalah $\cdots \cdot$
A. $1$ C. $5$ E. $9$
B. $3$ D. $7$
Cara 1: Menggunakan Pola
Perhatikan angka satuan dari perpangkatan $7$.
$$\begin{aligned} 7^1 & \to 7 \\ 7^2 & \to 9 \\ 7^3 & \to 3 \\ 7^4 & \to 1 \\ 7^5 & \to 7 \end{aligned}$$Tampak barisan satuan yang terbentuk berulang setiap $4$ suku, yaitu
$$\underbrace{7, 9, 3, 1}_{\text{berulang}}, 7, 9, 3, 1, 7, 9, \cdots.$$Karena $2020$ habis dibagi $4$, angka satuan dari $7^{2.020}$ sama dengan angka satuan dari $7^4$, yaitu $\boxed{1}.$
Cara 2: Menggunakan Modulo
Angka satuan dicari menggunakan modulo $10$.
$$\begin{aligned} 7^{2.020} & = (7^2)^{1.010} \\ & \equiv 9^{1.010} \\ & \equiv (-1)^{1010} \\ & = \color{blue}{1} ~(\text{mod}~10) \end{aligned}$$Jadi, angka satuan dari $7^{2.020}$ adalah $\boxed{1}.$
(Jawaban A)
Soal Nomor 5
Angka satuan dari $7^{7^7}$ adalah $\cdots \cdot$
A. $1$ C. $5$ E. $9$
B. $3$ D. $7$
Pertama, akan dicari dulu angka satuan dari $7^7$.
Perhatikan bahwa
$$\begin{aligned} 7^1 & \equiv 7 ~(\text{mod}~10) \\ 7^2 & \equiv 9 ~(\text{mod}~10) \\ 7^3 & \equiv 3 ~(\text{mod}~10) \\ 7^4 & \equiv 1 ~(\text{mod}~10) \end{aligned}$$sehingga kita peroleh
$$\begin{aligned} 7^7 & = 7^4 \cdot 7^3 \\ & \equiv 1 \cdot 3 \\ & = \color{blue}{3} ~(\text{mod}~10). \end{aligned}$$Jadi, angka satuan dari $7^7$ adalah $\boxed{3}.$
Dengan demikian, $7^{7^7} \equiv 7^3 \equiv 3 ~(\text{mod}~10).$
Jadi, angka satuan dari $7^{7^7}$ adalah $\boxed{3}.$
(Jawaban B)
Soal Nomor 6
Sisa hasil bagi $9^{42}-5^{42}$ oleh $7$ adalah $\cdots \cdot$
A. $0$ C. $2$ E. $5$
B. $1$ D. $3$
Dengan menggunakan sifat kongruensi modulo, diperoleh
$$\begin{aligned} 9^{42}-5^{42} & \equiv (2^{42}-5^{42}) \\ & = (2^3)^{14}-(5^3)^{14} \\ & = 8^{14}-125^{14} \\& \equiv 1^{14}-(-1)^{14} \\ & = 1-1 \\ & = 0~(\text{mod}~7). \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{0}.$
(Jawaban A)
Soal Nomor 7
Angka satuan dari $357^5 \cdot 117^9$ adalah $\cdots \cdot$
A. $1$ C. $5$ E. $9$
B. $3$ D. $7$
Angka satuan dapat dicari dengan menggunakan modulo $10$.
Sebelum itu, perhatikan bahwa angka satuan dari perpangkatan $7$ memiliki pola berulang: $7, 9, 3, 1.$ Dalam hal ini, $7^{14}$ memiliki satuan yang sama dengan $7^2.$ Dengan demikian, diperoleh
$$\begin{aligned} 357^5 \cdot 117^9 & \equiv 7^5 \cdot 7^9\\ & = 7^{14} \\ & \equiv 7^2 \\ & = 49 \\ & \equiv \color{red}{9}~(\text{mod}~10). \end{aligned}$$Jadi, angka satuan dari $357^5 \cdot 117^9$ adalah $\boxed{9}.$
(Jawaban E)
Soal Nomor 8
Sisa hasil bagi $4^{18} \cdot 19^{80}$ oleh $9$ adalah $\cdots \cdot$
A. $1$ C. $5$ E. $9$
B. $3$ D. $7$
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
$$\begin{aligned} 4^1 & \equiv 4 ~(\text{mod}~9) \\ 4^2 & \equiv 7 ~(\text{mod}~9) \\ 4^3 & \equiv 1 ~(\text{mod}~9). \end{aligned}$$Oleh karena itu, diperoleh
$$\begin{aligned} 4^{18} & \equiv (4^3)^6 \\ & \equiv 1^6 \\ & = 1 ~(\text{mod}~9). \end{aligned}$$Selanjutnya, akan dicari sisa pembagian $19^{80}$ oleh $9$. Perhatikan bahwa $19$ dibagi $9$ bersisa $1$ sehingga
$$\begin{aligned} 19 & \equiv 1 ~(\text{mod}~9) \\ \Rightarrow 19^{80} & \equiv 1^{80} ~(\text{mod}~9) \\ 19^{80} & \equiv 1 ~(\text{mod}~9). \end{aligned}$$Dengan demikian,
$$\begin{aligned} 4^{18} \cdot 19^{80} & \equiv 1 \cdot 1 \\ & = 1 ~(\text{mod}~9). \end{aligned}$$Jadi, sisa pembagiannya adalah $\boxed{1}.$
(Jawaban A)
Soal Nomor 9
Banyak bilangan bulat di antara $1.000$ dan $3.000$ yang kongruen dengan $5~(\text{mod}~7)$ adalah $\cdots \cdot$
A. $280$ D. $285$
B. $282$ E. $290$
C. $284$
Misalkan $x \in \mathbb{Z}$ dengan $1.000 < x < 3.000$ dan $x \equiv 5~(\text{mod}~7).$
Untuk suatu bilangan bulat $k$, berlaku
$$\begin{aligned} k & = \dfrac{x-5}{7} \\ 7k & = x-5 \\ x & = 7k+5. \end{aligned}$$Karena $x > 1.000,$ didapat
$$\begin{aligned} 7k + 5 & > 1.000 \\ 7k & > 995 \\ k & > 142,\cdots \\ k_{\text{min}} & = 143. \end{aligned}$$Karena $x < 3.000,$ didapat
$$\begin{aligned} 7k + 5 & < 3.000 \\ 7k & > 2.995 \\ k & > 427,\cdots \\ k_{\text{maks}} & = 427. \end{aligned}$$Banyak bilangan bulat dari $143$ sampai $427$ adalah $\text{n} = 427-143+1 = 285.$ Ini berarti ada $\boxed{285}$ bilangan bulat di antara $1.000$ dan $3.000$ yang kongruen dengan $5~(\text{mod}~7).$
(Jawaban D)
Soal Nomor 10
Sisa hasil bagi $17 + 177 + 1777 + \cdots + 1\underbrace{777\cdots7}_{\text{sebanyak 20 kali}}$ oleh $8$ adalah $\cdots \cdot$
A. $2$ C. $4$ E. $7$
B. $3$ D. $6$
Perhatikan bahwa
$$\begin{aligned} 17 & = 2 \times 8 + 1 \\ 177 & = 2 \times 88 + 1 \\ 1777 & = 2 \times 888 + 1 \\ & \vdots \end{aligned}$$Bilangan $8, 88, 888, \cdots$ semuanya habis dibagi $8$.
Dengan menggunakan sifat-sifat modulo, diperoleh
$$\begin{aligned} 17 + 177 + 1777 + \cdots + 1\underbrace{777\cdots7}_{\text{ada}~20} & \equiv \underbrace{1 + 1 + 1 + \cdots + 1}_{\text{ada}~20} \\ & = 20\\ & \equiv 4~(\text{mod}~8). \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{4}.$
(Jawaban C)
Soal Nomor 11
Jika $8^{79} \equiv x~(\text{mod}~5)$ dan $0 \leq x \leq 4$, maka nilai $x = \cdots \cdot$
A. $0$ C. $2$ E. $4$
B. $1$ D. $3$
Perhatikan bahwa
$$\begin{aligned} 8^{79} & \equiv 3^{79} \\ & = (3^{4})^{19} \cdot 3^3 \\ & \equiv 1^{19} \cdot 2 \\ & = 2~(\text{mod}~5). \end{aligned}$$Jadi, nilai $\boxed{x = 2}.$
(Jawaban C)
Baca Juga: Perhitungan Modulo pada ISBN
Soal Nomor 12
Sisa hasil bagi $(1^2+2^2+3^2+\cdots+99^2)$ oleh $9$ adalah $\cdots \cdot$
A. $1$ C. $5$ E. $9$
B. $3$ D. $7$
Perhatikan bahwa
$$\displaystyle \sum_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}.$$Untuk $n = 99$, diperoleh
$$\begin{aligned} 1^2+2^2+3^2+\cdots+99^2 & = \dfrac{99(99+1)(2(99)+1)}{6} \\ & = \dfrac{\cancelto{33}{99} \cdot \cancelto{50}{100} \cdot 199}{6} \\ & = 33 \cdot 50 \cdot 199. \end{aligned}$$Dengan demikian,
$$\begin{aligned} (1^2+2^2+3^2+\cdots+99^2) & \equiv 33 \cdot 50 \cdot 99 \\ & \equiv 6 \cdot 5 \cdot 1 \\ & = 30\\ & \equiv 3~(\text{mod}~9). \end{aligned}$$Jadi, sisa hasil baginya oleh $9$ adalah $\boxed{3}.$
(Jawaban B)
Soal Nomor 13
Banyak nilai $n$ yang memenuhi $n \equiv -n~(\text{mod}~12)$ dengan $40 \leq n \leq 80$ adalah $\cdots \cdot$
A. $4$ C. $7$ E. $10$
B. $6$ D. $8$
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}.$
(Jawaban C)
Soal Nomor 14
Bilangan bulat positif terkecil $n$ yang memenuhi $617n \equiv 943n~(\text{mod}~18)$ adalah $\cdots \cdot$
A. $3$ C. $9$ E. $18$
B. $7$ D. $12$
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}.$
(Jawaban C)
Soal Nomor 15
Sisa hasil bagi $11^{12}$ oleh $13$ adalah $\cdots \cdot$
A. $0$ C. $3$ E. $9$
B. $1$ D. $7$
Karena $13$ merupakan bilangan prima, dengan menggunakan teorema kecil Fermat, diperoleh $$11^{13} \equiv 11~(\text{mod}~13).$$Karena $\text{FPB}(11, 13) = 1,$ kedua ruas dapat dibagi dengan $11$ sehingga didapat
$$11^{12} \equiv 1~(\text{mod}~13).$$Jadi, sisa hasil bagi $11^{12}$ oleh $13$ adalah $\boxed{1}.$
(Jawaban D)
Soal Nomor 16
Sisa hasil bagi $16!$ oleh $19$ adalah $\cdots \cdot$
A. $5$ C. $9$ E. $13$
B. $7$ D. $11$
Perhatikan bahwa $19$ merupakan bilangan prima. Dengan menggunakan teorema Wilson, berlaku $18! \equiv 18~(\text{mod}~19).$ Dari sini, Anda akan peroleh
$$\begin{aligned} 18(17)(16!) & \equiv 18 ~(\text{mod}~19) \\ (-1)(-2)(16!) & \equiv 18 ~(\text{mod}~19) \\ 2(16!) & \equiv 18 ~(\text{mod}~19). \end{aligned}$$Karena $\text{FPB}(2, 19) = 1,$ kedua ruas dapat dibagi dengan $2$ sehingga didapat $16! \equiv 9~(\text{mod}~19).$ Jadi, sisa hasil bagi $16!$ oleh $19$ adalah $\boxed{9}.$
(Jawaban C)
Soal Nomor 17
Sisa hasil bagi $5!25!$ oleh $31$ adalah $\cdots \cdot$
A. $1$ C. $5$ E. $17$
B. $3$ D. $11$
Perhatikan bahwa $31$ merupakan bilangan prima. Dengan menggunakan teorema Wilson, berlaku $30! \equiv 30~(\text{mod}~31).$ Dengan demikian, didapat
$$\begin{aligned} 5!25! & = 5(4)(3)(2)(1)25! \\ & \equiv (-26)(-27)(-28)(-29)(-30)25! \\ & = (-1)^530! \\ & \equiv (-1)(30) \\ & \equiv 1~(\text{mod}~31). \end{aligned}$$Jadi, sisa hasil bagi $5!25!$ oleh $31$ adalah $\boxed{1}.$
(Jawaban A)
Soal Nomor 18
Sisa hasil bagi $$7 \cdot 8 \cdot 9 \cdot 15 \cdot 16 \cdot 17 \cdot 23 \cdot 24 \cdot 25 \cdot 43$$oleh $11$ adalah $\cdots \cdot$
A. $2$ C. $5$ E. $10$
B. $4$ D. $8$
Perhatikan bahwa $11$ merupakan bilangan prima sehingga menurut teorema Wilson, berlaku $10! \equiv 10~(\text{mod}~11).$ Dengan demikian, diperoleh
$$\begin{aligned} & 7 \cdot 8 \cdot 9 \cdot 15 \cdot 16 \cdot 17 \cdot 23 \cdot 24 \cdot 25 \cdot 43 \\ & \equiv 7 \cdot 8 \cdot 9 \cdot 4 \cdot 5 \cdot 6 \cdot 1 \cdot 2 \cdot 3 \cdot 10 \\ & = 10! \equiv 10~(\text{mod}~11). \end{aligned}$$Jadi, sisa hasil bagi bilangan tersebut oleh $11$ adalah $\boxed{10}.$
(Jawaban E)
Soal Nomor 19
Sisa hasil bagi $18!$ oleh $437$ adalah $\cdots \cdot$
A. $1$ C. $112$ E. $436$
B. $4$ D. $256$
Perhatikan bahwa $437 = 19 \cdot 23.$ Karena $19$ dan $23$ keduanya merupakan bilangan prima, berdasarkan teorema Wilson, diperoleh $18! \equiv -1~(\text{mod}~19)$ dan $22! \equiv 22~(\text{mod}~23).$ Sementara itu,
$$\begin{aligned} 22! & = 22(21)(20)(19)(18!) \\ & \equiv -1(-2)(-3)(-4)(18!) \\ & = 24(18!) \\ & \equiv 18!~(\text{mod}~23). \end{aligned}$$Dengan demikian, diperoleh dua kongruensi berikut.
$$\begin{cases} 18! & \equiv -1~(\text{mod}~19) \\ 18! & \equiv 22~(\text{mod}~23) \end{cases}$$Karena $\text{FPB}(19, 23) = 1,$ teorema sisa Cina dapat diterapkan untuk menyelesaikan sistem kongruensi linear berikut.
$$\begin{cases} x & \equiv -1~(\text{mod}~19) \\ x & \equiv 22~(\text{mod}~23) \end{cases}$$Untuk $M = 19 \times 23 = 437,$ diperoleh
$$\begin{aligned} M_1 & = \dfrac{437}{19} = 23 \\ M_2 & = \dfrac{437}{23} = 19. \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} y_1 & \equiv 23^{-1}~(\text{mod}~19) \\ & \equiv 5~(\text{mod}~19) \\ y_2 & \equiv 19^{-1}~(\text{mod}~23) \\ & \equiv -6~(\text{mod}~23). \end{aligned}$$sehingga
$$\begin{aligned} x & \equiv -1 \cdot 23 \cdot 5 + 22 \cdot 19 \cdot (-6) \\ & = -2.623 \\ & \equiv 436~(\text{mod}~437). \end{aligned}$$Jadi, sisa hasil bagi $18!$ oleh $437$ adalah $\boxed{436}.$
(Jawaban E)
Soal Nomor 20
Sisa hasil bagi $5^{100}$ oleh $7$ adalah $\cdots \cdot$
A. $1$ C. $3$ E. $5$
B. $2$ D. $4$
Karena $7$ merupakan bilangan prima dan $7 \nmid 5,$ teorema kecil Fermat dapat diterapkan, yaitu $5^{7-1} = 5^6 \equiv 1~(\text{mod}~7).$ Dengan menggunakan informasi tersebut, diperoleh
$$\begin{aligned} 5^{100} & = (5^6)^{16} \cdot 5^4 \\ & \equiv 1^{16} \cdot 5^2 \cdot 5^2 \\ & \equiv 1 \cdot 4 \cdot 4 \\ & \equiv 2~(\text{mod}~7). \end{aligned}$$Jadi, sisa hasil bagi $5^{100}$ oleh $7$ adalah $\boxed{2}.$
(Jawaban B)
Soal Nomor 21
Sisa hasil bagi $6^{2.000}$ oleh $11$ adalah $\cdots \cdot$
A. $0$ C. $2$ E. $4$
B. $1$ D. $3$
Karena $11$ merupakan bilangan prima dan $11 \nmid 6,$ teorema kecil Fermat dapat diterapkan, yaitu $6^{11-1} = 6^{10} \equiv 1~(\text{mod}~11).$ Dengan menggunakan informasi tersebut, diperoleh
$$\begin{aligned} 6^{2.000} & = (6^{10})^{200} \\ & \equiv 1^{200} \\ & = 1~(\text{mod}~11). \end{aligned}$$Jadi, sisa hasil bagi $6^{2.000}$ oleh $11$ adalah $\boxed{1}.$
(Jawaban B)
Soal Nomor 22
Sisa hasil bagi dari $2^{2.017} + 0^{2.017} + 1^{2.017} + 7^{2.017}$ oleh $2.017$ adalah $\cdots \cdot$
A. $0$ C. $3$ E. $10$
B. $1$ D. $5$
Perhatikan bahwa $2017$ merupakan bilangan prima.
Dengan menggunakan teorema kecil Fermat yang menyatakan bahwa $a^p \equiv a~(\text{mod}~p)$ untuk setiap bilangan prima $p,$ diperoleh
$$\begin{aligned} 2^{2.017} + 0^{2.017} + 1^{2.017} + 7^{2.017}) & \equiv 2 + 0 + 1 + 7 \\ & = 10~(\text{mod}~2.017). \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{10}.$
(Jawaban E)
Soal Nomor 23
Martha menuliskan senyawa glukosa (C6H12O6) berulang kali: “C6H12O6C6H12O6…”. Huruf atau angka yang dituliskan Martha pada urutan ke-$2^{2020}$ adalah $\cdots \cdot$
A. $1$ C. C E. O
B. $6$ D. H
Martha menuliskan barisan karakter yang berulang setiap $7$ suku. Oleh karena itu, kita akan mencari sisa hasil bagi dari $2^{2020}$ oleh $7.$
$$\begin{aligned} 2^{2020} & = (2^3)^{673} \cdot 2 \\ & = 8^{673} \cdot 2 \\ & \equiv 1^{673} \cdot 2 \\ & = 2~\text{mod}~7 \end{aligned}$$Jadi, sisa hasil bagi $2^{2020}$ oleh $7$ adalah $2$. Artinya, kita mencari suku ke-$2$ dari $7$ suku di barisan tersebut, yaitu $\boxed{6}.$
(Jawaban B)
Soal Nomor 24
Jika $2^{13.131}$ dibagi oleh $3^9$, maka sisanya adalah $\cdots \cdot$
A. $64$ D. $512$
B. $128$ E. $1.024$
C. $256$
Gunakan teorema Euler. Perhatikan bahwa untuk $n = 3^9.$ Banyaknya bilangan bulat positif yang kurang dari $n$ dan relatif prima dengannya dinyatakan oleh
$$\begin{aligned} \phi(n) & = \phi(3^9) \\ & = 3^9 \cdot \left(1-\dfrac13\right) \\ & = 2 \cdot 3^8. \end{aligned}$$Karena $2$ relatif prima dengan $3^9,$ menurut teorema Euler, berlaku
$$\begin{aligned} 2^{\phi(n)} &\equiv 1~(\text{mod}~3^9) \\ 2^{2 \cdot 3^8} & \equiv 1~(\text{mod}~3^9) \\ 2^{13.122} & \equiv 1~(\text{mod}~3^9)\\ 2^{13.122} \cdot 2^9 & \equiv 1 \cdot 2^9~(\text{mod}~3^9) \\ 2^{13.131} & \equiv 512~(\text{mod}~3^9). \end{aligned}$$Jadi, sisa hasil bagi $2^{13.131}$ oleh $3^9$ adalah $\boxed{512}.$
(Jawaban D)
Bagian Uraian
Soal Nomor 1
Tentukan nilai kebenaran masing-masing pernyataan berikut.
a. $76 \equiv -152~(\text{mod}~3).$
b. $721 \equiv -484 ~(\text{mod}~5).$
c. $118 \equiv 25 ~(\text{mod}~13).$
d. $2.401 \equiv 147 ~(\text{mod}~49).$
e. $183 \equiv 291 ~(\text{mod}~6).$
f. $2.701 \equiv 14.393 ~(\text{mod}~8).$
g. $493 \equiv 873 ~(\text{mod}~10).$
h. $4.113 \equiv 396 ~(\text{mod}~9).$
Perhatikan bahwa $x \equiv r ~(\text{mod}~d)$ jika dan hanya jika $x-r = kd$ untuk suatu bilangan bulat $k.$
Jawaban a)
$76 \equiv -152 ~(\text{mod}~3)$ merupakan pernyataan yang benar karena terdapat $k = 76 \in \mathbb{Z}$ sehingga $76-(-152) = 228 = \underbrace{76}_{k}(3).$
Jawaban b)
$721 \equiv -484 ~(\text{mod}~5)$ merupakan pernyataan yang benar karena terdapat $k = 241 \in \mathbb{Z}$ sehingga $721-(-484) = 1.205 = \underbrace{241}_{k}(3).$
Jawaban c)
$118 \equiv 25 ~(\text{mod}~13)$ merupakan pernyataan yang salah karena tidak terdapat $k \in \mathbb{Z}$ yang memenuhi persamaan $118-25 = 93 = 13k.$
Jawaban d)
$2.401 \equiv 147 ~(\text{mod}~49)$ merupakan pernyataan yang benar karena terdapat $k = 46 \in \mathbb{Z}$ sehingga $2.401-147 = 2.254 = \underbrace{46}_{k}(49).$
Jawaban e)
$183 \equiv 291 ~(\text{mod}~6)$ merupakan pernyataan yang benar karena terdapat $k = -18 \in \mathbb{Z}$ sehingga $183-291 = -108 = \underbrace{-18}_{k}(6).$
Jawaban f)
$2.701 \equiv 14.393 ~(\text{mod}~8)$ merupakan pernyataan yang salah karena tidak terdapat $k \in \mathbb{Z}$ yang memenuhi persamaan $2.701-14.393 = -11.692 = 8k.$
Jawaban g)
$493 \equiv 873 ~(\text{mod}~10)$ merupakan pernyataan yang benar karena terdapat $k = -38 \in \mathbb{Z}$ sehingga $493-873 = -380 = \underbrace{-38}_{k}(10).$
Jawaban h)
$4.113 \equiv 396 ~(\text{mod}~9)$ merupakan pernyataan yang benar karena terdapat $k = 413 \in \mathbb{Z}$ sehingga $4.113-396=3.717 = \underbrace{413}_{k}(9).$
Soal Nomor 2
Periksa kebenaran dari pernyataan berikut ini.
a. $(73 + 89) \equiv (3 + 9) \equiv 2~(\text{mod}~10).$
b. $(93-47) \equiv (3-2)~(\text{mod}~9).$
c. $(403 + 497) \equiv (3 + 7)~(\text{mod}~8).$
d. $(1.214 + 1.591) \equiv 5~(\text{mod}~7).$
e. $(134 + 453-217) \equiv 4~(\text{mod}~12).$
f. $(2.372 + 971-1.549) \equiv 1~(\text{mod}~11).$
Jawaban a)
Pernyataan benar karena $73$ dibagi $10$ bersisa $3$ dan $89$ dibagi $10$ bersisa $9,$ kemudian hasil dari $3+9 = 12,$ dan jika dibagi $10,$ sisa hasil baginya adalah $2.$
Jawaban b)
Pernyataan benar karena $93$ dibagi $9$ bersisa $3$ dan $47$ dibagi $9$ bersisa $2.$
Jawaban c)
Pernyataan salah karena $497$ dibagi $8$ seharusnya bersisa $1,$ bukan $7.$
Jawaban d)
Pernyataan benar karena $1.214 + 1.591 = 2.805$, dan jika dibagi $7,$ sisanya $5.$
Jawaban e)
Pernyataan salah karena $134 + 453-217 = 370,$ dan jika dibagi $12,$ seharusnya sisanya $10,$ bukan $4.$
Jawaban f)
Pernyataan benar karena $2.372 + 971-1.549 = 1.794,$ dan jika dibagi $11,$ sisanya $1.$
Soal Nomor 3
Carilah semua bilangan bulat di antara $-100$ dan $100$ (eksklusif) yang kongruen dengan $5 ~(\text{mod}~9).$
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\}.$
Soal Nomor 4
Diketahui barisan bilangan
$$1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,\cdots.$$Carilah bilangan pada urutan ke
a. $199,$
b. $998,$ dan
c. $2.020.$
Diketahui barisan bilangan
$$1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0,1,\cdots.$$Barisan tersebut berulang setiap $9$ suku.
Jawaban a)
Perhatikan bahwa
$$199 = 9 \times 22 + 1 \equiv \color{red}{1} ~(\text{mod}~9). $$Jadi, bilangan urutan ke-$199$ sama dengan bilangan urutan ke-$1,$ yaitu $\boxed{1}.$
Jawaban b)
Perhatikan bahwa
$$998 = 9 \times 110 + 8 \equiv \color{red}{8} ~(\text{mod}~9).$$Jadi, bilangan urutan ke-$998$ sama dengan bilangan urutan ke-$8,$ yaitu $\boxed{8}.$
Jawaban c)
Perhatikan bahwa
$$2.020 = 9 \times 224 + 4 \equiv \color{red}{4} ~(\text{mod}~9). $$Jadi, bilangan urutan ke-$2.020$ sama dengan bilangan urutan ke-$4,$ yaitu $\boxed{4}.$
Soal Nomor 5
Dua bilangan asli dibagi $16$ berturut-turut menghasilkan sisa $11$ dan $14.$ Carilah sisa jika jumlah kedua bilangan asli tersebut
a. dibagi $16,$ dan
b. dibagi $8.$
Alternatif 1: Tanpa Modulo
Asumsikan dua bilangan tersebut adalah $11$ dan $14.$ Jumlah dua bilangan itu adalah $11+14 = 25.$
Jawaban a)
$25$ dibagi $16$ bersisa $\boxed{9}$ karena $25 = 1 \times 16 + 9.$
Jawaban b)
$25$ dibagi $8$ bersisa $\boxed{1}$ karena $25 = 3 \times 8 + 1.$
Alternatif 2: Dengan Modulo
Misalkan dua bilangan itu adalah $a$ dan $b.$ Ini berarti $a \equiv 11 ~(\text{mod}~16)$ dan $b \equiv 14 ~(\text{mod}~16).$
Jawaban a)
$$\begin{aligned} a + b & \equiv 11 + 14 \\ & = 25\\ & \equiv \color{blue}{9} ~(\text{mod}~16) \end{aligned}$$Jadi, sisa pembagiannya adalah $\boxed{9}.$
Jawaban b)
$$a + b \equiv 9 \equiv \color{blue}{1} ~(\text{mod}~8) $$Jadi, sisa pembagiannya adalah $\boxed{1}.$
Soal Nomor 6
Tentukan himpunan bilangan bulat nonnegatif yang anggotanya kongruen dengan $122 ~(\text{mod}~7).$
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.
$$\{3, 10, 17, 24, 31, \cdots\} = \{n \mid n = 7m-4, m \in \mathbb{N}\}$$
Soal Nomor 7
Tentukan himpunan bilangan bulat yang anggotanya habis dibagi $5$ dan kongruen dengan $2~(\text{mod}~6).$
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\}.$
Soal Nomor 8
Carilah bilangan bulat positif yang habis dibagi $7$ yang kongruen dengan $2 ~(\text{mod}~9).$
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\}.$
Soal Nomor 9
Berapakah sisa hasil bagi $$(34-14\times 25)\times (23 \times 18 + 87)$$oleh $5$?
Dengan menggunakan sifat distributif modulo, diperoleh
$$\begin{aligned} (34-14\times 25)\times (23 \times 18 + 87) & \equiv (4-0) \times (3 \times 3 + 2) \\ & = 4 \times 11 \\ & \equiv 4~(\text{mod}~5). \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{4}.$
Soal Nomor 10
Carilah sisa setiap bilangan berikut jika dibagi oleh $5$.
a. $19^{77}$
b. $14^{92} \cdot 17^{76}$
Jawaban a)
$$\begin{aligned} 19^{77} & \equiv (-1)^{77} \\ & = (-1) \\ & \equiv \color{blue}{4}~(\text{mod}~5) \end{aligned}$$Jadi, sisa hasil baginya oleh $5$ adalah $\boxed{4}.$
Jawaban b)
$$\begin{aligned} 14^{92} \cdot 17^{76} & \equiv 4^{92} \cdot 2^{76} \\ & = 4^{92} \cdot 4^{38}\\ & = 4^{130} \\ & \equiv (-1)^{130} \\ & = \color{blue}{1} ~(\text{mod}~5) \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{1}.$
Soal Nomor 11
Carilah sisa hasil baginya.
a. $38^{10}$ dibagi oleh $13$.
b. $2.222^{5.555}$ dibagi oleh $7$.
Jawaban a)
$$\begin{aligned} 38^{101} & = (3 \times 13-1)^{101} \\ & \equiv (-1)^{101} \\ & = -1 \\ & \equiv 12~(\text{mod}~13) && (\text{Ditambah}~13) \end{aligned}$$Jadi, sisa hasil bagi $38^{101}$ oleh $13$ adalah $\boxed{12}.$
Jawaban b)
$$\begin{aligned} 2.222^{5.555} & = (7 \times 317 + 3)^{5.555} \\ & \equiv 3^{5.555} \\ & = (3^3)^{1.851} \cdot 3^2 \\ & = (4 \times 7-1)^{1.851} \cdot 3^2 \\ & \equiv (-1)^{1.851} \cdot 9 \\ & \equiv -9 \\ & \equiv 5~(\text{mod}~7) && (\text{Ditambah}~14) \end{aligned}$$Jadi, sisa hasil bagi $2.222^{5.555}$ oleh $7$ adalah $\boxed{5}.$
Soal Nomor 12
Buktikan bahwa jika $a \equiv 19~(\text{mod}~30),$ maka $3a \equiv 7~(\text{mod}~10).$
Misalkan $a \equiv 19~(\text{mod}~30).$ Dengan menggunakan sifat modulo, diperoleh
$$\begin{aligned} a & \equiv 19~(\text{mod}~30) \\ 3a & \equiv 57~(\text{mod}~30) \\ 3a & \equiv 27~(\text{mod}~30) \\ \dfrac{3a}{3} & \equiv \dfrac{27}{3}~\left(\text{mod}~\dfrac{30}{3}\right) \\ a & \equiv 9~(\text{mod}~10) \\ 3a & \equiv 27~(\text{mod}~10) \\ 3a & \equiv 7~(\text{mod}~10). \end{aligned}$$Jadi, terbukti bahwa jika $a \equiv 19~(\text{mod}~30)$, maka $3a \equiv 7~(\text{mod}~10).$
Soal Nomor 13
Carilah semua solusi persamaan linear kongruensi berikut.
a. $2x \equiv 3~(\text{mod}~4)$
b. $x+1 \equiv 3~(\text{mod}~5)$
c. $56x + 43 \equiv 211~(\text{mod}~96)$
Jawaban a)
$2x \equiv 3~(\text{mod}~4)$ memiliki arti bahwa terdapat suatu bilangan bulat $k$ sehingga
$$\begin{aligned} 2x-3 & = 4k \\ 2x-4k & = 3 \\ 2(x-2k) & = 3. \end{aligned}$$Persamaan terakhir menunjukkan bahwa ruas kiri bernilai genap, sedangkan ruas kanan bernilai. Karena paritasnya berbeda, persamaan linear kongruensi tersebut tidak memiliki solusi untuk $x.$
Jawaban b)
$x+1 \equiv 3~(\text{mod}~5)$ memiliki arti bahwa terdapat suatu bilangan bulat $k$ sehingga
$$\begin{aligned} (x+1)-3 & = 5k \\ x-2 & = 5k \\ x & = 5k + 2. \end{aligned}$$Persamaan terakhir ekuivalen dengan $x \equiv 2~(\text{mod}~5).$ Jadi, solusi persamaan linear kongruensi tersebut adalah $\boxed{x \equiv 2~(\text{mod}~5)}.$
Jawaban c)
Perhatikan bahwa $$\begin{aligned} 56x + 43 & \equiv 211~(\text{mod}~96) \\ 56x & \equiv 168~(\text{mod}~96) \\ 56x & \equiv 72~(\text{mod}~96) \\ 7x & \equiv 9~(\text{mod}~12) \\ 7x & \equiv 21~(\text{mod}~12) \\ x & \equiv 3~(\text{mod}~12). \end{aligned}$$Jadi, solusi persamaan linear kongruensi tersebut adalah $\boxed{x \equiv 3~(\text{mod}~12)}.$
Soal Nomor 14
Carilah invers dari setiap ekspresi modulo berikut.
a. $12~(\text{mod}~25)$
b. $6~(\text{mod}~49)$
c. $10~(\text{mod}~143)$
Jawaban a)
Dapat diperiksa bahwa $\text{FPB}(12, 25) = 1$, artinya $(12, 25)$ relatif prima sehingga ekspresi modulo itu memiliki invers.
Dengan algoritma Euclides, kita peroleh
$$25 = 2 \times 12+1 \Leftrightarrow 1 = 25\color{red}{-2} \times 12.$$Jadi, invers dari $12~(\text{mod}~25)$ adalah $\boxed{-2}$. Dapat diperiksa bahwa $12(-2) \equiv -24 \equiv 1~(\text{mod}~25).$
Jawaban b)
Dapat diperiksa bahwa $\text{FPB}(6, 49) = 1$, artinya $(6, 49)$ relatif prima sehingga ekspresi modulo itu memiliki invers.
Dengan algoritma Euclides, kita peroleh
$$49 = 8 \times 6+1 \Leftrightarrow 1 = 49\color{red}{-8} \times 6$$Jadi, invers dari $6~(\text{mod}~49)$ adalah $\boxed{-8}$. Dapat diperiksa bahwa $6(-8) \equiv -48 \equiv 1~(\text{mod}~49)$.
Jawaban c)
Dapat diperiksa bahwa $\text{FPB}(10, 343) = 1$, artinya $(10, 343)$ relatif prima sehingga ekspresi modulo itu memiliki invers.
Dengan algoritma Euclides, kita peroleh
$$\begin{aligned} 343 & = 34 \times 10+3 \\ 10 & = 3 \times 3 + 1 \end{aligned}$$Algoritma pembalikannya menjadi
$$\begin{aligned} 1 & = 10-3 \times 3 \\ & = 10-3 \times (343-34 \times 10) \\ & = \color{red}{103} \times 10-3 \times 343 \end{aligned}$$Jadi, invers dari $10~(\text{mod}~343)$ adalah $\boxed{103}$. Dapat diperiksa bahwa $10(103) \equiv 1030 \equiv 1~(\text{mod}~343).$
Baca: Materi, Soal, dan Pembahasan – Teorema Sisa Cina
Soal Nomor 15
Tentukan sisa pembagian dari $\left(2.020\right)^{2.015^{2.014^{\cdots^{3^{2^{1}}}}}}$ oleh $101.$
Perhatikan bahwa $2020 \div 101 = 20$. Dengan menggunakan sifat distributif modulo, diperoleh
$$\begin{aligned} \left(2.020\right)^{2.015^{2.014^{\cdots^{3^{2^{1}}}}}} & \equiv \left(2.020~(\text{mod}~101)\right)^{2.015^{2.014^{\cdots^{3^{2^{1}}}}}}~(\text{mod}~101) \\ & \equiv 0^{2.015^{2.014^{\cdots^{3^{2^{1}}}}}}~(\text{mod}~101) \\ & \equiv 0~(\text{mod}~101). \end{aligned}$$Jadi, sisa pembagiannya adalah $\boxed{0}$ atau tidak bersisa.
Soal Nomor 16
Berapa sisa hasil bagi $$5 \times 55 \times 555 \times \underbrace{555\cdots55}_{5.555~\text{kali}}$$ oleh $100$?
Dengan menggunakan sifat-sifat kongruensi modulo, diperoleh
$$\begin{aligned} 5 \times 55 \times 555 \times \underbrace{555\cdots55}_{5.555~\text{angka}} & \equiv 5 \times \underbrace{55 \times 55 \times \cdots 55}_{\text{ada}~5.554} \\ & \equiv 5 \times 55^{5.554} \\ & = 5^{5.555} \times 11^{5.554} \\ & = 5^{5.555} \times (11^{10})^{555} \times 11^4) \\ & \equiv 25 \times 1^{555} \times 41 \\ & = 25 \times 41 \\ & \equiv 25~(\text{mod}~100). \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{25}.$
Soal Nomor 17
Diberikan $a_n = 6^n + 8^n$. Tentukan sisa pembagian $a_{2015}$ setelah dibagi oleh $49.$
Kita akan mencari $(6^{2015} + 8^{2015})~(\text{mod}~49).$
Gunakan teorema Euler untuk $n = 49 = 7^2.$ Kita peroleh $\phi(n) = 49 \cdot \left(1-\dfrac17\right) = 42$. Karena $6$ dan $8$ keduanya relatif prima dengan $49,$ berlaku
$$\begin{aligned} 6^{42} & \equiv 1~(\text{mod}~49) \\ 8^{42} & \equiv 1~(\text{mod}~49). \end{aligned}$$Dengan demikian, diperoleh
$$\begin{aligned} (6^{2015} + 8^{2015}) & = 6^{42})^{48} \cdot 6^{-1} + (8^{42})^{48} \cdot 8^{-1} \\ & \equiv 1^{48} \cdot 6^{-1} + 1^{48} + 8^{-1} \\ & = 6^{-1} + 8^{-1} \\ & \equiv -8-6 \\ & = -14 \\ & \equiv 35~(\text{mod}~49). \end{aligned}$$Catatan: Notasi $6^{-1}$ dan $8^{-1}$ pada ekspresi modulo di atas berturut-turut menyatakan invers dari $6~(\text{mod}~49)$ dan $8~(\text{mod}~49)$. Inversnya bisa dicari dengan menggunakan algoritma Euclides, yaitu
$$\begin{aligned} 49 & = 8 \times 6 + 1 \Rightarrow 1 = 49\color{blue}{-8} \times 6 \\ 49 & = 6 \times 8 + 1 \Rightarrow 1 = 49\color{blue}{-6}\times 8. \end{aligned}$$Dengan demikian, inversnya adalah $-8$ dan $-6.$
Jadi, sisa hasil baginya adalah $\boxed{35}.$
Soal Nomor 18
Tentukan banyaknya bilangan $n \in \{1, 2, 3, \cdots, 2009\}$ sehingga $4n^6 + n^3 + 5$ habis dibagi $7.$
Analisis setiap nilai $n$ yang kongruen dengan sisa hasil bagi oleh $7$ yang mungkin, yaitu $\{0, 1, 2, 3, 4, 5, 6\}$.
Jika $n \equiv 0~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(0)^6 + (0)^3 + 5)~(\text{mod}~7) \\ & \equiv 5~(\text{mod}~7). \end{aligned}$$Jika $n \equiv 1~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(1)^6 + (1)^3 + 5)~(\text{mod}~7) \\ & \equiv (4 + 1 + 5)~(\text{mod}~7) \\ & \equiv 3~(\text{mod}~7). \end{aligned}$$Jika $n \equiv 2~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(2)^6 + (2)^3 + 5)~(\text{mod}~7) \\ & \equiv (4 + 1 + 5)~(\text{mod}~7) \\ & \equiv 3~(\text{mod}~7). \end{aligned}$$Jika $n \equiv 3~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(3)^6 + (3)^3 + 5)~(\text{mod}~7) \\ & \equiv (4 + 6 + 5)~(\text{mod}~7) \\ & \equiv 1~(\text{mod}~7). \end{aligned}$$Jika $n \equiv 4 \equiv (-3)~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(-3)^6 + (-3)^3 + 5)~(\text{mod}~7) \\ & \equiv (4 + 1 + 5)~(\text{mod}~7) \\ & \equiv 3~(\text{mod}~7). \end{aligned}$$Jika $n \equiv 5 \equiv (-2)~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(-2)^6 + (-2)^3 + 5)~(\text{mod}~7) \\ & \equiv (4 + 6 + 5)~(\text{mod}~7) \\ & \equiv 1~(\text{mod}~7). \end{aligned}$$Jika $n \equiv 6 \equiv (-1)~(\text{mod}~7)$, maka $$\begin{aligned} 4n^6 + n^3 + 5 & \equiv (4(-1)^6 + (-1)^3 + 5)~(\text{mod}~7) \\ & \equiv (4 + 6 + 5)~(\text{mod}~7) \\ & \equiv 1~(\text{mod}~7). \end{aligned}$$Dari ketujuh penelusuran sisa hasil bagi di atas, ternyata tidak ditemukan sisa hasil bagi $0$ untuk setiap nilai $n$.
Jadi, tidak ada nilai $n$ yang memenuhi kondisi tersebut.
Soal Nomor 19
Barisan 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_{2.020}$ dibagi $5.$
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.
Untuk soal ini, $n = 5$ dan akan kita temukan bahwa $\pi(n) = 20,$ artinya barisan akan berulang setiap $20$ suku.
Barisan Fibonacci:
$$\begin{array}{cccccc} 1 & 1 & 2 & 3 & 5 & 8 \\ 13 & 21 & 34 & 55 & 89 & 144 \\ 233 & 377 & 610 & 987 & 1.597 & 2.584 \\ 4.181 & 6.765 & 10.946 & 17.711 & \cdots & \cdots \end{array}$$Sisa hasil bagi masing-masing suku oleh $5$:
$$\begin{array}{cccccc} \color{red}{1} & \color{red}{1} & 2 & 3 & 5 & 3 \\ 3 & 1 & 4 & 0 & 4 & 4 \\ 3 & 2 & 0 & 2 & 2 & 4 \\ 1 & \underbrace{0}_{F_{20}} & \color{red}{1} & \color{red}{1} & \cdots & \cdots \end{array}$$Karena $2.020$ habis dibagi $20$, $F_{2.020} \equiv F_{20} \equiv 0~(\text{mod}~5).$ Jadi, sisa hasil baginya adalah $\boxed{0}.$
Baca: Materi, Soal, dan Pembahasan – Bilangan Fibonacci
Soal Nomor 20
Buktikan 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).$$
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).$
Dengan demikian, diperoleh
$$\begin{aligned} a_1^2+a_2^2+\cdots+a_9^2 & \equiv \underbrace{1+1+\cdots+1}_{\text{sebanyak 9 kali}} \\ & = 9 \\ & \equiv 0~(\text{mod}~3). \end{aligned}$$Jadi, terbukti bahwa $$a_1^2+a_2^2+\cdots+a_9^2 \equiv 0~(\text{mod}~3).$$
Soal Nomor 21
Tunjukkan bahwa $12! + 1$ habis dibagi $13$ dengan cara mengelompokkan pasangan dua bilangan yang saling invers terhadap modulo $13$ pada bentuk penjabaran $12!.$
Karena $12! = 1(2)(3)\cdots(12),$ pasangan dua bilangan yang saling invers terhadap modulo $13$ pada faktor-faktor tersebut adalah $(2, 7), (3, 9),$ $(4, 10),$ $(5, 8),$ dan $(6, 11).$ Anda dapat melihat bahwa hasil kali dua bilangan pada setiap pasangan kongruen dengan $1$ modulo $13.$ Dengan demikian, dapat ditulis
$$\begin{aligned} 12! + 1 & = 1(2)(3)\cdots(12) + 1 \\ & = 1(2 \cdot 7)(3 \cdot 9)(4 \cdot 10)(5 \cdot 8)(6 \cdot 11)(12) + 1 \\ & \equiv 1(1)(1)(1)(1)(1)(-1) + 1 \\ & \equiv -1 + 1 \\ & \equiv 0~(\text{mod}~13). \end{aligned}$$Jadi, terbukti bahwa $12! + 1$ habis dibagi $13.$
Soal Nomor 22
Gunakan teorema kecil Fermat untuk menentukan solusi dari kongruensi linear berikut.
a. $7x \equiv 11~(\text{mod}~17).$
b. $3x \equiv 9~(\text{mod}~19).$
Jawaban a)
Perhatikan bahwa $7^{16} \equiv 1~(\text{mod}~17)$ berdasarkan teorema kecil Fermat karena $17$ prima dan $17 \nmid 7.$ Dengan demikian, kalikan $7^{15}$ pada kedua ruas dari kongruensi $7x \equiv 11~(\text{mod}~17)$ sehingga didapat
$$\begin{aligned} 7^{16}x & \equiv 7^{15} \cdot 11~(\text{mod}~17) \\ x & \equiv (7^3)^5 \cdot 11~(\text{mod}~17) \\ x & \equiv 3^5 \cdot 11~(\text{mod}~17) \\ x & \equiv 5 \cdot 11~(\text{mod}~17) \\ x & \equiv 4~(\text{mod}~17). \end{aligned}$$Jadi, solusi dari kongruensi linear tersebut adalah $\boxed{x \equiv 4~(\text{mod}~17)}.$
Jawaban b)
Perhatikan bahwa $3^{18} \equiv 1~(\text{mod}~19)$ berdasarkan teorema kecil Fermat karena $19$ prima dan $19 \nmid 3.$ Dengan demikian, kalikan $3^{17}$ pada kedua ruas dari kongruensi $3x \equiv 9~(\text{mod}~19)$ sehingga didapat
$$\begin{aligned} 3^{18}x & \equiv 3^{17} \cdot 9~(\text{mod}~19) \\ x & \equiv (3^4)^4 \cdot 3 \cdot 9~(\text{mod}~19) \\ x & \equiv 5^4 \cdot 27~(\text{mod}~19) \\ x & \equiv 5^2 \cdot 5^2 \cdot 8~(\text{mod}~19) \\ x & \equiv 6 \cdot 6 \cdot 8 ~(\text{mod}~19) \\ x & \equiv 3~(\text{mod}~19). \end{aligned}$$Jadi, solusi dari kongruensi linear tersebut adalah $\boxed{x \equiv 3~(\text{mod}~19)}.$
Soal Nomor 23
Buktikan bahwa jika $p$ merupakan bilangan prima, maka $2(p-3)! \equiv -1~(\text{mod}~p).$
Misalkan $p$ merupakan bilangan prima. Berdasarkan teorema Wilson, berlaku $(p-1)! \equiv -1~(\text{mod}~p).$ Dari sini, diperoleh
$$\begin{aligned} (p-1)(p-2)(p-3)! & \equiv -1~(\text{mod}~p) \\ (-1)(-2)(p-3)! & \equiv -1~(\text{mod}~p) \\ 2(p-3)! & \equiv -1~(\text{mod}~p). \end{aligned}$$Jadi, terbukti bahwa $2(p-3)! \equiv -1~(\text{mod}~p).$
Soal Nomor 24
Buktikan bahwa jika $p$ merupakan bilangan prima, maka $$1^{p-1} + 2^{p-1} + 3^{p-1} + \cdots + (p-1)^{p-1} \equiv -1~(\text{mod}~p).$$
Misalkan $p$ merupakan bilangan prima. Karena $p$ prima, teorema kecil Fermat berlaku, yaitu $a^{p-1} \equiv 1~(\text{mod}~p)$ untuk setiap bilangan bulat $a$ dengan $p \nmid a.$ Jelas bahwa $p \nmid a$ saat $a \le p-1.$ Oleh karena itu, teorema kecil Fermat memberlakukan
$$\begin{aligned} 1^{p-1} & \equiv 1~(\text{mod}~p) \\ 2^{p-1} & \equiv 1~(\text{mod}~p) \\ 3^{p-1} & \equiv 1~(\text{mod}~p) \\ \cdots \\ (p-1)^{p-1} & \equiv 1~(\text{mod}~p). \end{aligned}$$Dengan menjumlahkan semua kongruensi tersebut sesuai ruasnya, didapat
$$\begin{aligned} 1^{p-1} + 2^{p-1} + 3^{p-1} + \cdots + (p-1)^{p-1} & \equiv \underbrace{1+1+\cdots+1}_{\text{sebanyak}~p-1} \\ & = p-1~(\text{mod}~p). \end{aligned}$$Jadi, terbukti bahwa $$1^{p-1} + 2^{p-1} + 3^{p-1} + \cdots + (p-1)^{p-1} \equiv -1~(\text{mod}~p).$$