Materi, Soal, dan Pembahasan – Kongruensi Modulo

Misalkan $m \in \mathbb{N}$, untuk dua bilangan bulat $a, b$, $a$ dikatakan kongruen dengan $b$ modulo $m$ jika dan hanya jika $m~|~(a-b)$, ditulis dengan $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~|~(34-4)$.
Contoh 2:
$7 \equiv -8~(\text{mod}~5)$ (baca: $7$ kongruen dengan $-8$ modulo $5$), lebih tepat dipahami dalam model keterbagian $5~|~(7+8)$, atau bisa juga $7$ dan $-8$ dibagi $7$, sisanya sama.

Kongruensi atau kesetaraan diformulasikan pertama kali oleh Carl Friedrich Gauss pada tahun 1790 dengan formula $x \equiv r ~(\text{mod}~d)$ jika dan hanya jika $x = kd + r$ untuk sembarang bilangan bulat $k$.

Sifat Distributif Modulo

Jika $a, b$ bilangan bulat dan $n$ adalah bilangan asli, maka berlaku
$$\begin{aligned} 1. &~(a\pm b)~(\text{mod}~n) \equiv (a~(\text{mod}~n) \pm b ~(\text{mod}~n))~(\text{mod}~n) \\ 2. &~(ab)~(\text{mod}~n) \equiv (a~(\text{mod}~n) \cdot b~(\text{mod}~n))~(\text{mod}~n) \\ 3. &~a^b ~(\text{mod}~n) \equiv ((a~(\text{mod}~n))^b)~(\text{mod}~n),~\text{untuk}~b~\text{bilangan}~\text{bulat non-negatif} \end{aligned}$$

Sifat Keterhubungan Modulo

  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~|~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 $n \in \mathbb{N}$.
  11. Jika $a \equiv b ~(\text{mod}~m)$, maka $a^n \equiv b^n ~(\text{mod}~m)$, untuk bilangan asli $n$.
  12. Jika $a \equiv a ~(\text{mod}~m)$ dan $f$ merupakan fungsi polinomial, $$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$$ dengan koefisien bilangan bulat, 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 ranah 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

Misalkan $p$ adalah bilangan prima dan $a$ sembarang bilangan bulat. Dengan demikian, $a^p-a$ selalu habis dibagi oleh $p$.
Dalam notasi modulo aritmetik, ditulis sebagai
$$a^p \equiv a~(\text{mod}~p)$$

Contoh:
Karena $11$ adalah bilangan prima, maka $2^{11}-2 = 2046$ pasti 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

Misalkan $n$ adalah bilangan bulat positif dan $a$ adalah bilangan bulat yang relatif prima dengan $n$, maka
$$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 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 $\{1, 3, 7, 9\}$, sehingga $\phi(10) = 4$. Berdasarkan Teorema Euler,
$$a^4 \equiv 1~(\text{mod}~10)$$atau 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},$$ maka 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 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 kebenarannya. Pada tahun 1771, Joseph Lagrange (1736 – 1813) berhasil membuktikan konjektur ini, dan selanjutnya dimasukkan sebagai teorema. Meskipun demikian, teorema ini diberi nama Teorema Wilson, karena John Wilson (1741 – 1793) mencetuskannya lebih dulu. Uniknya, catatan sejarah memberi bukti 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

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

Contoh:
Karena $13$ prima, maka $12! \equiv -1~(\text{mod}~13)$. Dengan kata lain, $12!$ dibagi $13$ sisanya adalah $12$.
Karena $41$ prima, maka $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)$ bila $aa^{-1} \equiv 1~(\text{mod}~m)$.
Untuk menemukan $a^{-1}$, kita harus membuat kombinasi linear dengan menggunakan Algoritma Euclid dan pembalikannya, seperti contoh-contoh berikut.

Contoh 1
Carilah invers dari $4~(\text{mod}~7)$.

Jelas bahwa $\text{FPB}(4, 7) = 1$, berarti $(4, 7)$ relatif prima, sehingga $4~(\text{mod}~7)$ memiliki invers.
Pertama, kita buat 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 Bezout.
$$\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 bila kita periksa,
$$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$, berarti $(7, 23)$ relatif prima, sehingga $7~(\text{mod}~23)$ memiliki invers.
Pertama, kita buat Algoritma Euclid 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 Bezout.
$$\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 bila kita periksa,
$$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 Euclid

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}$$maka kita peroleh
$$\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

