_olim_matik_sma_blog_koma.png)
Kongruensi (Modulo)
Konsep kongruensi biasa digunakan untuk menyelesaikan soal-soal yang berkaitan:
- Sisa pembagian.
- Menentukan angka satuan dan lainnya.
A). Pengertian Kongruensi
Misalkan $a, b$ bilangan bulat dan $m$ suatu bilangan bulat positif. $a$ kongruen dengan $b$ modulo $m$, dinotasikan $a \equiv b \pmod m$, jika $a$ dan $b$ memiliki sisa yang sama ketika dibagi dengan $m$ (dapat diartikan sebagai $m$ membagi $a - b$). Jika sisa pembagiannya berbeda, maka $a$ tidak kongruen dengan $b$ modulo $m$, dinotasikan $a \not\equiv b \pmod m$ (artinya $m$ tidak membagi $a - b$).
Manakah yang benar dari setiap pernyataan berikut:
- a). $30 \equiv 2 \pmod 7$
- b). $25 \equiv 4 \pmod 6$
- c). $15 \not\equiv 3 \pmod 5$
- d). $46 \not\equiv 5 \pmod 7$
B). Penulisan lain Kongruensi
Bentuk $a \equiv b \pmod m$ dapat ditulis menjadi $a = km + b$ (atau sebaliknya) dengan $k$ adalah bilangan bulat. Bisa diartikan $a \equiv b \pmod m$ adalah $a$ dibagi $m$ bersisa $b$.
- a). bentuk $27 \equiv 2 \pmod 5$ dapat ditulis $27 = 5k + 2$.
- b). bentuk $43 = 3k + 1$ dapat ditulis $43 \equiv 1 \pmod 3$.
- c). bilangan $N$ dibagi 7 bersisa 4 dapat ditulis $N = 7k + 4$ atau $N \equiv 4 \pmod 7$.
C). Sifat-sifat bilangan modulo
Untuk bilangan bulat $a, b, c, d, n$ dan bilangan bulat positif $m$, berlaku sifat-sifat modulo berikut:
- 1). $a \equiv a \pmod m$
- 2). Jika $a \equiv b \pmod m$, maka $b \equiv a \pmod m$
- 3). Jika $a \equiv b \pmod m$ dan $b \equiv c \pmod m$, maka $a \equiv c \pmod m$
- 4). Jika $a \equiv b \pmod m$ dan $c \equiv d \pmod m$, maka
- a). $(a + c) \equiv (b + d) \pmod m$
- b). $(a - c) \equiv (b - d) \pmod m$
- c). $ac \equiv bd \pmod m$
- 5). Jika $a \equiv b \pmod m$ dan $d \mid m$ maka
- a). $a \equiv b \pmod d$
- b). $(a + c) \equiv (b + c) \pmod m$
- c). $(a - c) \equiv (b - c) \pmod m$
- d). $ac \equiv bc \pmod m$
- e). $a^n \equiv b^n \pmod m$
- f). $n \mid a, n \mid b, \text{FPB}(n, m) = 1$, maka $\frac{a}{n} \equiv \frac{b}{n} \pmod m$
- 6). $(am + b)^n \equiv b^n \pmod m$
- 7). Jika $a \equiv b \pmod m$ dan $f(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_0$ maka $f(a) \equiv f(b) \pmod m$
- 8). (Fermat's Little Theorem). Untuk bilangan bulat positif $a$ dan bilangan prima $p$, berlaku:
- a). $a^p \equiv a \pmod p$ untuk setiap $a$.
- b). $a^{p-1} \equiv 1 \pmod p$, syaratnya $\text{FPB}(a, p) = 1$.
- 9). Jika $m, p$ bilangan prima, maka
- a). $(a + b)^m \equiv (a^m + b^m) \pmod m$
- b). $(x_1 + \dots + x_n)^m \equiv (x_1^m + \dots + x_n^m) \pmod m$
- c). jika $a \equiv 1 \pmod{p^n}$ maka $a^p \equiv 1 \pmod{p^n}$
- 10). Jika $a \equiv b \pmod m$, $a \equiv b \pmod n$, dan $\text{FPB}(m, n) = 1$, maka $a \equiv b \pmod{m \times n}$
- 11). Sifat-sifat khusus
- a). Misalkan $n \in \mathbb{N}$ dan $S(n)$ menyatakan penjumlahan digit-digit dari $n$, berlaku $n \equiv S(n) \pmod 9$
- b). $n^5 \equiv n \pmod{10}$ untuk setiap $n \in \mathbb{N}$
- c). $(\pmod{10^n})$ digunakan untuk menentukan $n$ angka terakhir
Diketahui $b$ dibagi 5 bersisa 3 dan $a$ dibagi 5 bersisa $b$. Dalam bentuk bilangan, sisa dari $a$ dibagi 5 adalah ...
Diketahui $b \equiv 3 \pmod 5$ dan $a \equiv b \pmod 5$. Berdasarkan sifat transitif kongruensi, jika $a \equiv b \pmod 5$ dan $b \equiv 3 \pmod 5$, maka $a \equiv 3 \pmod 5$. Jadi, sisa dari $a$ dibagi 5 adalah 3.
Diketahui $a$ dibagi 7 bersisa 5 dan $b$ dibagi 7 bersisa 3. Tentukan sisa pembagian dari:
- a). $(a + b)$ dibagi 7.
- b). $(a - b)$ dibagi 7.
- c). $a \times b$ dibagi 7.
Dari soal diperoleh $a \equiv 5 \pmod 7$ dan $b \equiv 3 \pmod 7$.
- a). $(a + b) \equiv 5 + 3 = 8 \equiv 1 \pmod 7$. Sisa = 1.
- b). $(a - b) \equiv 5 - 3 = 2 \pmod 7$. Sisa = 2.
- c). $a \times b \equiv 5 \times 3 = 15 \equiv 1 \pmod 7$. Sisa = 1.
Diketahui bahwa $6 \equiv 1 \pmod 5$. Tentukan sisa pembagian $2^{2021} \times 3^{2021}$ dibagi 5?
Berdasarkan sifat eksponen, $2^{2021} \times 3^{2021} = (2 \times 3)^{2021} = 6^{2021}$. Karena diketahui $6 \equiv 1 \pmod 5$, maka $6^{2021} \equiv 1^{2021} \equiv 1 \pmod 5$. Jadi, sisa pembagiannya adalah 1.
Tentukan sisa pembagian $25^{2021}$ oleh 8?
Perhatikan bahwa $25 = 3 \times 8 + 1$, sehingga $25 \equiv 1 \pmod 8$. Akibatnya, $25^{2021} \equiv 1^{2021} \equiv 1 \pmod 8$. Jadi, sisa pembagiannya adalah 1.
Terdapat suku banyak $f(x) = 5x^{2021} - 4x^2 + 1$. Tentukan sisa pembagian $f(25^{2021})$ oleh 6?
Karena $25 \equiv 1 \pmod 6$, maka $25^{2021} \equiv 1^{2021} = 1 \pmod 6$. Sisa pembagian $f(25^{2021})$ oleh 6 sama dengan $f(1) \pmod 6$. Hitung $f(1) = 5(1)^{2021} - 4(1)^2 + 1 = 5 - 4 + 1 = 2$. Jadi, sisanya adalah 2.
Tentukan sisa pembagian $8^{2021}$ oleh 11?
Berdasarkan Teorema Kecil Fermat, karena 11 adalah bilangan prima dan $\text{FPB}(8, 11) = 1$, maka $8^{10} \equiv 1 \pmod{11}$. Kita tulis $2021 = 10 \times 202 + 1$. Sehingga $8^{2021} = (8^{10})^{202} \times 8^1 \equiv 1^{202} \times 8 \equiv 8 \pmod{11}$. Jadi, sisanya adalah 8.
Tentukan sisa pembagian $(6^{2021} + 9^{2022})^5$ oleh 5?
Dalam modulo 5: $6 \equiv 1 \pmod 5 \implies 6^{2021} \equiv 1 \pmod 5$. Dan $9 \equiv 4 \equiv -1 \pmod 5 \implies 9^{2022} \equiv (-1)^{2022} = 1 \pmod 5$. Maka $(6^{2021} + 9^{2022})^5 \equiv (1 + 1)^5 = 2^5 = 32 \equiv 2 \pmod 5$. Jadi, sisanya adalah 2.
Tentukan sisa pembagian $8\underbrace{222 \dots 222}_{2021 \text{ kali}} 57$ oleh 9?
Sisa pembagian suatu bilangan oleh 9 sama dengan sisa penjumlahan digit-digitnya oleh 9. Jumlah digit = $8 + 2(2021) + 5 + 7 = 20 + 4042 = 4062$. Jumlah digit dari 4062 adalah $4 + 0 + 6 + 2 = 12$, dan $1 + 2 = 3$. Jadi, sisa pembagiannya adalah 3.
Tentukan angka satuan dan dua angka terakhir dari $7^{3125}$?
1. Angka satuan ($\pmod{10}$): $7^4 \equiv 1 \pmod{10}$. Karena $3125 = 4 \times 781 + 1$, maka $7^{3125} = (7^4)^{781} \times 7 \equiv 1 \times 7 = 7 \pmod{10}$ (Angka satuan = 7).
2. Dua angka terakhir ($\pmod{100}$): $7^4 = 2401 \equiv 1 \pmod{100}$. Maka $7^{3125} \equiv 1^{781} \times 7 = 7 \pmod{100}$ (Dua angka terakhir = 07).
Soal Latihan
Tentukan sisa pembagian jika $8^{2021}$ dibagi oleh 7?
Tentukan angka satuan dari $2007^{2009}$?
Tentukan sisa pembagian $2^{73} + 14^3$ oleh 11?
Tentukan sisa jika $6^{2024}$ dibagi oleh 37?
Tentukan angka satuan dari $7^{7^7}$?
$N$ adalah bilangan asli yang memenuhi $N \equiv 2 \pmod 3$ dan $N \equiv 1 \pmod 2$. Tentukan sisa jika $N$ dibagi 6?
Tentukan dua angka terakhir dari $3^{2009}$?
Jika $10^{999999999}$ dibagi oleh 7, maka sisanya adalah ...
Misalkan $N$ adalah bilangan bulat terkecil yang bersifat: bersisa 2 jika dibagi 5, bersisa 3 jika dibagi oleh 7, dan bersisa 4 jika dibagi 9. Berapakah hasil penjumlahan digit-digit dari $N$?
Berapakah sisa pembagian $43^{43^{43}}$ oleh 100?
Berapakah sisa pembagian $1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3! + \dots + 99 \cdot 99! + 100 \cdot 100!$ oleh 101?
Mana di antara 5 ekspresi $5^{5^{5^5}}$, $6^{6^{6^6}}$, $8^{8^{8^8}}$, $9^{9^{9^9}}$, dan $10^{10^{10^{10}}}$ yang angka terakhirnya berturut-turut bukan 5, 6, 8, 9, atau 0?
Tunjukkan bahwa ada sebanyak tak hingga bilangan komposit $n$ sehingga $n \mid (a^{n-1} - a)$ untuk sebarang bilangan bulat $a$.
Tentukan sebuah bilangan bulat $n$ dengan $100 \le n \le 1997$ sehingga $n$ membagi $2^n + 2$.
Tentukan angka satuan dari $(2012)^{2012}$?
Jika $n = 2011^2 + 2^{2011}$, maka digit satuan dari $n^2$ adalah ...
Diberikan $133^5 + 110^5 + 84^5 + 27^5 = k^5$ dengan $k$ bilangan bulat. Tentukan nilai $k$?
Tentukan bilangan asli terkecil yang jika dipangkatkan tiga akan berakhiran dengan 888?
Tentukan bilangan bulat positif terkecil $a$ dengan $a > 2$ sehingga $2 \mid a$, $3 \mid (a + 1)$, $4 \mid (a + 2)$, $5 \mid (a + 3)$, $6 \mid (a + 4)$.
Untuk setiap bilangan bulat positif $n$, tunjukkan bahwa $10 \times 3^{2n} + 1$ selalu merupakan bilangan komposit.
Buktikan bahwa $2^{5n+1} + 5^{n+2}$ habis dibagi 27 untuk bilangan bulat non negatif $n$.
Kembali ke Daftar Isi Olimpiade Matik SMA
Demikian pembahasan materi Kongruensi (Modulo) Olim Matik SMA dan contoh-contohnya. Silahkan juga baca materi lain yang berkaitan dengan materi ini. Setiap artikel akan diupdate secara bertahap. Jika ada kritik dan saran, atau koreksi dari isi artikel di halaman ini, mohon bantuannya untuk menuliskannya di kolom komentar di bagian bawah setiap artikel. Ini sangat membantu untuk memperbaiki kualitas dari artikel di blog koma. Semoga bermanfaat. Terimakasih.
