Latihan 2. Uji Keprimaan.
Ingat kembali Teorema Kecil Fermat dari Bab 6. Misalkan \(p\) prima dengan \(\gcd(a, p) = 1\text{.}\) Maka \(a^{p-1} \equiv 1 \pmod{p}\text{.}\) Kita dapat menggunakan Teorema Kecil Fermat sebagai uji penyaring untuk bilangan prima. Sebagai contoh, \(15\) tidak mungkin prima karena
\begin{equation*}
2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}\text{.}
\end{equation*}
Namun, \(17\) berpotensi prima karena
\begin{equation*}
2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}\text{.}
\end{equation*}
Bilangan komposit ganjil \(n\) disebut pseudoprima jika
\begin{equation*}
2^{n-1} \equiv 1 \pmod{n}\text{.}
\end{equation*}
Manakah di antara bilangan berikut yang prima dan manakah yang pseudoprima?
-
\(\displaystyle 342\)
-
\(\displaystyle 811\)
-
\(\displaystyle 601\)
-
\(\displaystyle 561\)
-
\(\displaystyle 771\)
-
\(\displaystyle 631\)