Deret aritmetika di atas memiliki 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 ~(\text{mod}~5) & \equiv (\underbrace{2+2+2+\cdots+2}_{\text{ada}~201}) ~(\text{mod}~5) \\ & \equiv 2(201) ~(\text{mod}~5) \\ & \equiv 402 ~(\text{mod}~5) \\ & \equiv (400 + 2) ~(\text{mod}~5) \\ & \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 menjumlahkan dulu semua bilangannya, lalu dicari sisa hasil baginya terhadap $4$, tetapi ini bisa jadi tidak efektif.
Alternatif lain: Masing-masing bilangan dicari sisa hasil baginya terhadap $4$, lalu dijumlahkan, seperti berikut.
$$\begin{aligned} & (1+2+3+65+66+67+79+80+81+99)~\text{mod}~4) \\ & \equiv (1+2+3+1+2+3+3+0+1+3)~(\text{mod}~4) \\ & \equiv 19~(\text{mod}~4) \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^{2020}$ 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$, maka angka satuan dari $7^{2020}$ sama dengan angka satuan dari $7^4$, yaitu $\boxed{1}$
Cara 2: Menggunakan Modulo
Angka satuan dicari menggunakan modulo $10$.
$$\begin{aligned} 7^{2020} ~(\text{mod}~10) & \equiv (7^2)^{1010} ~(\text{mod}~10) \\ & \equiv 49^{1010} ~(\text{mod}~10) \\ & \equiv \\ (4 \times 10 + 9)^{1010} ~(\text{mod}~10) \\ & \equiv 9^{1010} ~(\text{mod}~10) \\ & \equiv (-1)^{1010} ~(\text{mod}~10) \\ & \equiv \color{blue}{1} ~(\text{mod}~10) \end{aligned}$$Jadi, angka satuan dari $7^{2020}$ 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 & \equiv (7^4 \cdot 7^3) ~(\text{mod}~10) \\ & \equiv (7^4 ~(\text{mod}~10))(7^3 ~(\text{mod}~10)) \\ & \equiv (1 \cdot 3) ~(\text{mod}~10) \\ & \equiv \color{blue}{3} ~(\text{mod}~10) \end{aligned}$$Jadi, angka satuan dari $7^7$ adalah $\boxed{3}$
Dengan demikian,
$$\begin{aligned} 7^{7^7} & \equiv 7^3 ~(\text{mod}~10) \\ & \equiv 3 ~(\text{mod}~10) \end{aligned}$$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, kita peroleh
$$\begin{aligned} 9^{42}-5^{42} & \equiv (2^{42}-5^{42})~(\text{mod}~7) \\ & \equiv ((2^3)^{14}-(5^3)^{14})~(\text{mod}~7) \\ & \equiv (8^{14}-125^{14})~(\text{mod}~7) \\ & \equiv ((1 \times 7 + 1)^{14}-(7 \times 18-1)^{14})~(\text{mod}~7) \\ & \equiv (1^{14}-(-1)^{14})~(\text{mod}~7) \\ & \equiv (1-1)~(\text{mod}~7) \\ & \equiv 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$.
$$\begin{aligned} 357^5 \cdot 117^9 & \equiv 7^5 \cdot 7^9~(\text{mod}~10) \\ & \equiv 7^{14}~(\text{mod}~10) \\ & \equiv 7^2~(\text{mod}~10) \\ & \equiv 49~(\text{mod}~10) \\ & \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 pembagian $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 melalui 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, kita peroleh
$$\begin{aligned} 4^{18} & \equiv (4^3)^6 ~(\text{mod}~9) \\ & \equiv 1^6 ~(\text{mod}~9) \\ & \equiv 1 ~(\text{mod}~9) \end{aligned}$$Selanjutnya, akan dicari sisa pembagian $19^{80}$ oleh $9$. Perhatikan bahwa $19$ dibagi $9$ bersisa $1$.
$$\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) ~(\text{mod}~9) \\ & \equiv 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 terhadap $5~(\text{mod}~7)$ adalah $\cdots \cdot$
A. $280$                   C. $284$                    E. $290$
B. $282$                   D. $285$

