Konsep Bilangan Prima Dan Teoremanya

Pengertian Bilangan Prima

Pada pembahasan keterbagian kita kenal dengan bagi membagi, $a$ membagi $b$ sama artinya dengan $a$ adalah faktor dari $b$.

Definisi 1

Bilangan bulat positif $p$ dikatakan bilangan prima jika $p$ mempunyai tepat dua faktor positif yaitu $1$ dan $p$ itu sendiri.

Definisi 2

Bilangan bulat positif $n$ dikatakan bilangan komposit jika $n$ mempunyai lebih dari 2 faktor positif. Atau juga bisa dikatakan bahwa $n$ bilangan komposit jika ada bilangan bulat positif $a,b>1$ sehingga $ab=n$.

Teorema 1

Banyak bilangan prima adalah tak hingga

Bukti :

Andaikan hanya ada sejumlah berhingga bilangan prima misalkan $p_1,p_2,p_3,\cdots ,p_k$ dengan $p_1< p_2< p_3 < \cdots < p_k$. Bentuk $N=p_1p_2p_3\cdots p_k+1$, jelas bahwa $N>p_k$. Perhatikan untuk setiap $n=1,2,\cdots ,k$ haruslah $p_n$ tidak membagi $N$ karena jika $p_n$ membagi $N$ maka $p_n$ habis membagi $1$ yang jelas tidak mungkin. Dengan begitu $N$ prima atau terbagi oleh bilangan prima yang lebih dari $p_k$. Ini kontradiksi dengan assumsi kita, jadi ada tak hingga bilangan prima.

Akibat 1

1. Jika $p$ prima maka untuk sebarang bilangan asli berlaku $p$ habis membagi $n$ atau $gcd(p,n)=1$
2. Jika $p$ prima dan $p$ habis membagi $ab$ untuk suatu bilangan bulat $a,b$ maka $p$ habis membagi $a$ atau $p$ habis membagi $b$

Bukti :

1. Jika $p$ habis membagi $n$ maka tidak ada yang perlu dibuktikan. Assumsikan $p$ tidak habis membagi $n$, Misalkan $x=gcd(p,n)$ yang berarti $x$ habis membagi $p$ dan $n$, Jika $x$ habis membagi $p$ karena $p$ prima maka $x=1\ \text{atau}\ p$. Tetapi jika $x=p$ maka berdasarkan assumsi $x$ tidak habis membagi $n$. Jadi, $x=1$ atau $gcd(p,n)=1$.
2. Jika $p$ habis membagi $a$ maka kita selesai. Assumsikan $p$ tidak habis membagi $a$. Maka $gcd(p,a)=1$ dengan begitu kita bisa mencari bilangan bulat $x,y$ yang memenuhi $px+ay=1$. Dengan mengalikan kedua ruas dengan $b$ maka $pbx+aby=b$ atau ekivalen dengan $p(bx)=b-aby$. Akan tetapi $p$ habis membagi $ab$, jadi $p$ juga habis membagi $b$

Akibat 2

Jika $p$ prima dan $n,m$ bilangan asli dengan $p$ habis membagi $n^m$ maka $p$ habis membagi $n$
Bukti :
Perhatikan bahwa $n^m=n\times n\times n\times \cdots\times n$. Berdasarkan akibat sebelumnya maka $p$ habis membagi $n$.