Materi, Soal, dan Pembahasan – Kongruensi Modulo

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.

  1. $a \equiv a ~(\text{mod}~m).$
  2. Jika $a \equiv b ~(\text{mod}~m),$ maka $b \equiv a ~(\text{mod}~m).$
  3. Jika $a \equiv b ~(\text{mod}~m)$ dan $b \equiv c ~(\text{mod}~m)$, maka $a \equiv c ~(\text{mod}~m).$
  4. Jika $a \equiv b ~(\text{mod}~m)$, maka $ac \equiv bc ~(\text{mod}~m).$
  5. Jika $a \equiv b ~(\text{mod}~m)$, maka $a+c \equiv b+c ~(\text{mod}~m).$
  6. Jika $a \equiv b ~(\text{mod}~m)$ dan $c \equiv d ~(\text{mod}~m)$, maka $a+c \equiv b+d ~(\text{mod}~m).$
  7. Jika $a \equiv b ~(\text{mod}~m)$ dan $c \equiv d ~(\text{mod}~m)$, maka $a-c \equiv b-d ~(\text{mod}~m).$
  8. Jika $a \equiv b ~(\text{mod}~m)$ dan $d \mid m,$ $d > 0,$ maka $a \equiv b ~(\text{mod}~d).$
  9. Jika $a \equiv b ~(\text{mod}~m)$ dan $c \equiv d ~(\text{mod}~m)$, maka $ac \equiv bd ~(\text{mod}~m).$
  10. $(am + b)^n \equiv b^n ~(\text{mod}~m)$ untuk setiap $n \in \mathbb{N}.$
  11. Jika $a \equiv b ~(\text{mod}~m)$, maka $a^n \equiv b^n ~(\text{mod}~m)$ untuk setiap bilangan asli $n.$
  12. 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.

Fermat, Euler, dan Wilson
Fermat, Euler, dan Wilson

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 (16071665).

Teorema Kecil Fermat

Misalkan $p$ merupakan bilangan prima dan $a$ merupakan bilangan bulat. Dengan demikian, $a^p-a$ selalu habis dibagi oleh $p.$ Secara matematis, ditulis $$a^p \equiv a~(\text{mod}~p).$$

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 (17071783).

Teorema Euler

Misalkan $n$ merupakan bilangan bulat positif dan $a$ merupakan bilangan bulat yang relatif prima dengan $n.$ Dengan demikian,
$$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

Misalkan $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
$$\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 (17361798) 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 (17361813) berhasil membuktikan konjektur ini sehingga menjadi teorema. Meskipun demikian, teorema ini diberi nama teorema Wilson karena John Wilson (17411793) 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 (9651040) telah mengetahui dan membuktikan teorema ini.

Teorema Wilson

Jika $p$ merupakan bilangan prima, maka $(p-1)! \equiv -1~(\text{mod}~p).$

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

Jika kamu ingin menggapai mimpimu, carilah orang yang sudah berhasil menggapai mimpi itu dan belajarlah darinya.

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$

Pembahasan

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)

[collapse]

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$

Pembahasan

$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)

[collapse]

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$

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.
$$\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)

[collapse]

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$

Pembahasan

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)

[collapse]

Soal Nomor 5

Angka satuan dari $7^{7^7}$ adalah $\cdots \cdot$
A. $1$                       C. $5$                    E. $9$
B. $3$                       D. $7$

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

Soal Nomor 7

Angka satuan dari $357^5 \cdot 117^9$ adalah $\cdots \cdot$
A. $1$                       C. $5$                      E. $9$
B. $3$                       D. $7$

Pembahasan

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)

[collapse]

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$

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
$$\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)

[collapse]

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$

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

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$

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}.$
(Jawaban C)

[collapse]

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$

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}.$
(Jawaban C)

[collapse]

Soal Nomor 15

Sisa hasil bagi $11^{12}$ oleh $13$ adalah $\cdots \cdot$
A. $0$                     C. $3$                   E. $9$
B. $1$                     D. $7$

Pembahasan

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)

[collapse]

Soal Nomor 16

Sisa hasil bagi $16!$ oleh $19$ adalah $\cdots \cdot$
A. $5$                  C. $9$                   E. $13$
B. $7$                  D. $11$