Pembahasan

Misalkan bilangan bulat tersebut adalah $x$, sehingga $x \equiv 5~(\text{mod}~7)$ dengan $1.000 < x < 3.000$.
Untuk sembarang bilangan bulat $k$, berlaku
$$\begin{aligned} k & = \dfrac{x-5}{7} \\ 7k & = x-5 \\ x & = 7k+5 \end{aligned}$$Karena $x > 1.000$, maka
$$\begin{aligned} 7k + 5 & > 1.000 \\ 7k & > 995 \\ k & > 142,\cdots \\ k_{\text{min}} & = 143 \end{aligned}$$Karena $x < 3.000$, maka
$$\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}(k) = 427-143+1 = 285$. Ini berarti ada $\boxed{285}$ bilangan bulat di antara $1.000$ dan $3.000$ yang kongruen terhadap $5~(\text{mod}~7)$.
(Jawaban D)

[collapse]

Soal Nomor 10
Sisa hasil bagi $17 + 177 + 1777 + \cdots + 1\underbrace{777\cdots7}_{\text{ada}~20}$ 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})~(\text{mod}~8) \\ & \equiv 20~(\text{mod}~8) \\ & \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}~(\text{mod}~5) && (8 \div 5 = R3) \\ & \equiv (3^{4})^{19} \cdot 3^2~(\text{mod}~5) \\ & \equiv (16 \times 5 + 1)^{19} \cdot 9~(\text{mod}~5) \\ & \equiv 1^{19} \cdot 9~(\text{mod}~5) \\ & \equiv 9~(\text{mod}~5) \\ & \equiv \color{blue}{4}~(\text{mod}~5) && (9 \div 5 = R4) \end{aligned}$$Jadi, nilai $\boxed{x = 4}$
(Jawaban E)

[collapse]

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)~(\text{mod}~9) \\ & \equiv (6 \cdot 5 \cdot 1)~(\text{mod}~9) \\ & \equiv 30~(\text{mod}~9) \\ & \equiv 3~(\text{mod}~9) \end{aligned}$$Jadi, sisa hasil pembagiannya adalah $\boxed{3}$
(Jawaban B)

[collapse]

Soal Nomor 13
Banyak nilai $n$ yang memenuhi $n \equiv -n~(\text{mod}~12)$ untuk $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)$ ekuivalen dengan
$$k = \dfrac{n-(-n)}{12} = \dfrac{2n}{12} = \dfrac16n$$dengan $k$ bilangan bulat. Agar diperoleh bilangan bulat, maka $n$ haruslah bilangan berkelipatan $6$. Karena $40 \leq n \leq 80$, maka nilai $n$ yang memenuhi adalah $$\{42, 48, 54, 60, 66, 72, 78\}.$$Jadi, banyak nilai $n$ 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)$ ekuivalen dengan
$$k = \dfrac{617n-943n}{18} = \dfrac{-326n}{18} = -\dfrac{163}{9}n$$dengan $k$ bilangan bulat. Agar diperoleh bilangan bulat, dan juga $163$ merupakan bilangan prima, maka $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$ adalah bilangan prima, maka dengan menggunakan Teorema Kecil Fermat, kita peroleh
$$11^{13} \equiv 11~(\text{mod}~13)$$yang ekuivalen dengan
$$11^{12} \equiv 1~(\text{mod}~13)$$Jadi, sisa hasil baginya adalah $\boxed{1}$
(Jawaban D)

[collapse]

Soal Nomor 16
Sisa pembagian dari $2^{2017} + 0^{2017} + 1^{2017} + 7^{2017}$ oleh $2017$ 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 sembarang bilangan prima $p$, kita peroleh
$$\begin{aligned} & (2^{2017} + 0^{2017} + 1^{2017} + 7^{2017})~(\text{mod}~2017) \\ & \equiv (2 + 0 + 1 + 7)~(\text{mod}~2017) \\ & \equiv 10~(\text{mod}~2017) \end{aligned}$$Jadi, sisa hasil baginya adalah $\boxed{10}$
(Jawaban E)

[collapse]

