1. Mengapa \(5^k \mod 77\) Kelihatan Tidak Beraturan?
Ketika kita menghitung \(5^k \mod 77\) untuk \(k = 1, 2, \dots, 20\), hasilnya tampak tidak langsung menunjukkan pengulangan yang jelas:
Ini terjadi karena periode (pengulangan) penuhnya lebih panjang dari 20 langkah. Faktanya, modulus \(77 = 7 \times 11\) adalah bilangan komposit, dan periode \(5^k\) modulo 77 adalah KPK dari periode modulo 7 dan modulo 11, yaitu:
- Periode modulo 7 = 6
- Periode modulo 11 = 5
- KPK(6, 5) = 30
Jadi, \(5^{k+30} \equiv 5^k \pmod{77}\) untuk semua \(k\), tetapi kita tidak melihat \(k=30\) dalam data awal. Karena kita hanya melihat sampai \(k=20\), kita hanya melihat sebagian dari satu siklus penuh, sehingga terkesan acak.
2. Mengapa mod 7 & mod 11 Punya Pola Pendek, Sedangkan mod 77 Panjang?
Ini adalah konsekuensi dari Teorema Sisa Tiongkok (Chinese Remainder Theorem).
Setiap hasil \(5^k \mod 77\) sebenarnya adalah sepasang nilai:
Modulo 7:
\(5^1 \equiv 5\), \(5^2 \equiv 4\), \(5^3 \equiv 6\), \(5^4 \equiv 2\), \(5^5 \equiv 3\), \(5^6 \equiv 1\), lalu berulang → periode 6.
Modulo 11:
\(5^1 \equiv 5\), \(5^2 \equiv 3\), \(5^3 \equiv 4\), \(5^4 \equiv 9\), \(5^5 \equiv 1\), lalu berulang → periode 5.
Agar pasangan \((a \mod 7, b \mod 11)\) kembali sama seperti saat \(k=1\), kita perlu \(k\) yang merupakan kelipatan 6 dan 5 → KPK(6,5) = 30.
Jadi, periode modulo 77 = 30, lebih panjang daripada periode masing-masing komponennya.
3. Contoh Kecil Pola Pendek vs Panjang
Mari kita bandingkan pola dari masing-masing modulus:
Mod 7 (periode 6):
\[
[5, 4, 6, 2, 3, 1]
\]
Mod 11 (periode 5):
\[
[5, 3, 4, 9, 1]
\]
Sekarang lihat beberapa nilai \(5^k \mod 77\):
- \(k=1\): \((5,5) \to 5\)
- \(k=2\): \((4,3) \to 25\)
- \(k=3\): \((6,4) \to 48\)
- \(k=4\): \((2,9) \to 9\)
- \(k=5\): \((3,1) \to 45\)
- \(k=6\): \((1,5) \to 71\)
- \(k=7\): \((5,3) \to 47\)
- \(\dots\)
Perhatikan bahwa urutan pasangan \((a,b)\) baru akan kembali ke \((5,5)\) saat \(k = 30\), karena 30 adalah KPK(6,5).
Kesimpulan
- Mod 77 memiliki pola panjang 30 karena merupakan gabungan dari dua modulus prima berbeda dengan periode 6 dan 5.
- Data terbatas (hanya 20 suku) tidak cukup untuk melihat pengulangan penuh, sehingga terlihat acak.
- Dengan memahami struktur modulus komposit dan Chinese Remainder Theorem, kita tahu pasti ada pola, meski tersembunyi dalam cuplikan data kecil.
Ini adalah contoh bagus mengapa dalam kriptografi (seperti RSA dengan modulus \(n = pq\)), panjang periode pangkat bisa sangat besar, sehingga sulit ditekan tanpa mengetahui faktorisasi \(n\).