Pembahasan

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)

[collapse]

Soal Nomor 17

Sisa hasil bagi $5!25!$ oleh $31$ adalah $\cdots \cdot$
A. $1$                    C. $5$                  E. $17$
B. $3$                    D. $11$

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

Soal Nomor 19

Sisa hasil bagi $18!$ oleh $437$ adalah $\cdots \cdot$
A. $1$                  C. $112$                 E. $436$
B. $4$                 D. $256$

Pembahasan

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)

[collapse]

Soal Nomor 20

Sisa hasil bagi $5^{100}$ oleh $7$ adalah $\cdots \cdot$
A. $1$                    C. $3$                   E. $5$
B. $2$                    D. $4$

Pembahasan

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)

[collapse]

Soal Nomor 21

Sisa hasil bagi $6^{2.000}$ oleh $11$ adalah $\cdots \cdot$
A. $0$                  C. $2$                  E. $4$
B. $1$                  D. $3$

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

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

Pembahasan

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)

[collapse]

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$

Pembahasan

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)

[collapse]

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).$

Pembahasan

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).$ 

[collapse]

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).$

Pembahasan

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.$

[collapse]

Soal Nomor 3

Carilah 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 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.$

Pembahasan

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}.$

[collapse]

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.$

Pembahasan

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}.$

[collapse]

Soal Nomor 6

Tentukan 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.
$$\{3, 10, 17, 24, 31, \cdots\} = \{n \mid n = 7m-4, m \in \mathbb{N}\}$$

[collapse]

Soal Nomor 7

Tentukan 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 8

Carilah 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 9

Berapakah sisa hasil bagi $$(34-14\times 25)\times (23 \times 18 + 87)$$oleh $5$?

Pembahasan

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}.$

[collapse]

Soal Nomor 10

Carilah sisa setiap bilangan berikut jika dibagi oleh $5$.
a. $19^{77}$
b. $14^{92} \cdot 17^{76}$

Pembahasan

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}.$

[collapse]

Soal Nomor 11

Carilah sisa hasil baginya.
a. $38^{10}$ dibagi oleh $13$.
b. $2.222^{5.555}$ dibagi oleh $7$.

Pembahasan

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}.$

[collapse]

Soal Nomor 12

Buktikan 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
$$\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).$

[collapse]

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)$

Pembahasan

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)}.$

[collapse]

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)$

Pembahasan

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).$

[collapse]

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.$

Pembahasan

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.

[collapse]

Soal Nomor 16

Berapa 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
$$\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}.$

[collapse]

Soal Nomor 17

Diberikan $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).$
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}.$

[collapse]

Soal Nomor 18

Tentukan 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\}$.
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.

[collapse]

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.$

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.
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}.$

[collapse]

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).$$

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).$
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).$$

[collapse]

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!.$

Pembahasan

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.$

[collapse]

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).$

Pembahasan

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)}.$

[collapse]

Soal Nomor 23

Buktikan bahwa jika $p$ merupakan bilangan prima, maka $2(p-3)! \equiv -1~(\text{mod}~p).$

Pembahasan

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).$

[collapse]

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).$$

Pembahasan

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).$$

[collapse]

7 Replies to “Materi, Soal, dan Pembahasan – Kongruensi Modulo”

  1. Permisi, itu untuk nomor 11, bukannya 3 itu dipangkatkan dengan 3 ya? Karena kan 4 dikali 19 itu 76 dan jika 3 nya dipangkatkan 2 hasilnya hanya 78. Mohon maaf kalau salah, terimakasih. Allahualam. :))

  2. kak pengen nanya
    untuk soal nomor 4 uraian
    kok dipembahasannnya bilang “suku barisan itu berulang untuk setiap delapan giliran”
    bukannya berulang setiap sembilan bilangan yah kak?
    kan barisan bilangannya
    1,2,3,4,5,6,7,8,0 terus balik lagi jadi 1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,0. . .
    nah 1,2,3,4,5,6,7,8,0 ini bilangannya ada 9 angka.
    mohon dijawab kak🙏
    .
    .
    ohyah saya ingin berterimakasih karena website ini sangat membantu saya dalam mempelajari materi olimpiade

Leave a Reply

Your email address will not be published. Required fields are marked *