Soal Nomor 17 (Soal Kihajar STEM 2020 Tingkat SMA)
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 objek yang berulang setiap $7$ suku. Oleh karena itu, kita akan mencari sisa hasil bagi dari $2^{2020}$ oleh $7$.
$$\begin{aligned} 2^{2020} & \equiv (2^3)^{673} \cdot 2)~\text{mod}~7 \\ & \equiv (8^{673} \cdot 2)~\text{mod}~7 \\ & \equiv (1^{673} \cdot 2)~\text{mod}~7 \\ & \equiv 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]
 

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 = kd + r$ untuk sembarang bilangan bulat $k$. Apalagi $k$ ditemukan bernilai bulat, maka pernyataan tersebut bernilai benar.
Jawaban a)
$76 \equiv -152 ~(\text{mod}~3)$ memiliki arti
$$\begin{aligned} 76 & = 3k + (-152) \\ 228 & = 3k \\ k & = 76 \in \mathbb{Z} \end{aligned}$$Karena $k$ bernilai bulat, maka pernyataan $76 \equiv -152 ~(\text{mod}~3)$ bernilai benar.
Jawaban b)
$721 \equiv -484 ~(\text{mod}~5)$ memiliki arti
$$\begin{aligned} 721 & = 5k + (-484) \\ 1205 & = 5k \\ k & = 241 \in \mathbb{Z} \end{aligned}$$Karena $k$ bernilai bulat, maka pernyataan $721 \equiv -484 ~(\text{mod}~5)$ bernilai benar.
Jawaban c)
$118 \equiv 25 ~(\text{mod}~13)$ memiliki arti
$$\begin{aligned} 118 & = 13k + 25 \\ 93 & = 13k \\ k & = \dfrac{93}{13} \notin \mathbb{Z} \end{aligned}$$Karena $k$ tidak bernilai bulat, maka pernyataan $118 \equiv 25 ~(\text{mod}~13)$ bernilai salah.
Jawaban d)
$2.401 \equiv 147 ~(\text{mod}~49)$ memiliki arti
$$\begin{aligned} 2.401 & = 49k + 147 \\ 2.254 & = 49k \\ k & = 46 \in \mathbb{Z} \end{aligned}$$Karena $k$ bernilai bulat, maka pernyataan $2.401 \equiv 147 ~(\text{mod}~49)$ bernilai benar.
Jawaban e)
$183 \equiv 291 ~(\text{mod}~6)$ memiliki arti
$$\begin{aligned} 183 & = 6k + 291 \\ -108 & = 6k \\ k & = -18 \in \mathbb{Z} \end{aligned}$$Karena $k$ bernilai bulat, maka pernyataan $183 \equiv 291 ~(\text{mod}~6)$ bernilai benar.
Jawaban f)
$2.701 \equiv 14.393 ~(\text{mod}~8)$ memiliki arti
$$\begin{aligned} 2.701 & = 8k + 14.393 \\ -11.692 & = 8k \\ k & = -\dfrac{11.692}{8} \notin \mathbb{Z} \end{aligned}$$Karena $k$ tidak bernilai bulat, maka pernyataan $2.701 \equiv 14.393 ~(\text{mod}~8)$ bernilai salah.
Jawaban g)
$493 \equiv 873 ~(\text{mod}~10)$ memiliki arti
$$\begin{aligned} 493 & = 10k + 873 \\ -380 & = 10k \\ k & = -38 \in \mathbb{Z} \end{aligned}$$Karena $k$ bernilai bulat, maka pernyataan $493 \equiv 873 ~(\text{mod}~10)$ bernilai benar.
Jawaban h)
$4.113 \equiv 396 ~(\text{mod}~9)$ memiliki arti
$$\begin{aligned} 4.113 & = 9k + 396 \\ 3.717 & = 9k \\ k & = 413 \in \mathbb{Z} \end{aligned}$$Karena $k$ bernilai bulat, maka pernyataan $4.113 \equiv 396 ~(\text{mod}~9)$ bernilai benar.

[collapse]

