Definisi dan Sifat Dasar Bilangan Prima

Bilangan prima adalah bilangan asli yang lebih dari $1$ yang tidak memiliki pembagi selain 1, seperti 2, 3, 5, 7 dan 11, sedangkan 4 dan 6 bukanalah bilangan prima sebab $4 = 2 \times 2$ dan $6 = 2 \times 3$ . 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 $S = \{p_1, p_2, \ldots, p_m\}$ merupakan himpunan semua bilangan prima. Tinjau bilangan $P = p_1p_2\cdots p_m+1$ . Pertama-tama, jelas bahwa dari definisi $P$ , $P$ lebih besar dari semua anggota $S$ sehingga $P$ bukanlah bilangan prima. Akibatnya, $P$ harus memiliki suatu faktor prima $p > 1$ yang merupakan anggota $S$ , misalkan $p = p_k$ . Diperoleh

$p_k \mid P \implies p_k \mid p_1p_2 \cdots p_m + 1 \implies p_k \mid 1$

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 $n$ merupakan bilangan komposit, maka $n$ memiliki faktor prma yang tidak lebih dari $\sqrt{n}$ .[/box]

[learn_more caption=”Bukti:” state=”open”]
Andaikan $n = ab$ di mana $a,b$ merupakan bilangan asli yang lebih dari 1 dan $a$ merupakan faktor terkecil $n$ . Jelas bahwa $a$ merupakan bilangan prima, sebab jika tidak, maka terdapat bilangan asli $p > 1$ yang habis membagi $a$ dan karena $p \mid a$ dan $a \mid n$ , maka $p \mid n$ kontradiksi dengan minimalitas $a$ .
Karena $a$ merupakan faktor terkecil $n$ , maka $a \leq b$ . Diperoleh $n = ab \geq a^2$ sehingga $a \leq \sqrt{n}$ . Jadi, terbukti bahwa $n$ memiliki faktor prima yang tidak lebih dari $\sqrt{n}$ .[/learn_more]

Di sekolah dasar, kita pernah diajarkan untuk mencari faktorisasi prima bilangan-bilangan asli (biasanya menggunakan pohon faktor). Sebagai contoh, $20 = 2^2 \times 5, 92 = 2^2 \times 23$ dan $180 = 2^2 \times 3^2 \times 5$ . 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 $n > 1$ dapat dinyatakan sebagai hasil kali bilangan-bilangan prima secara tunggal. [/box]

[learn_more caption=”Bukti:” state=”open”]
Misalkan $p_1$ merupakan suatu faktor prima $n$ . Jika $p_1 = n$ , maka $n = p_1$ merupakan faktorisasi prima dari $n$ . Jika $p_1 < n$ , maka $n = p_1r_1$ untuk suatu bilangan asli $r_1 > 1$ . Jika $r_1$ prima, maka $n = p_1r_1$ merupakan faktorisasi prima dari $n$ . Jika $r_1$ komposit, diperoleh $r_1 = p_2r_2$ suatu bilangan prima $p_2$ dan bilangan asli $r_2 > 1$ sehingga $n = p_1p_2r_2$ . Jika $r_2$ prima, maka $n = p_1p_2r_2$ merupakan faktorisasi prima $n$ , sedangkan jika $r_2$ komposit, algoritma dapat kita lanjutkan terus menerus hingga diperoleh barisan bilangan asli $r_1 > r_2 > \ldots \leq 1$ . Algoritma ini akan berhenti dengan sebanyak berhingga langkah, sehingga $r_{k-1}$ dan diperoleh $n = p_1p_2 \cdots p_k$ . 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 $n$ yang memiliki dua faktorisasi prima berbeda, yaitu

$n = p_1p_2 \cdots p_k = q_1q_2 \cdots q_h$

dengan $p_1,p_2,\ldots,p_k,q_1,q_2,\ldots,q_h$ prima dengan $p_1 \leq p_2 \leq \ldots \leq p_k$ dan $q_1 \leq q_2 \leq \ldots q_h$ dan $k$ -tupel $(p_1,p_2,\ldots,p_k)$ berbeda dengan $h$ -tupel $(q_1,q_2,\ldots,q_h)$ . Jelas bahwa $k \leq 2$ dan $h \leq 2$ , sebab jika salah satu dari $k$ atau $h$ bernilai 1, maka $n$ harus prima dan jelas bahwa $n$ memiliki faktorisasi prima tunggal. Misalkan pula $n$ merupakan \textbf{bilangan terkecil} yang memiliki dua faktorisasi prima berbeda.

