Cara Membuktikan Bilangan Prima

Masih ingat definisi bilangan prima? Bilangan prima adalah bilangan asli yang lebih besar dari 1 yang hanya memiliki dua faktor, yaitu 1 dan bilangan itu sendiri,  sedangkan bilangan asli yang lebih besar dari 1 dan bukan merupakan bilangan prima disebut bilangan komposit.

Himpunan bilangan prima yaitu {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … } sedangkan himpunan bilangan komposit yaitu {4, 6, 8, 9, 10, 12, … }.

Nah, bagaimana 41, apakah termasuk bilangan prima? Ya, karena 41 tidak memiliki faktor yang lain selain 1 dan 41.

Namun, jika bilangan seperti 91 atau yang lebih besar lagi, bagaimana cara mengecek bilangan itu, apakah termasuk bilangan prima atau komposit?

Untuk mengetahui suatu bilangan merupakan bilangan komposit (bukan bilangan prima), tentu kita harus menemukan satu faktor selain 1 dan bilangan itu sendiri.

Misalnya 237  merupakan bilangan komposit karena 237 dapat dibagi dengan 3.

Ada dua cara mengetahui 237 bisa dibagi 3, yaitu pertama mencoba membagi secara langsung hasilnya 79, kedua mengetahui ciri-ciri bilangan dapat dibagi 3.

Karena ciri suatu bilangan dapat dibagi 3 adalah “jumlah digit bilangan itu dapat dibagi 3” dalam hal ini 2+3+7=12 dapat dibagi 3 maka kita simpulkan bahwa 237 dapat dibagi 3.

Selain ciri-ciri bilangan dibagi 3, ada juga ciri-ciri bilangan yang dapat dibagi dengan 2, 4, 5, 6, dsb. yang ini sangat bermanfaat untuk mempercepat menemukan faktor suatu bilangan.

Kalian  dapat membacanya di Ciri-Ciri Bilangan yang Habis Dibagi – Matematikaku Bisa.

Selain dari mengetahui adakah faktor yang lain, kita dapat mengecek bilangan tersebut apakah merupakan  bilangan komposit dengan menggunakan Teorema Bilangan Komposit:

Jika n adalah suatu bilangan komposit maka n memiliki faktor prima p dimana $p \le \sqrt{n}$.

Bukti:

Karena n komposit, maka n=ab dimana $1< a \le b < n$, a dan b bilangan bulat positif.

Dengan kata lain, n memiliki suatu faktor a dan b.

Andaikan $a> \sqrt{n}$, maka $\sqrt{n} < a \le b$ mengakibatkan $ab > \sqrt{n} \sqrt{n}=n$.

Ini bertentangan dengan kenyataan bahwa n=ab sehingga pengandaian salah yang artinya $a \le \sqrt{n}$.

Karena a bilangan bulat positif lebih besar dari 1 maka a memiliki faktor prima $a_1$ yang juga merupakan faktor dari n.

Akibatnya, kita sudah membuktikan bahwa terdapat faktor prima dari n $p \le \sqrt{n}$, yaitu $a_1 \le a \le \sqrt{n}$.

Baca: Membuktikan setiap Bilangan Asli Selain 1 Memiliki Faktor Prima

Contoh: 6 memiliki faktor prima 2 dimana $2 < \sqrt{6}$; 100 memiliki faktor prima 2 dan 5 dimana 2 dan 5 kurang dari 10; dsb.

Dengan menggunakan teorema bilangan komposit di atas, kita dapat menyaring bilangan prima yang kurang dari atau sama dengan n, yaitu dengan cara mendaftar semua bilangan dari 2 sampai n, kemudian menghapus bilangan  komposit dari daftar tersebut yaitu bilangan kelipatan faktor-faktor prima yang tidak lebih dari $\sqrt{n}$, akhirnya yang tersisa tinggal bilangan prima.

Algoritma ini dekenal dengan Saringan Eratosthenes.

Contoh: Tentukan bilangan prima dari 1 sampai 50!

Penyelesaian:

Faktor prima yang kurang dari $\sqrt{50}$ adalah 2, 3, 5, dan 7. Setelah mendaftar bilangan dari 1 sampai 50 dan mengeliminasi bilangan kelipatan 2, 3, 5, dan 7, maka diperoleh bilangan prima dari 1 sampai 50, yaitu {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.

Teorema bilangan komposit jika dikontrasposisikan akan menjadi Teorema Bilangan Prima: “Jika n tidak memiliki faktor prima p dimana $p \le \sqrt{n}$ maka n adalah bilangan prima”.

Contoh 1: Tentukan apakah 91 adalah bilangan prima

Penyelesaian:

Bilangan prima yang kurang dari atau sama dengan $\sqrt{91}$ adalah 2, 3, 5, dan 7. Karena 91 tidak bisa dibagi 2, 3, dan 5, tetapi bisa dibagi 7 maka 91 bukan bilangan prima.

Contoh 2: Tentukan apakah 139 bilangan prima

Penyelesaian:

Bilangan prima yang kurang dari atau sama dengan $\sqrt{139}$ adalah 2, 3, 5, 7 dan 11. Karena 139 tidak bisa dibagi 2, 3, 5, 7, dan 11 maka 139 adalah bilangan prima.

---

Sumber: Wissam Raji, An Introductory Course in Elementary Number Theory (ebook).