Soal Nomor 2
Nyatakan benar atau salah 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. $73$ dibagi $10$ bersisa $3$, sedangkan $89$ dibagi $10$ bersisa $9$. Hasil dari $3+9 = 12$, dibagi $10$ bersisa $2$.
Jawaban b)
Pernyataan benar. $93$ dibagi $9$ bersisa $3$, sedangkan $47$ dibagi $9$ bersisa $2$.
Jawaban c)
Pernyataan salah. $497$ dibagi $8$ seharusnya bersisa $1$, bukan $7$.
Jawaban d)
Pernyataan benar. Dapat diperiksa bahwa $1.214 + 1.591 = 2.805$, bila dibagi $7$, maka sisanya $5$.
Jawaban e)
Pernyataan salah. Dapat diperiksa bahwa $134 + 453-217 = 370$, bila dibagi $12$, seharusnya sisanya $10$, bukan $4$.
Jawaban f)
Pernyataan benar. Dapat diperiksa bahwa $2.372 + 971-1.549 = 1.794$, bila dibagi $11$, sisanya $1$.

[collapse]

Soal Nomor 3
Carilah semua bilangan bulat di antara $-100$ dan $100$ yang merupakan $5 ~(\text{mod}~9)$.

Pembahasan

Misalkan bilangan bulat itu dinotasikan $n$, maka didapat $n \equiv 5 ~(\text{mod}~9)$, yang berarti $n = 9k + 5$ untuk suatu $k$ bilangan bulat dan $-100 < n < 100$. Nilai minimum $k$ adalah $k_{\text{min}} = -11$ dan nilai maksimumnya adalah $k_{\text{maks}} = 10$. Dengan demikian, semua bilangan bulat yang dimaksud dinyatakan dalam himpunan berikut.
$$\{-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:
a. $199$
b. $998$
c. $2.020$

Pembahasan

Suku barisan itu kembali berulang untuk setiap delapan giliran.
Jawaban a)
Karena
$$\begin{aligned} 199 ~(\text{mod}~8) & \equiv (8 \times 24 + 7) ~(\text{mod}~8) \\ & \equiv \color{red}{7} ~(\text{mod}~8) \end{aligned}$$maka nilai suku ke-$199$ sama dengan nilai suku ke-$7$, yaitu $\boxed{7}$
Jawaban b)
Karena
$$\begin{aligned} 998 ~(\text{mod}~8) & \equiv (8 \times 124 + 6) ~(\text{mod}~8) \\ & \equiv \color{red}{6} ~(\text{mod}~8) \end{aligned}$$maka nilai suku ke-$998$ sama dengan nilai suku ke-$6$, yaitu $\boxed{6}$
Jawaban c)
Karena
$$\begin{aligned} 2.020 ~(\text{mod}~8) & \equiv (8 \times 252 + 4) ~(\text{mod}~8) \\ & \equiv \color{red}{4} ~(\text{mod}~8) \end{aligned}$$maka nilai suku ke-$2.020$ sama dengan nilai suku ke-$4$, yaitu $\boxed{4}$

[collapse]

Soal Nomor 5
Diketahui dua bilangan asli dibagi $16$ berturut-turut bersisa $11$ dan $14$. Carilah sisa apabila jumlah kedua bilangan asli tersebut:
a. dibagi $16$;
b. dibagi $8$.

Pembahasan

Alternatif 1: Tanpa Modulo
Anggap saja dua bilangan asli 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$, maka
$a \equiv 11 ~(\text{mod}~16)$ dan $b \equiv 14 ~(\text{mod}~16)$.
Jawaban a)
$$\begin{aligned} a + b & \equiv (11 + 14) ~(\text{mod}~16) \\ & \equiv 25 ~(\text{mod}~16) \\ & \equiv \color{blue}{9} ~(\text{mod}~16) \end{aligned}$$Jadi, sisa pembagiannya adalah $\boxed{9}$
Jawaban b)
$$\begin{aligned} a + b & \equiv 9 ~(\text{mod}~16) \\ & \equiv (9-8) ~(\text{mod}~8) \\ & \equiv \color{blue}{1} ~(\text{mod}~8) \end{aligned}$$Jadi, sisa pembagiannya adalah $\boxed{1}$

[collapse]

Soal Nomor 6
Carilah himpunan bilangan bulat tidak negatif yang setara dengan $122 ~(\text{mod}~7)$.

Pembahasan