Apabila terdapat $1 \leq i \leq k$ dan $1 \leq j \leq h$ sehingga $p_i = q_j = p$ , maka

$\frac{n}{p} = p_1 \cdots p_{i-1} p_{i+1} \cdots p_k = q_1 \cdots q_{j-1} q_{j+1} \cdots q$

dan diperoleh suatu bilangan asli yang kurang dari $n$ namun memiliki dua faktorisasi prima berbeda. Kontradiksi. Jadi, $p_i \neq q_j$ untuk setiap $1 \leq i \leq k$ dan $1 \leq j \leq h$ . Tanpa mengurangi keumuman, misalkan $p_1 \leq q_1$ . Dengan algoritma pembagian, untuk setiap $i = 1,2,\ldots,h$ , terdapat suatu bilangan asli $r_i$ sehingga $q_i = p_1c_i+r_i$ dengan $1 \leq r_i < p_1$ . Jadi

$n = q_1q_2 \cdots q_h = (p_1c_1+r_1)(p_1c_2+r_2) \cdots (p_1c_h+r_h).$

Perhatikan bahwa dengan mengekspansi $n = (p_1c_1+r_1)(p_1c_2+r_2) \cdots (p_1c_h+r_h)$ , diperoleh $n = mp_1 + r_1r_2 \cdots r_h$ untuk suatu bilangan asli $m$ . Misalkan $n' = r_1r_2 \cdots r_h$ , maka diperoleh $n = p_1p_2 \cdots p_k = mp_1 + n'$ . Akibatnya $n' = n - mp_1$ sehingga $p_1 \mid n'$ dan $n' = p_1s$ untuk suatu bilangan asli $s$ . Jika $s = 1$ , maka $n' = p_1$ merupakan faktorisasi prima dari $n'$ sedangkan jika $s > 1$ kita nyatakan $s$ sebagai perkalian bilangan-bilangan prima, yaitu $s = s_1s_2 \cdots s_v$ . Jadi, $n' = p_1s_1 \cdots s_v$ merupakan faktorisasi prima dari $n$ .

Di sisi lain, karena $r_i < p_1$ maka setiap faktor primanya kurang dari $p_1$ . Akibatnya, jika kita nyatakan $r_1,r_2,\ldots,r_h$ ke dalam hasil kali bilangan-bilangan prima, diperoleh $n' = t_1t_2\cdots t_j$ dengan $t_l$ bilangan prima dan $t_l < p_1$ untuk setiap $l = 1,2,\ldots,j$ . Dari sini, diperoleh $n' = t_1t_2 \cdots t_j = p_1s_1 \cdots s_v$ merupakan dua faktorisasi prima berbeda dari $n'$ . Karena $n' < n$ , diperoleh kontradiksi dengan minimalitas $n$ .[/learn_more]

Dari teorema di atas, dapat disimpulkan bahwa setiap bilangan asli $n > 1$ dapat dinyatakan secara tunggal dalam bentuk

$n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$

di mana $p_1,\ldots,p_k$ adalah bilangan-bilangan prima berbeda dan $\alpha_1,\ldots,\alpha_k$ bilangan asli. Representasi ini seringkali disebut sebagai faktorisasi kanonik dari $n$ .

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 $m$ . Tidak terdapat polinomial $p(x)$ dengan koefsien bulat sedemikian hingga $p(n)$ prima untuk setiap bilangan bulat $n$ dengan $n \geq m$ .[/box]

[learn_more caption=”Bukti:” state=”open”]
Andaikan terdapat polinomial

$p(x) = a_nx^n + a_{n-1}x_{n-1} + \ldots + a_0$

dengan $a_0,a_1,\ldots,a_n$ bulat dan $a_n \leq 0$ sedemikian hingga $p(n)$ prima untuk setiap $n \geq m$ .

