Teorema Berkaitan Kongruensi
Untuk setiap bilangan bulat positif \(N\), didefinisikan \(\phi(N)\) adalah banyaknya bilangan bulat positif yang kurang dari atau sama dengan \(N\) yang relatif prima dengan \(N\).
Jelas bahwa \(\phi(1) = 1\) dan \(\phi(p) = p - 1\) untuk setiap bilangan prima \(p\). Untuk bilangan prima \(p\), terdapat \(p^m\) bilangan yaitu \(\{1, 2, 3, \dots, p^m\}\) yang kurang dari atau sama dengan \(p^m\), dan yang merupakan kelipatan dari \(p\) ada sebanyak \(p^{m-1}\) dalam \(\{1, 2, 3, \dots, p^m\}\), sehingga \(\phi(p^m) = p^m - p^{m-1}\).
\[ \phi(p^m) = p^m - p^{m-1} = p^m(1 - p^{-1}) = p^m\left(1 - \frac{1}{p}\right) \]Untuk \(a\) dan \(b\) yang saling relatif prima, maka berlaku \(\phi(a \times b) = \phi(a) \times \phi(b)\).
Misalkan faktorisasi prima \(N\) yaitu:
\[ N = p_1^{k_1} \times p_2^{k_2} \times p_3^{k_3} \times \dots \times p_n^{k_n} \]Maka \(\phi(N) = N\left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\dots\left(1 - \frac{1}{p_n}\right)\) atau:
\[ \phi(N) = p_1^{k_1-1}(p_1 - 1)\dots p_n^{k_n-1}(p_n - 1) \]Dari definisi fungsi Euler, untuk setiap bilangan prima \(p\) maka \(\phi(p) = p - 1\). Berlaku sebaliknya, jika bilangan bulat positif \(n\) dan berlaku \(\phi(n) = n - 1\), maka \(n\) bilangan prima.
Tentukan nilai dari \(\phi(12)\) dan \(\phi(16)\)?
- \(12 = 2^2 \times 3^1\), maka \(\phi(12) = 12 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4\).
- \(16 = 2^4\), maka \(\phi(16) = 16 \left(1 - \frac{1}{2}\right) = 16 \times \frac{1}{2} = 8\).
Misalkan \(a_i\) adalah faktor positif dari 30, maka tentukan hasil dari penjumlahan semua nilai dari \(\phi(a_i)\)?
Faktor-faktor positif dari 30 adalah \(1, 2, 3, 5, 6, 10, 15, 30\).
Berdasarkan sifat umum fungsi Euler \(\sum_{d | n} \phi(d) = n\), maka penjumlahan nilai \(\phi\) untuk semua faktor dari 30 pasti sama dengan 30 itu sendiri.
\[ \phi(1) + \phi(2) + \phi(3) + \phi(5) + \phi(6) + \phi(10) + \phi(15) + \phi(30) = 30 \]Tentukan jumlah semua bilangan bulat positif relatif prima dengan 36 dan kurang dari 36?
Rumus jumlah bilangan bulat positif yang kurang dari \(n\) dan relatif prima dengan \(n\) adalah \(\frac{1}{2} \times n \times \phi(n)\) (untuk \(n > 1\)).
Hitung \(\phi(36)\): Karena \(36 = 2^2 \times 3^2\), maka \(\phi(36) = 36 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 12\).
Maka jumlah semua bilangannya adalah \(\frac{1}{2} \times 36 \times 12 = 216\).
Misalkan \(a\) dan \(n\) bilangan bulat positif yang saling relatif prima, berlaku \(a^{\phi(n)} \equiv 1 \pmod n\).
Tentukan dua angka terakhir dari \(3^{4443}\)?
Mencari dua angka terakhir sama dengan mencari nilai modulo 100.
Karena \(\text{FPB}(3, 100) = 1\), gunakan Teorema Euler: \(\phi(100) = 40\), sehingga \(3^{40} \equiv 1 \pmod{100}\).
Sederhanakan eksponen: \(4443 = 40 \times 111 + 3\).
\[ 3^{4443} = (3^{40})^{111} \cdot 3^3 \equiv 1^{111} \cdot 27 \equiv 27 \pmod{100} \]Jadi, dua angka terakhirnya adalah 27.
Tentukan sisa pembagian \(314^{161}\) dibagi oleh 165?
Basis disederhanakan: \(314 \equiv 149 \pmod{165}\).
Hitung \(\phi(165)\): karena \(165 = 3 \times 5 \times 11\), maka \(\phi(165) = 2 \times 4 \times 10 = 80\).
Berlaku \(314^{80} \equiv 1 \pmod{165}\).
\[ 314^{161} = (314^{80})^2 \cdot 314^1 \equiv 1^2 \cdot 314 \equiv 149 \pmod{165} \]Jadi, sisa pembagiannya adalah 149.
Misalkan \(p\) bilangan prima dan bilangan bulat positif \(a\) relatif prima dengan \(p\), berlaku:
\[ a^{p-1} \equiv 1 \pmod p \]Atau dapat ditulis \(a^p \equiv a \pmod p\).
Teorema kecil Fermat ini merupakan kejadian khusus dari Teorema Euler karena \(\phi(p) = p - 1\).
Tentukan sisa pembagian \(1234^{4005}\) dibagi 2003?
2003 adalah bilangan prima dan \(\text{FPB}(1234, 2003) = 1\). Berdasarkan Teorema Kecil Fermat:
\[ 1234^{2002} \equiv 1 \pmod{2003} \]Membagi eksponen: \(4005 = 2 \times 2002 + 1\).
\[ 1234^{4005} = (1234^{2002})^2 \cdot 1234^1 \equiv 1^2 \cdot 1234 \equiv 1234 \pmod{2003} \]Jadi, sisa pembagiannya adalah 1234.
Tunjukkan bahwa \(n^7 - n\) habis dibagi oleh 42!
Faktorisasi \(42 = 2 \times 3 \times 7\). Kita uji keterbagian dengan faktor-faktor prima tersebut:
- Mod 7: Berdasarkan Teorema Kecil Fermat, \(n^7 \equiv n \pmod 7\), sehingga \(n^7 - n \equiv 0 \pmod 7\).
- Mod 3: \(n^7 - n = n(n^6 - 1) = (n-1)n(n+1)(n^4 + n^2 + 1)\). Perkalian tiga bilangan bulat beruntun \((n-1)n(n+1)\) pasti habis dibagi 3.
- Mod 2: \((n-1)n\) adalah perkalian dua bilangan berurutan, pasti habis dibagi 2.
Karena \(2, 3, 7\) saling relatif prima, maka \(n^7 - n\) habis dibagi oleh \(2 \times 3 \times 7 = 42\).
Tentukan sisa pembagian \(2^{3405}\) dibagi oleh 341?
Perhatikan bahwa \(341 = 11 \times 31\).
Mod 11: \(2^{10} \equiv 1 \pmod{11} \implies 2^{3405} = (2^{10})^{340} \cdot 2^5 \equiv 32 \equiv 10 \pmod{11}\).
Mod 31: \(2^5 = 32 \equiv 1 \pmod{31} \implies 2^{3405} \equiv 1 \pmod{31}\).
Dengan Teorema Sisa China, solusi untuk \(x \equiv 10 \pmod{11}\) dan \(x \equiv 1 \pmod{31}\) adalah \(x = 32\).
Untuk setiap bilangan ganjil \(n\), tentukan bilangan prima terkecil yang dapat membagi \(n^8 + 1\) tetapi tidak membagi \(n^{16} + 1\)?
Misalkan \(p\) adalah bilangan prima pembagi \(n^8 + 1\), maka \(n^8 \equiv -1 \pmod p\). Dikuadratkan menjadi \(n^{16} \equiv 1 \pmod p\).
Jika \(p\) juga membagi \(n^{16} + 1\), maka \(1 \equiv -1 \pmod p \implies p = 2\). Namun karena \(n\) ganjil, \(n^8 + 1\) genap dan \(n^{16} + 1\) juga genap.
Agar \(p\) tidak membagi \(n^{16} + 1\), prima \(p\) harus ganjil dan memenuhi \(16 | (p-1)\). Bilangan prima terkecil yang memenuhi adalah \(p = 17\).
Buktikan bahwa untuk setiap bilangan prima \(p > 2\), bentuk \(1^p + 2^p + 3^p + \dots + (p - 1)^p\) habis dibagi \(p\).
Berdasarkan Teorema Kecil Fermat, untuk setiap \(1 \le k \le p-1\), berlaku \(k^p \equiv k \pmod p\).
\[ 1^p + 2^p + \dots + (p-1)^p \equiv 1 + 2 + \dots + (p-1) \pmod p \]Jumlah deret aritmatika tersebut adalah \(\frac{(p-1)p}{2} = p \times \left(\frac{p-1}{2}\right)\).
Karena \(p > 2\) ganjil, \(\frac{p-1}{2}\) bulat, sehingga jumlah tersebut kelipatan dari \(p\).
Jika \(p\) merupakan bilangan prima, berlaku:
\[ (p - 1)! + 1 \equiv 0 \pmod p \]Dengan kata lain \((p - 1)! + 1\) kelipatan dari \(p\).
Tentukan sisa pembagian dari bentuk \(1! + 2! + 3! + 10! + 11! + 12! + 13! + \dots + 2022!\) jika dibagi oleh 11?
Untuk setiap suku \(k \ge 11\), \(k!\) mengandung faktor 11 sehingga habis dibagi 11.
Berdasarkan Teorema Wilson, \(10! \equiv -1 \equiv 10 \pmod{11}\).
Total modulo 11: \(1! + 2! + 3! + 10! \equiv 1 + 2 + 6 + 10 = 19 \equiv 8 \pmod{11}\).
Jadi, sisa pembagiannya adalah 8.
Misalkan \(p\) adalah bilangan prima ganjil. Buktikan bahwa \(1^2 \cdot 3^2 \cdot 5^2 \dots (p - 2)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p\), begitu juga \(2^2 \cdot 4^2 \cdot 6^2 \dots (p - 1)^2 \equiv (-1)^{\frac{p+1}{2}} \pmod p\).
Gunakan Teorema Wilson \((p-1)! \equiv -1 \pmod p\), lalu substitusikan suku genap dengan bentuk negatif modulo \(p\) untuk membuktikan keselarasan kuadrat tersebut.
Misalkan bilangan bulat positif \(m_1, m_2, m_3, \dots, m_k\) saling relatif prima, \(M = m_1 m_2 \dots m_k\), \(M_i = \frac{M}{m_i}\). Sistem persamaan \(x \equiv b_i \pmod{m_i}\) mempunyai solusi tunggal modulo \(M\):
\[ x = b_1 M_1 N_1 + b_2 M_2 N_2 + \dots + b_k M_k N_k \pmod M \]di mana \(N_i \cdot M_i \equiv 1 \pmod{m_i}\).
Tentukan semua bilangan bulat \(x\) yang memenuhi sistem persamaan \(x \equiv 2 \pmod 3\), \(x \equiv 3 \pmod 5\), dan \(x \equiv 4 \pmod 7\).
\(M = 3 \times 5 \times 7 = 105\).
- \(M_1 = 35 \implies 35 N_1 \equiv 1 \pmod 3 \implies N_1 = 2\).
- \(M_2 = 21 \implies 21 N_2 \equiv 1 \pmod 5 \implies N_2 = 1\).
- \(M_3 = 15 \implies 15 N_3 \equiv 1 \pmod 7 \implies N_3 = 1\).
Sebuah bilangan dibagi 2 bersisa 1, dibagi 3 bersisa 2, dibagi 5 bersisa 2 dan dibagi 7 bersisa 1. Tentukan bilangan terkecil yang memenuhi.
Sistem kongruensi eivalen: \(x \equiv -1 \pmod 2\), \(x \equiv -1 \pmod 3 \implies x \equiv 5 \pmod 6\). Digabungkan dengan kondisi lainnya menghasilkan bilangan positif terkecil \(x = 17\).
Kembali ke Daftar Isi Olimpiade Matik SMA
Demikian pembahasan materi Teorema Berkaitan Kongruensi 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.