Misalkan bilangan bulat itu dinotasikan dengan $n$, maka diperoleh $n \equiv 122 ~(\text{mod}~7)$, yang berarti $n = 7k + 122$ untuk suatu bilangan bulat $k$ dan $n > 0$.
Nilai minimum $k$ adalah $k_{\text{min}} = -17$, sehingga untuk masing-masing nilai $k = -17, -16, -15, \cdots$, diperoleh nilai-nilai $n$ yang dinyatakan dalam himpunan berikut.
$$\{3, 10, 17, 24, 31, \cdots\}.$$

[collapse]

Soal Nomor 7
Carilah bilangan bulat yang habis dibagi $5$ yang kongruen dengan $2 ~(\text{mod}~6)$.

Pembahasan

Misalkan bilangan bulat yang habis dibagi $5$ dinotasikan dengan $5n$ untuk $n \in \mathbb{Z}$, maka diperoleh $5n \equiv 2 ~(\text{mod}~6)$, yang berarti $5n = 6k + 2 \Leftrightarrow k = \dfrac{5n-2}{6}$ untuk suatu bilangan bulat $k$.
Nilai $n$ yang mungkin antara lain $n = \cdots, 4, 10, 16, 22, \cdots$, sehingga bilangan bulat kelipatan $5$ tersebut bila dinyatakan dalam notasi himpunan adalah
$$\{\cdots, 20, 50, 80, 110, \cdots\}.$$

[collapse]

Soal Nomor 8
Carilah bilangan bulat positif yang habis dibagi $7$ yang kongruen terhadap $2 ~(\text{mod}~9)$.

Pembahasan

Misalkan bilangan bulat yang habis dibagi $7$ dinotasikan dengan $7n$ untuk $n \in \mathbb{Z}$, maka diperoleh $7n \equiv 2 ~(\text{mod}~9)$, yang berarti $7n = 9k + 2 \Leftrightarrow k = \dfrac{7n-2}{9}$ untuk suatu bilangan bulat $k$.
Nilai $n$ yang mungkin antara lain $n = \cdots, 8, 17, 26, 35, \cdots$, sehingga bilangan bulat kelipatan $7$ tersebut bila dinyatakan dalam notasi himpunan adalah
$$\{\cdots, 56, 119, 182, 245, \cdots\}$$

[collapse]

Soal Nomor 9
Berapakah sisa hasil bagi $$(34-14\times 25)\times (23 \times 18 + 87)$$ketika dibagi $5$?

Pembahasan

Dengan menggunakan sifat distributif modulo, kita peroleh
$$\begin{aligned} \left((34-14\times 25)\times (23 \times 18 + 87)\right) & \equiv \left((4-0) \times (3 \times 3 + 2)\right)~\text{mod}~5 \\ & \equiv \left(4 \times 11\right)~\text{mod}~5 \\ & \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}~(\text{mod}~5) \\ & \equiv (-1)~(\text{mod}~5) \\ & \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}~(\text{mod}~5) \\ & \equiv 4^{92} \cdot 4^{38}~(\text{mod}~5) \\ & \equiv 4^{130}~(\text{mod}~5) \\ & \equiv (-1)^{130} ~(\text{mod}~5) \\ & \equiv \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. $2222^{5555}$ dibagi oleh $7$.

Pembahasan

Jawaban a)
$$\begin{aligned} 38^{101} & \equiv (3 \times 13-1)^{101}~(\text{mod}~13) \\ & \equiv (-1)^{101}~(\text{mod}~13) \\ & \equiv (-1)~(\text{mod}~13) \\ & \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} 2222^{5555} & \equiv (7 \times 317 + 3)^{5555}~(\text{mod}~7) \\ & \equiv 3^{5555} ~(\text{mod}~7) \\ & \equiv (3^3)^{1851} \cdot 3^2~(\text{mod}~7) \\ & \equiv (4 \times 7-1)^{1851} \cdot 3^2~(\text{mod}~7) \\ & \equiv (-1)^{1851} \cdot 9~(\text{mod}~7) \\ & \equiv -9~(\text{mod}~7) \\ & \equiv 5~(\text{mod}~7) && (\text{ditambah}~14) \end{aligned}$$Jadi, sisa hasil bagi $2222^{5555}$ 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