Misalkan $p(m) = p$ untuk suatu bilangan prima $p$ . Untuk setiap bilangan asli $i$ . Cukup mudah untuk membuktikan bahwa jika $p(x)$ adalah polinomial dengan koefisien bulat, maka $a-b$ habis membagi $p(a)-p(b)$ untuk setiap bilangan bulat berbeda $a,b$ . Akibatnya, diperoleh $p$ habis membagi $p(m+pi) - p(m)$ untuk setiap bilangan asli $i$ . Namun, karena $p(m) = p$ , maka $p$ habis membagi $p(m+pi)$ . Akan tetapi, karena $m+pi > m$ , maka $p(m+pi)$ prima sehingga $p(m+pi) = p$ untuk setiap bilangan asli $i$ . Ini merupakan kontradiksi, sebab jika dimisalkan $q(x) = p(x) - p$ , maka polinomial $q(x)$ memiliki tak hingga banyak akar sehingga $q(x)$ haruslah polinomial nol dan diperoleh $p$ merupakan polinomial konstan. [/learn_more]

Meskipun tidak ada formula pasti untuk mencari bilangan prima, kita telah mengetahui bagaimana sifat persebaran bilangan prima. Jika $\pi(n)$ sebagai banyaknya bilangan prima yang tidak lebih dari $n$ , sebagai contoh $\pi(10) = 4, \pi(40) = 12$ , maka kita punya

$\lim_{n \to \infty} \dfrac{\pi(n)}{n/\ln n} = 1.$

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 $a$ dan $b$ adalah bilangan asli yang relatif prima, maka terdapat tak hingga bilangan prima pada barisan aritmatika $a,a+b,a+2b,\ldots$ . [/box]

Teorema [Bertrand’s Postulate]
[box] Untuk setiap bilangan asli $n > 1$ , terdapat bilangan prima $p$ yang terletak di antara $n$ dan $2n$ . [/box]

Teorema [Green-Tao Theorem]
[box] Untuk setiap bilangan asli $n$ , terdapat barisan aritmatika dengan $n$ 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 $n$ yang lebih dari 2, dapat dinyatakan sebagai jumlahan dua bilangan prima. [/box]

Konjektur [Twin Prime]
[box] Terdapat tak hingga bilangan prima $p$ sedemikian hingga $p+2$ 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 $n$ sehingga $3n-4,4n-5,5n-3$ semuanya prima.
Buktikan bahwa untuk semua bilangan asli $n > 1$ sehingga $n^5+n^4+1$ .
[OSK 2015] Tentukan semua pasangan bilangan prima $(p,q)$ yang memenuhi persamaan
$(7p-q)^2 = 2(p-1)q^2.$
[OSP 2012] Diketahui $p_0 = 1$ dan $p_i$ menyatakan bilangan prima ke- $i$ untuk $i = 1,2,\ldots$ . Bilangan prima $p_i$ dikatakan \textbf{sederhana} jika
$p_i^{(n^2)} > p_{i=1} (n!)^4$

untuk setiap bilangan asli $n$ . Tentukan semua bilangan prima yang sederhana.
[OSP 2015]
Misalkan $p_1,p_2,\ldots,p_n$ merupakan barisan aritmatika dengan beda $b > 0$ dan $p_i$ prima untuk setiap $i = 1,2,\ldots,n$ .
a. Jika $p_1 > n$ , tunjukkan bahwa untuk setiap bilangan prima $p$ dengan $p \leq n$ , berlaku $p \mid b$ .
b. Berikan contoh barisan aritmatika $p_1,p_2,\ldots,p_{10}$ dengan beda positif dan $p_i$ prima untuk $i = 1,2,\ldots,10$ .
[IMO 2001] Diberikan bilangan asli $a > b > c > d$ yang memenuhi
$ac + bd = (b+d+a-c)(b+d-a+c).$

Buktikan bahwa $ab+cd$ bukan bilangan prima.

Definisi dan Sifat Dasar Bilangan Prima

Published by ricky.the.ising on October 20, 2020October 20, 2020

0 Comments

Leave a Reply Cancel reply

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli

Definisi dan Sifat Dasar Bilangan Prima

Published by ricky.the.ising on October 20, 2020October 20, 2020

0 Comments

Leave a Reply Cancel reply

Related Posts

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli