Cara Mudah Membuktikan Bilangan Prima

Pada artikel terdahulu, saya pernah membahas tentang cara mudah untuk mencari bilangan prima dengan metode saringan. Namun, metode tersebut pun terbilang masih sangat tidak efisien untuk bilangan prima yang nilainya sampai ribuan atau bahkan jutaan. Pertanyaannya sekarang, adakah metode atau cara untuk mengecek bahwa suatu bilangan itu termasuk bilangan prima atau bukan? Ada banyak jawaban untuk pertanyaan ini. Berbagai metode saat ini telah banyak muncul untuk tertama metode dengan menggunakan komputer. Lalu bagaimana jika kita sedang ujian dan butuh secepatnya tahu apakah suatu bilangan termasuk bilangan prima tau bukan. Berikut ini akan kita bahas salah satu metode untuk mengecek atau membuktikan bilangan prima. Bagaimana caranya? Mari kita pelajari!

Metode ini berkaitan erat dengan teori bilangan jadi untuk pelajar tingkat SMA ataupun SMP bisa langsung melihat contoh penggunaannya tanpa melihat bagaimana pembuktian teorema berikut. Pasalnya, mungkin ada beberapa bagian yang agak sulit dipahami karena teori bilangan tidak secara khusus dibahas di tingkat SMP dan SMA. Teorema tersebut berbunyi sebagai berikut:

Teorema Bilangan Komposit:

Jika n suatu bilangan komposit maka n memiliki faktor k dengan

Teorema tersebut belum secara langsung menyebut tentang bilangan prima, tetapi akibat dari terbuktinya teorema ini akan membawa kita pada metode yang akan kita gunakan. Apakah teorema di atas benar-benar sudah terbukti? Mari kita buktikan saja!

Bukti:

Diketahui n suatu bilangan komposit. Oleh karena itu, pasti ada bilangan positif k dan m dimana

Kita asumsikan bahwa nilai k dan m lebih dari akar n.

Akibatnya,

Padahal km = n Sehingga terjadi kontradiksi. Ini artinya salah satu dari k atau m haruslah kurang dari akar n. Jadi,

Teorema terbukti.

Teorema di atas telah terbukti artinya setiap bilangan komposit pasti memiliki akar yang kurang dari akar n dan lebih besar dari satu. Karena teorema di atas telah terbukti artinya kontraposisi dari teorema di atas juga terbukti dan berlaku. Sekarang kita lihat kontraposisi dari teorema diatas yaitu sebagai berikut:

Teorema Bilangan Prima:

Jika suatu bilangan n tidak memiliki faktor k dengan nilai k lebih dari 1 dan kurang dari sama dengan akar n, maka n bukan bilangan komposit. Dengan kata lain:

Jadi, berdasarkan teorema di atas asalkan kita bisa membuktikan bahwa n tidak memiliki faktor k tersebut maka n adalah bilangan prima. Simpel bukan? Bagaimana aplikasinya? Mari kita lihat contoh berikut:

Contoh 1:

Apakah bilangan berikut adalah bilangan prima?

a.       51

b.      139

Jawaban poin a:

Bilangan prima yang kurang dari 8 adalah 2, 3, 5, 7. Jika 53 tidak bisa dibagi bilangan prima tersebut maka 51adalah bilangan prima. Mari kita cek!

Jadi, 51 adalah bilangan komposit.

Jawaban poin b:

Bilangan prima yang kurang dari 12 yaitu 2, 3, 5, 7, 11. Jadi jika 123 tidak terbagi oleh bilangan prima tersebut maka 139 adalah bilangan prima. Mari kita cek!

Karena 139 tidak memiliki faktor k yang kurang dari 12 maka 139 adalah bilangan prima.

Cukup mudah bukan? Mari kita coba untuk bilangan yang lebih besar.

Contoh 2:

Buktikan bahwa 2173 adalah bilangan prima!

Jawab:

Bilangan prima yang kurang dari 47 adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, dan 43. Kita harus mengecek apakah 2167 terbagi oleh bilangan prima di atas.

Ternyata tidak terbukti. Jadi bilangan 2173 adalah bilangan komposit.

Metode ini dapa diterapkan pada program komputer untuk membuat suatu aplikasi yang bisa mendekteksi apakah suatu bilangan itu prima atau bukan. Caranya tentu dengan menjadikan prosedur di atas sebagai algoritma. Silahkan dicoba!

Ini hanyalah salah satu metode untuk membuktikan bilangan prima. Dilain waktu akan kita bahas metode yang lain. Sekian artikel kali ini tentang membuktikan bilangan prima. Silahkan jika ada pertanyaan bisa tulis di kolom komentar.