Perhatikan bahwa 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
$$\begin{aligned} k & = \dfrac{2x-3}{4} \\ 4k & = 2x-3 \\ 2x-4k & = 3 \\ 2(x-2k) & = 3 \end{aligned}$$Persamaan terakhir menunjukkan bahwa ruas kiri bernilai genap, sedangkan ruas kanan ganjil, sehingga untuk sembarang bulat $x$ dan $k$, pernyataan di atas selalu tidak terpenuhi. Jadi, solusi $x$ tidak ada.
Jawaban b)
$x+1 \equiv 3~(\text{mod}~5)$ memiliki arti
$$\begin{aligned} k & = \dfrac{(x+1)-3}{5} \\ 5k & = x-2 \\ 5k+2 & = x \\ x & \equiv 2~(\text{mod}~5) \end{aligned}$$Jadi, solusi persamaan linear kongruensi tersebut adalah $\boxed{x \equiv 2~(\text{mod}~5)}$
Jawaban c)
$$\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 Euclid, 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 Euclid, 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 Euclid, 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(2020\right)^{2015^{2014^{\cdots^{3^{2^{1}}}}}}$ oleh $101$.

Pembahasan

Perhatikan bahwa $2020 \div 101 = 20$. Dengan menggunakan sifat distributif modulo, kita akan mendapatkan
$$\begin{aligned} \left(2020\right)^{2015^{2014^{\cdots^{3^{2^{1}}}}}} & \equiv \left(2020~(\text{mod}~101)\right)^{2015^{2014^{\cdots^{3^{2^{1}}}}}}~(\text{mod}~101) \\ & \equiv 0^{2015^{2014^{\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}_{5555~\text{angka}}$$ oleh $100$?

Pembahasan

Dengan menggunakan sifat-sifat kongruensi modulo, diperoleh
$$\begin{aligned} & (5 \times 55 \times 555 \times \underbrace{555\cdots55}_{5555~\text{angka}})~(\text{mod}~100) \\ & \equiv (5 \times \underbrace{55 \times 55 \times \cdots 55}_{\text{ada}~5554})~(\text{mod}~100) \\ & \equiv (5 \times 55^{5554})~(\text{mod}~100) \\ & \equiv (5^{5555} \times 11^{5554})~(\text{mod}~100) \\ & \equiv (5^{5555} \times (11^{10})^{555} \times 11^4)~(\text{mod}~100) \\ & \equiv (25 \times (01)^{555} \times 41)~(\text{mod}~100) \\ & \equiv (25 \times 41)~(\text{mod}~100) \\ & \equiv 1025~(\text{mod}~100) \\ & \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$. Dengan demikian, karena $6$ dan $8$ relatif prima dengan $49$, berlaku
$$\begin{aligned} 6^{42} & \equiv 1~(\text{mod}~49) \\ 8^{42} & \equiv 1~(\text{mod}~49) \end{aligned}$$Kembali pada soal, kita dapatkan
$$\begin{aligned} (6^{2015} + 8^{2015}) & \equiv (6^{42})^{48} \cdot 6^{-1} + (8^{42})^{48} \cdot 8^{-1})~(\text{mod}~49) \\ & \equiv (1^{48} \cdot 6^{-1} + 1^{48} + 8^{-1})~(\text{mod}~49) \\ & \equiv (6^{-1} + 8^{-1})~(\text{mod}~49) \\ & \equiv (-8-6)~(\text{mod}~49) \\ & \equiv (-14)~(\text{mod}~49) \\ & \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 Euclid bahwa
$$\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}$$Diperoleh 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\}$ sedemikian 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 $n \geq 1$, $n$ bilangan asli. Tentukan sisanya apabila $F_{2020}$ dibagi $5$.

Pembahasan

Soal ini mengacu pada Periode Pisano, yaitu periode barisan Fibonacci 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, pola barisan berlanjut sampai 20 suku, lalu berulang lagi) berdasarkan observasi berikut.
Barisan Fibonacci:
$$\begin{array}{cccccc} 1 & 1 & 2 & 3 & 5 & 8 \\ 13 & 21 & 34 & 55 & 89 & 144 \\ 233 & 377 & 610 & 987 & 1597 & 2584 \\ 4181 & 6765 & 10946 & 17711 & \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 $2020$ habis dibagi $20$, maka $F_{2020} \equiv F_{20} \equiv 0~(\text{mod}~5)$. Jadi, sisa hasil baginya adalah $\boxed{0}$

[collapse]

Tinggalkan Balasan

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *