Bilangan prima adalah bilangan asli yang lebih dari yang tidak memiliki pembagi selain 1, seperti 2, 3, 5, 7 dan 11, sedangkan 4 dan 6 bukanalah bilangan prima sebab
dan
. Bilangan asli yang bukan bilangan prima kita sebut sebagai bilangan komposit.
Sifat yang sangat natural untuk ditanyakan dari definisi bilangan prima adalah apakah terdapat tak hingga banyaknya bilangan prima? Untungnya, bapak penemu geometri, Euclid telah membuktikan sifat ini sekitar 300 tahun sebelum masehi lalu.
Teorema
[box] Terdapat tak hingga banyaknya bilangan prima.[/box]
[learn_more caption=”Bukti:” state=”open”]Andaikan terdapat berhingga bilangan prima dan misalkan merupakan himpunan semua bilangan prima. Tinjau bilangan
. Pertama-tama, jelas bahwa dari definisi
,
lebih besar dari semua anggota
sehingga
bukanlah bilangan prima. Akibatnya,
harus memiliki suatu faktor prima
yang merupakan anggota
, misalkan
. Diperoleh
yang merupakan sebuah kontradiksi.[/learn_more]
Apakah 21 merupakan bilangan prima? Bagaimana dengan 191? Relatif mudah untuk mengecek apakah-apakah bilangan tersebut merupakan bilangan prima, sebab ukurannya yang kecil memungkinkan kita untuk mengecek satu per satu bilangan yang mungkin habis membagi mereka. Namun, bagaimana jika kita perlu mengecek apakah 49587137 prima? Kurang praktis apabila kita harus mengecek semua bilangan yang kurang dari 49587137 membagi 49587137 atau tidak.
Berikut diberikan suatu kriteria untuk mengecek keprimaan suatu bilangan dengan cara yang cukup efisien.
Teorema
[box] Jika bilangan asli merupakan bilangan komposit, maka
memiliki faktor prma yang tidak lebih dari
.[/box]
[learn_more caption=”Bukti:” state=”open”]
Andaikan di mana
merupakan bilangan asli yang lebih dari 1 dan
merupakan faktor terkecil
. Jelas bahwa
merupakan bilangan prima, sebab jika tidak, maka terdapat bilangan asli
yang habis membagi
dan karena
dan
, maka
kontradiksi dengan minimalitas
.
Karena merupakan faktor terkecil
, maka
. Diperoleh
sehingga
. Jadi, terbukti bahwa
memiliki faktor prima yang tidak lebih dari
.[/learn_more]
Di sekolah dasar, kita pernah diajarkan untuk mencari faktorisasi prima bilangan-bilangan asli (biasanya menggunakan pohon faktor). Sebagai contoh, dan
. Faktorisasi prima tidak lain merupakan cara menyatakan suatu bilangan asli sebagai perkalian bilangan-bilangan prima. Namun, apakah semua bilangan asli selalu dapat dinyatakan sebagai perkalian bilangan-bilangan prima? Jawabannya adalah ya! Ini dijamin oleh teorema fundamental aritmatika, yang merupakan landasan utama teori bilangan.
Teorema [Teorema Fundamental Arimatika]
[box] Setiap bilangan asli dapat dinyatakan sebagai hasil kali bilangan-bilangan prima secara tunggal. [/box]
[learn_more caption=”Bukti:” state=”open”]
Misalkan merupakan suatu faktor prima
. Jika
, maka
merupakan faktorisasi prima dari
. Jika
, maka
untuk suatu bilangan asli
. Jika
prima, maka
merupakan faktorisasi prima dari
. Jika
komposit, diperoleh
suatu bilangan prima
dan bilangan asli
sehingga
. Jika
prima, maka
merupakan faktorisasi prima
, sedangkan jika
komposit, algoritma dapat kita lanjutkan terus menerus hingga diperoleh barisan bilangan asli
. Algoritma ini akan berhenti dengan sebanyak berhingga langkah, sehingga
dan diperoleh
. Terbukti bahwa setiap bilangan asli dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.
Selanjutnya, akan kita buktikan bahwa representasi ini tunggal. Diandaikan terdapat bilangan asli yang memiliki dua faktorisasi prima berbeda, yaitu
dengan prima dengan
dan
dan
-tupel
berbeda dengan
-tupel
. Jelas bahwa
dan
, sebab jika salah satu dari
atau
bernilai 1, maka
harus prima dan jelas bahwa
memiliki faktorisasi prima tunggal. Misalkan pula
merupakan \textbf{bilangan terkecil} yang memiliki dua faktorisasi prima berbeda.
Apabila terdapat dan
sehingga
, maka
dan diperoleh suatu bilangan asli yang kurang dari namun memiliki dua faktorisasi prima berbeda. Kontradiksi. Jadi,
untuk setiap
dan
. Tanpa mengurangi keumuman, misalkan
. Dengan algoritma pembagian, untuk setiap
, terdapat suatu bilangan asli
sehingga
dengan
. Jadi
Perhatikan bahwa dengan mengekspansi , diperoleh
untuk suatu bilangan asli
. Misalkan
, maka diperoleh
. Akibatnya
sehingga
dan
untuk suatu bilangan asli
. Jika
, maka
merupakan faktorisasi prima dari
sedangkan jika
kita nyatakan
sebagai perkalian bilangan-bilangan prima, yaitu
. Jadi,
merupakan faktorisasi prima dari
.
Di sisi lain, karena maka setiap faktor primanya kurang dari
. Akibatnya, jika kita nyatakan
ke dalam hasil kali bilangan-bilangan prima, diperoleh
dengan
bilangan prima dan
untuk setiap
. Dari sini, diperoleh
merupakan dua faktorisasi prima berbeda dari
. Karena
, diperoleh kontradiksi dengan minimalitas
.[/learn_more]
Dari teorema di atas, dapat disimpulkan bahwa setiap bilangan asli dapat dinyatakan secara tunggal dalam bentuk
di mana adalah bilangan-bilangan prima berbeda dan
bilangan asli. Representasi ini seringkali disebut sebagai faktorisasi kanonik dari
.
Apakah bilangan prima memiliki pola? Definisi pola sebenarnya cukup rancu, namun jika pola yang dimaksud adalah berbentuk polinomial, maka jawabannya adalah tidak ebagaimana akan kita lihat pada contoh berikut.
Teorema
[box] Diberikan bilangan bulat . Tidak terdapat polinomial
dengan koefsien bulat sedemikian hingga
prima untuk setiap bilangan bulat
dengan
.[/box]
[learn_more caption=”Bukti:” state=”open”]
Andaikan terdapat polinomial
dengan bulat dan
sedemikian hingga
prima untuk setiap
.
Misalkan untuk suatu bilangan prima
. Untuk setiap bilangan asli
. Cukup mudah untuk membuktikan bahwa jika
adalah polinomial dengan koefisien bulat, maka
habis membagi
untuk setiap bilangan bulat berbeda
. Akibatnya, diperoleh
habis membagi
untuk setiap bilangan asli
. Namun, karena
, maka
habis membagi
. Akan tetapi, karena
, maka
prima sehingga
untuk setiap bilangan asli
. Ini merupakan kontradiksi, sebab jika dimisalkan
, maka polinomial
memiliki tak hingga banyak akar sehingga
haruslah polinomial nol dan diperoleh
merupakan polinomial konstan. [/learn_more]
Meskipun tidak ada formula pasti untuk mencari bilangan prima, kita telah mengetahui bagaimana sifat persebaran bilangan prima. Jika sebagai banyaknya bilangan prima yang tidak lebih dari
, sebagai contoh
, maka kita punya
Hasil di atas dikenal sebagai \textit{prime number theorem}. Pembuktian teorema tersebut membutuhkan pengetahuan mengenai teori bilangan analitik (\textit{analytic number theory}) yang mumpuni sehingga tidak akan kita buktikan di tulisan ini. Selain \textit{prima number theorem}, hasil berikut juga tidak kalah cantiknya dan sangat layak untuk diketahui meskipun buktinya sulit.
Teorema [Dirichlet Theorem]
[box] Jika dan
adalah bilangan asli yang relatif prima, maka terdapat tak hingga bilangan prima pada barisan aritmatika
. [/box]
Teorema [Bertrand’s Postulate]
[box] Untuk setiap bilangan asli , terdapat bilangan prima
yang terletak di antara
dan
. [/box]
Teorema [Green-Tao Theorem]
[box] Untuk setiap bilangan asli , terdapat barisan aritmatika dengan
suku yang semua sukunya prima. [/box]
Masih sangat banyak hal yang belum kita ketahui tentang bilangan prima. Berikut adalah dua konjektur yang dapat dikatakan paling terkenal dan paling tua terkait bilangan prima.
Konjektur [Goldbach]
[box]Setiap bilangan genap yang lebih dari 2, dapat dinyatakan sebagai jumlahan dua bilangan prima. [/box]
Konjektur [Twin Prime]
[box] Terdapat tak hingga bilangan prima sedemikian hingga
juga merupakan bilangan prima. [/box]
Semua pembaca dipersilahkan menyelesaikan konjektur-konjektur di atas.
Berikut ini adalah latihan soal terkait dengan bilangan prima.
- Tentukan semua bilangan asli
sehingga
semuanya prima.
- Buktikan bahwa untuk semua bilangan asli
sehingga
.
- [OSK 2015] Tentukan semua pasangan bilangan prima
yang memenuhi persamaan
- [OSP 2012] Diketahui
dan
menyatakan bilangan prima ke-
untuk
. Bilangan prima
dikatakan \textbf{sederhana} jika
untuk setiap bilangan asli
. Tentukan semua bilangan prima yang sederhana.
- [OSP 2015]
Misalkanmerupakan barisan aritmatika dengan beda
dan
prima untuk setiap
.
a. Jika, tunjukkan bahwa untuk setiap bilangan prima
dengan
, berlaku
.
b. Berikan contoh barisan aritmatikadengan beda positif dan
prima untuk
.
- [IMO 2001] Diberikan bilangan asli
yang memenuhi
Buktikan bahwa
bukan bilangan prima.
0 Comments