BILANGAN PRIMA

Tugas Kelompok

Teori Bilangan

Bilangan Prima

Disusun Oleh:

Kelompok 6

No.	Nama	NIM
1	Wahyu Indah Lestari	10536 4623 13
2	Siti Fahmia	10536 4632 13
3	Ayu Oktaviani Azhari	10536 4653 13
4	Linda Puspitasari	10536 4654 13

Kelas 2013 E

PROGRAM STUDI PENDIDIKAN MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

UNIVERSITAS MUHAMMADIYAH MAKASSAR

2014

KATA PENGANTAR

Puji syukur kehadirat Tuhan Yang Maha Esa, atas rahmat dan karunia-Nya, sehingga penyusun dapat menyelesaikan makalah Teori Bilangan “Bilangan Prima”

Pada dasarnya makalah ini disusun untuk memenuhi tugas mata kuliah Teori Bilangan.Dalam pembuatan makalah ini, penulis mendapat bantuan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terima kasih yang sebesar-besarnya kepada : Ahmad Syamsuadi, S.Pd.yang telah memberikan kesempatan dan memberi fasilitas sehingga makalah ini dapat selesai dengan lancar. Dan terima kasih pula kami ucapkan kepada bapak dan ibu dirumah yang telah memberikan bantuan materil maupun do’anya, sehingga pembuatan makalah ini dapat terselesaikan. Semua pihak yang tidak dapat penulis sebutkan satu persatu yang membantu pembuatan makalah ini.

Akhir kata semoga makalah ini bisa bermanfaat bagi pembaca pada umumnya dan penulis pada khususnya, penulis menyadari bahwa dalam pembuatan makalah ini masih jauh dari sempurna untuk itu penulis menerima saran dan kritik yang bersifat membangun demi perbaikan kearah kesempurnaan. Akhir kata penulis sampaikan terimakasih. 

Makassar, Oktober 2014

Penyusun

DAFTAR ISI

Kata Pengantar.................................................................................................................... i

Daftar Isi............................................................................................................................... ii

BAB I PENDAHULUAN................................................................................................... 1

A.    Latar Belakang........................................................................................................... 1

B.     Rumusan Masalah...................................................................................................... 1

C.     Tujuan........................................................................................................................ 1

BAB II PEMBAHASAN..................................................................................................... 2

A.    Sejarah dan Perkembangan Bilangan Prima.......................................................................... 2

B.     Rumus Bilangan Prima.......................................................................................................... 9

C.     Teorema Bilangan Prima........................................................................................................ 13

D.    Faktorisasi Tunggal................................................................................................................ 19

E.     Fungsi Tau ( ) dan Sigma ( )................................................................................................... 28

BAB III PENUTUP............................................................................................................. 41

A.    Kesimpulan............................................................................................................................ 41

B.     Saran...................................................................................................................................... 43

DAFTAR PUSTAKA......................................................................................................... 44

BAB I

PENDAHULUAN

A.    Latar Belakang

Bilangan prima memiliki kekhususan dan peran penting yang tidak dimiliki bilangan lain. Selain itu, berbagai kontroversi rumus dan banyaknya bilangan prima juga belum dapat dijelaskan secara tuntas. Dengan adanya pernyataan di atas maka dari itu kami sebagai mahasiswa matematika terdorong untuk menyusun makalah yang berjudul Bilangan Prima.

B.     Rumusan Masalah

Adapun rumusan masalah dalam makalah ini adalah :

1.    Bagaimana sejarah dan perkembangan bilangan prima?

2.    Bagaimana menentukan bilangan prima dengan menggunakan rumus?

3.    Apa-apa sajakah teorema dari bilangan prima?

4.    Bagaimana cara menentukan hasil kali faktor-faktor bilangan prima sehingga menghasilkan faktorisasi tunggal?

5.    Bagaimana menyatakan suatu fungsi tau ( ) dan fungsi sigma ( )?

C.    Tujuan

Tujuan dari makalah ini adalah :

1.    Untuk mengetahui sejarah dan perkembangan bilangan prima

2.    Untuk mengetahui cara menentukan bilangan prima dengan menggunakan suatu rumus

3.    Untuk mengetahui dan dapat membuktikan teorema dari bilangan prima

4.    Untuk mengetahui cara menentukan hasil kali faktor-faktor bilangan prima sehingga menghasilkan faktorisasi tunggal

5.    Untuk mengetahui dan menyatakan suatu fungsi tau ( ) dan fungsi sigma ( )

BAB II

PEMBAHASAN

A.    Sejarah dan Perkembangan Bilangan Prima

Manusia telah mengenal bilangan prima sejak 6500 sebelum masehi (S.M.). tulang Ishango yang ditemukan pada tahun 1960 (sekarang disimpan di Musse d’Histoire Naturelle di Brussels) membuktikan hal tersebut. Tulang Ishango memiliki 3 baris takik. Salah satu kolomnya memiliki 11, 13, 17 dan 19 takik, yang merupakan bilangan prima antara 10 dan 20.

Sekitar abad 6 S.M., Phythagoras dan kelompoknya telah mempelajari sifat-sifat bilangan, antara lain : bilangan sempurna (perfect numbers), bilangan sekawan (amicable numbers), bilangan segi banyak(polygonal numbers) dan bilangan prima (prime numbers). Selanjutnya, sekitar abad ke empat SM, Euclides mengembangkan konsep dasar teori bilangan. Beberapa jenis bilangan khusus akan dikemukakan, namun pengertian pembagi dan pembagi sejati perlu dikemukakan lebih dahulu.

Pembagi (kadang disebut faktor) dari sebuah bilangan bulat adalah bilangan yang dapat membagi bilangan itu tanpa adaa sisa. Misalnya pembagi dari 12 adalah . Pembagi sejati (proper divisors) adalah pembagi sebuah bilangan yang kurang dari bilangan itu sendiri. Misalnya pembagi sejati dari 12 adalah . Selanjutnya, beberapa bilangan khusus dikemukakan sebagai berikut.

1.    Bilangan Berlimpah (Abundant Numbers)

Jika sebuah bilangan dengan jumlah pembagi sejatinya lebih dari bilangan itu sendiri disebut bilangan berlimpah. Misalnya, pembagi sejati 24 adalah  dan 1+2+3+4+6+8+12=36 adalah bilangan berlimpah karena 36>24.

2.    Bilangan Berkekurangan (Deficient Numbers)

Jika jumlah pembagi sejati sebuah bilangan kurang dari bilangan itu sendiri, maka bilangan itu disebut berkekurangan. Misalnya, 16 adalah bilangan berkekurangan karena jumlah pembagi sejatinya  adalah 1+2+4+8=1<16.

3.    Bilangan Sempurna (Perfect Numbers)

Sebuah bilangan disebut sempurna apabila jumlah pembaginya sama dengan bilangan itu sendiri. Misalnya, 6 adalah bilangan sempurna karena pembagi 6 adalah 1,2 dan 3 serta 1+2+3=6.

4.    Bilangan Mungil (cute numbers)

Jika sebuah bilangan kuadrat dapat dibagi ke dalam n kuadrat pada paling banyak dua ukuran berbeda, maka n disebut bilangan mungil. Misalnya 4 dan 10 adalah bilangan mungil.

5.    Bilangan Setengah Sempurna (semiperfect numbers)

Sebuah bilangan setengah sempurna apabila sama dengan jumlah sebagian pembagi sejatinya. Misalnya, misalnya 18 adalah bilangan setengah sempurna karena pembagi sejati 18 adalah  dan 3+6+9=18. Sebuah bilangan setengah sempurna yang merupakan jumlah dari semua pembagi sejatinya disebut bilangan sempurna.

6.    Bilangan Berbahagia (happy numbers)

Sebuah bilangan yang jumlah kuadrat angka-angkanya pada akhirnya berjumlah satu disebut bilangan berbahagia. Misalnya 203 adalah bilangan berbahagia, karena + + =13, + =10, + =1.

7.    Bilangan Narsis (narcissistic numbers)

Seorang narsis  jika tertarik kepada dirinya sendiri, sebuah bilangan narsis nampaknya sedikit terpusat pada dirinya juga. Sebuah bilangan narsis adalah sebuah bilangan yang sama dengan sebuah pernyataan yang menggunakan angka yang sama. Misalnya 36= 3! 6. Kadang-kadang sebuah bilangan narsis didefenisikan sebagai bilangan yang sama dengan jumlah angka-angkanya yang berpangkat tertentu. Lebih khusus, sebuah bilangan dengan n angka sama dengan jumlah angka-angkanya yang berpangkat tertentu. Lebih khusus, sebuah bilangan dengan n angka sama dengan jumlah angka-angkanya berpangkat n. Misalnya,  371 adalah bilangan narsis karena 371=  dan 9474 juga bilangan narsis karena

8.    Bilangan Palindrom (palindromic numbers)

Sebuah polindrom adalah kata yang sama baik dibaca dari kiri maupun kanan, misalnya noon atau kayak. Bilangan polindrom, seperti 88 dan 1640461 mempunyai angka yang sama baik dibaca dari kiri maupun dari kanan.

9.    Bilangan bersahabat (amicable numbers)

Dua bilangan disebut bersahabat apabila jumlah pembagi  sejati bilangan pertama sama dengan bilangan kedua dan juga sebaliknya jumlah pembagi sejati bilangan kedua sama dengan bilangan pertama. Misalnya, 2620 dan 2924 adalah dua bilangan bersahabat. Pembagi sejati 2620 adalah  yang jumlahnya .

Selanjutnya, kita memeriksa pembagi sejati 2924, yaitu  dan jumlahnya . Dengan demikian, kedua bilangan itu bersahabat.

10.    Bilangan Sosial (sociable numbers)

Bilangan sosial seperti bilangan bersahabat, tetapi bilangan sosial dalam kelompok yang lebih besar. Pembagi sejati dari bilangan pertama dalam sebuah kelompok jumlahnya sama dengan bilangan kedua, pembagi sejati bilangan kedua jumlahnya sama dengan bilangan ketiga, dan seterusnya. Pembagi sejati bilangan terakhir dalam kelompok jumlahnya sama dengan bilangan pertama. Bilangan sosial cenderung besar, sehingga sulit didapatkan tanpa menggunakan komputer. Satu contoh kelompok bilangan sosial adalah 12496, 14288, 15472, 14536 dan 14264.

11.    Bilangan Berpola (figurate numbers)

Bilangan dari titik dalam sebuah susunan titik-titik yang berjarak sama disebut bilangan berpola. Misalnya:

Titik-titik dapat disusun dalam dimensi satu, dua, tiga atau lebih. Ada banyak jenis bilangan berpola, misalnya bilangan polygon (polygonal numbers) dan bilangan tetrahedral (tetrahedral numbers).

12.    Bilangan Poligon (polygonal numbers)

Sebuah bilangan poligon adalah bilangan titik yang berjarak sama diperlukan untuk menggambar sebuah bilangan berpola. Barisan bilangan poligon berdasarkan pada poligon tersarang. Contohnya:

Terdapat banyak jenis berbeda dari bilangan poligon, mulai dengan bilangan kuadrat dan bilangan segitiga.

13.    Bilangan Kuadrat (square numbers)

Bilangan kuadrat adalah hasil perkalian sebuah bilangan dengan dirinya sendiri. Ini adalah sama dengan kuadrat sempurna (perfect squares): =1, =4, =9 dan seterusnya. Kuadrat dari 5 adalah 25 dan bekerja dari belakang, kita mengatakan bahwa akar kuadrat dari 25 adalah 5. Beberapa gambar bilangan kuadrat diberikan sebagai berikut.

14.    Bilangan Kubik (cube numbers)

Bilangan kubik adalah hasil dari perkalian sebuah bilangan  dengan dirinya sendiri dua kali : =1, =8, =27 dan seterusnya. Kubik dari 4 adalah 64 dn bekerja dari belakang, kita mengatakan bahwa akar pangkat tiga dari 64 adalah 4. Jika kita menggunakan balok bentuk kubik (kubus) untuk membangun sebuah kubik lebih besar, banyaknya balok yang diperlukan adalah sebuah bilangan kubik. Misalnya, kita akan membangun kubik 10 cm dengan menggunakan kubik 1 cm kita membutuhkan 1000 kubik.

15.    Bilangan Tetrahedral (tetrahedral numbers)

Bilangan tetrahedral adalah satu jenis bilangan berpola yang diperoleh dengan menghitung banyaknya titik berjarak sama yang diperlukan untuk membangun sebuah tetrahedron. Tetrahedron adalah piramid dengan dasar segitiga.

16.    Bilangan Segitiga (triangular numbers)

Sebuah bilangan segitiga adalah banyaknya titik yang diperlukan untuk menggambar sebuah segitiga. Ini adalah satu jenis bilangan berpola. Beberapa gambar bilangan segitiga yang pertama diberikan sebagai berikut:

Rumus bilangan segitiga ke-n adalah T(n)=n(n+1)/2.

17.    Bilangan Aneh (weird numbers)

Sebuah bilangan aneh (tidak wajar) apabila berlimpah tetapi tidak setengah sempurna, misalnya 70 adalah bilangan aneh. Pembagi sejati 70 adalah dan , tetapi 70 tidak sama dengan jumlah beberapa pembagi sejatinya.

Sebelum komputer ditemukan, perkembangan penemuan bilangan prima masih lambat karena orang belum merasakan manfaatnya. Meski pun sedikit sekali manfaat yang diketahui, namun di awal masehi orang-orang tetap mencari dan membuktikan bahwa suatu bilangan merupakan bilangan prima.

Bilangan prima disebut oleh Nicomachus, Theon dan Lamblichus sebagai “bilangan prima dan tidak komposit”. Theon mendefenisikan hampir sama dengan yang didefenisikan oleh Euclid, yaitu “bilangan yang tidak dihasilkan oleh sebarang bilangan, melainkan oleh hanya satu satuan saja”. Satuan berarti bilangan asli yang bukan bilangan prima dan juga bukan bilangan komposit. Aristotheles juga mengatakan bahwa bilangan prima tidak dihasilkan oleh sebarang bilangan, sebuah satuan bukan merupakan bilangan, tetapi hanya permulaan bilangan (Theon dari Smyrna mengatakan hal yang sama). Menurut Nicomachus, bilangan prima adalah sebuah subbagian, bukan dari sembarang bilangan melainkan dari bilangan yang ganjil, yaitu “bilangan ganjil yang tidak berlaku untuk bagian yang lain kecuali bagian yang disebutkan setelah nama bilangan iu sendiri”. Bilangan prima adalah 3, 5, 7 dan seterusnya. Dan tidak ada subkelipatan dari 3 kecuali 1/3, tidak ada subkelipatan dari 11 kecuali 1/11 dan seterusnya.

Dalam kasus ini satu-satunya subkelipatan tersebut adalah satuan. Menurut Nicomachus, 3 adalah bilangan prima yang pertama sedangkan Aristotheles menganggap 2 sebagian bilangan prima: (2 adalah satu-satunya bilangan genap yang prima), hal ini menunjukkan bahwa perbedaan doktrin phytagorean lebih awal dari Euclid. Angka 2 juga memperkuat defenisi Euclid terhadap bilangan prima. Lamblichus menjadikan ini sebagai dasar serangan lain terhadap Euclid. Argumentasinya adalah bahwa 2 adalah satu-satunya angka genap yang tidak memiliki bagian kecuali sebuah satuan. Namun, sebelumnya dijelaskan bahwa genap kali genap, ganjil kali ganjil dan ganjil kali genap, semuanya tidak termasuk sifat bilangan prima. Telah dijelaskan bahwa kemungkinan besar 2 adalah bilangan genap dan ganjil, yang dihasilkan dengan mengalikan 2 terhadap bilangan ganjil yakni satuan tersebut, sehingga 2 dianggap sebagai batas atas subbagian bilangan genap, yang bukan termasuk bilangan prima. Theon memandang 2 dalam anggapan yang sama, tetapi mendukungnya dengan lingkaran yang nyata. Bilangan prima menurutnya, juga disebut ganjil-kali-ganjil, sehingga hanya bilangan ganjil yang prima dan tidak komposit. Bilangan genap tidak dihasilkan oleh hanya satu satuan, kecuali 2, sehingga terlihat ganjil tetapi tidak prima.

Terdapat beragam nama yang digunakan terhadap bilangan prima. Kita telah memperhatikan penandaan yang aneh terhadapnya yaitu ganjil kali ganjil. Menurut Lamblichus, beberapa orang menyebutnya euthimetric dan thimaridas rectilinier, dengan dasar bahwa ia hanya dapat ditemukan dalam satu dimensi tanpa luasan. Aspek yang sama dari bilangan prima juga dinyatakan oleh Aristotheles, yang membedakan bilangan komposit dengan bilangan prima yang hanya memiliki satu dimensi. Theon dari Smyrna memberikan linear sebagai nama alternatif dari rectilinear. Dalam kedua kasus, untuk membuat deskripsi yang pas terhadap bilangan prima, kita harus memahami kata hanya, “bilangan prima adalah bilangan yang hanya linear atau rectilinear”. Bagi Nicomachus, yang menggunakan bentuk linear, dengan jelas mengatakan bahwa semua bilangan juga begitu, yakni dapat dipresentasikan oleh titik-titik linear untuk jumlah yang dibutuhkan dan ditetapkan pada seruas garis.

Bilangan prima disebut prima atau pertama,menurut nicomachus,karena hanya dapat diperoleh dengan meletakkan sejumlah satuan tertentu bersama,dan satuan tersebut adalah permukaan dari bilangan.Menurut lamblichus,karena tidak ada bilangan sebelumnya,bilangan prima menjadi kumpulan satuan yang merupakan kelipatan dan muncul pertama sebagiaan basis yang bilangan yang lain yang menjadi kelipatannya.Berdassarkan berbagai pernyataan tersebut,bilangan prima dapat didefinisikanberikut.

“Bilangan bulat p>1 disebut bilangan prima bilamana tidak ada bilangan pembagi d terhadap p yang memenuhi syarat 1<d<p.Dengan perkataan lain,bilangan prima adalah bilangan asli yang lebih besar dari satu dan bilangan itu sendiri.Sebuah bilangan bulat p>1 yang bukan bilangan prima disebut bilangan komposit(tersusun)”.

Sebagian contoh,2, 3, 5dan 7 adalah bilangan prima, sedangkan 4, 6, 8 dan 9 adalah bilangan komposit. Perlu diperhatikan bahwa 1 bukan bilangan primaa dan bukan pula bilangan composit, sehingga 1 disebut satuan. Jadi, himpunan semua bilangan bulat positif (bilangan asli) terbagi dalam 3 himpunan bagian yang saling lepas, yaitu:

1)   Himpunan bilangan prima

2)   Himpunan bilangan komposit

3)   Himpunan bilangan satuan.

B.     Rumus Bilangan Prima

Selama berabad-abad, banyak matematikawan telah mencoba untuk mencari rumusan yang dapat digunakan dalam menentukan bilangan prima. Semua bilangan prima yang lebih besar dari 2 jelas merupakan bilangan gasal (ganjil) sehingga orang percaya bahwa untuk suatu bilangan prima p, -1 juga merupakan bilangan prima. Persamaan ini sama halnya dengan persamaan yang diungkapkan oleh Mersenne, yakni rumus: = -1, n>1. Namun, hal tersebut kemudian terbukti tidak benar. Pada tahun 1536, Regius membuktikan bahwa bilangan -1=2047=23 89, bukan bilangan prima.

Cara yang paling sederhana untuk mencari bilangan prima adalah dengan menggunakan metode saringan Eratosthenes (Sieve of Eratosthenes), sebuah karya dari Eratosthenes (240 SM), seorang ilmuwan Yunani Kuno. Cara ini yang paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum saringan Atkin ditemukan pada tahun 2004. Saringan Atkin merupakan cara yang lebih cepat namun lebih rumit dibandingkan dengan saringan Eratosthenes.

Misalkan, kita hendak menemukan semua bilangan prima di antara 1 sampai bilangan bulat 50. Peragaaun saringan Eratosthenes untuk membuat daftar bilangan kurang dari atau sama dengan 50 dilakukan sebagai berikut:

1.    Membuat daftar bilangan mulai dari 1 sampai dengan 50,

2.    Mencoret bilangan 1 dari daftar bilangan tersebut,

3.    Membiarkan bilangan 2 dan mencoret semua bilangan kelipatan 2,

4.    Membiarkan bilangan 3 dan mencoret semua bilangan kelipatan 3,

5.    Membiarkan bilangan 5 dan mencoret semua bilangan kelipatan 5,

6.    Membiarkan bilangan 7 dan mencoret semua bilangan kelipatan 7,

7.    Membiarkan semua bilangan yang belum dicoret,

8.    Melihat hasil bilangan yang dibiarkan dan tidak dicoret.

9.    Mendaftar semua bilangan prima yang kurang dari 50, yaitu 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 dan 47.

(catatan: beberapa bilangan mendapat pencoretan lebih dari sekali)

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

Penggunaan saringan Eratosthenes tidak dapat secara memuaskan untuk menguji langsung suatu bilangan adalah bilangan prima atau bukan bilangan prima, sehingga banyak “formula” lain yang dibuat untuk menghasilkan bilangan prima. Rumus atau formula itu antara lain:

1)   f(n)= -n+41, untuk n N

Untuk n=1 sampai dengan n=40, diperoleh daftar angka yang merupakan bilangan prima. Tetapi, untuk n=41 maka f(41)=  bukan bilangan prima karena 1681 habis dibagi 1, 41 dan 1681. Dengan demikian, f(n)= -n+41 gagal menjadi rumus bilangan prima.

2)   f(n)= -79n+1601

Formula ini gagal menjadi rumus bilangan prima sebab f(81)= -79(81)+1601=1763, di mana faktor dari 1763 adalaah 1, 41,43 dan 1763, sehingga 1763 bukan bilangan prima.

3)   f(n)= +1

Rumus ini dibuat oleh Fermat. Jika secara berturut-turut n diganti dengan 1, 2, 3 dan 4 maka diperoleh semuanya adalah bilangan prima. Tetapi, jika n diganti dengan 5 maka f(5)= +1=4.294.967.297. Hasil ini bukan bilangan prima karena habis dibagi oleh 641. Jadi, rumus Fermat gagal menghasilkan bilangan prima untuk n=5.

4)   Bilangan prima Sophie Germain. Sebuah bilangan prima p disebut bilangan prima Sophie Germain bila 2p+1 juga bilangan prima. Misalnya, 23 adalah bilangan prima Sophie Germain karena 2 23+1=47 juga bilangan prima. Bilangan ini diberi nama sesuai nama matematikawan Perancis Marie Sophie Germain.

5)    Bilangan prima dengan rumus 3+4k, untuk k>0. Tentu, rumus ini gagal menghasilkan bilangan prima untuk k=3, karena 3+4(3)=15 bukan bilangan prima.

6)   Teorema kecil Fermat menyatakan jika p adalah bilangan prima, maka untuk semua bilangan bulat a, =a(mod p). Ini berarti, jika kita mengambil sembarang bilangan a, kemudian mengalikan dengan dirinya sendiri sebanyak p kali dan mengurangi a, hasilnya akanhabis dibagi dengan p.

Secara khusus, jika a bukan faktor p, maka (mod p) 1. Teorema ini memberikan uji yang baik untuk ketidakmiripan. Dengan bilangan bulat n>1, pilihlah a>1 dan hitung (mod n). jika hasilnya 1, maka n bukan bilangan prima. Sebaliknya, jika hasilnya=1, maka n mungkin bilangan prima sehingga n mungkin disebut  bilangan prima semu basis a (prima semu, bilangan yang “mendekati” bilangan prima).

Sebagai contoh, untuk a=2 dan n=341, maka (mod 341)= (mod 341)= = mod 341=1. Tetapi, 341 bukan bilangan prima karena 341= , sehingga 341 adalah bilangan prima semu basis 2. (umumnya digunakan oleh praktisi kriptografi, kriptografi adalah teknik untuk menyamarkan suatu pesan dengan kata lain “sandi”).

Meski bilangan prima Mersenne terbukti tidak secara pasti benar bahwa rumus tersebut adalah rumus untuk bilangan prima, namun para peneliti tetap menggunakan rumus Mersenne dalam mencari bilangan prima. Bilangan prima terbesar yang diketahui pada September 2006 adalah -1. Bilangan ini mempunyai 9.808.358 digit dan merupakan bilangan prima Mersenne yang ke-44. (demikian notasi penulisan bilangan prima Mersenne ke-44) ditemukan oleh Curtis Cooper dan Steven Boone pada 4 september 2006 yang keduanya adalah profesor university of Sentral Missoouri bekerja sama dengan puluhan ribu anggota lainnya dari proyek Great Internet Mersenne Prime Search (GIMPS).

Di antara semua bilangan prima Mersenne yang sudah ditemukan, sepuluh bilangan terbesarnya ditemukan dengan GIMPS. Bilangan prima Mersenne terbesar saat ini memiliki 9.808.358 digit angka.

C.    Teorema Bilangan Prima

Sebelum membahas teorema tentang bilangan prima, terlebih dahulu dijelaskan istilah saling prima. Dua buah bilangan dikatakan saling prima jika faktor persekutuan terbesar (FPB) dari dua bilangan tersebut adalah 1. Istilah lain dari saling prima adalah komprima atau prima relatif. Jadi defenisi saling prima dapat dituliskan sebagai berikut.

“Dua bilangan bulat a dan b dikatakan prima relatif, jika (a,b)=1”

Apabila ( )=1 maka  juga dikatakan saling prima. Bilangan bulat positif  dikatakan saling prisma dua-dua atau saling prima sepasang, apabila ( )=1, untuk i=1, 2, 3,…., n dan j=1, 2, 3,…., n  dengan i j. contoh (7, 8, 15)=1,sehingga dikatakan bahwa 7, 8 dan 15saling prima dan sekaligus saling prima dua-dua, sebab (7,8)=(7,15)=(8,15)=1. Contoh lain (4, 6, 9, 10) =1 menunjukkan bahwa 4, 6, 9 dan 10 saling prima, tetapi tidak saling prima dua-dua, sebab (4,6)=2, (4,10)=2, (6,9)=3, (6,10)=2 meskipun (4,9)=(9,10)=1.

1)   Teorema 6.1

Jika sisa pembagian b oleh a adalah prima relatif dengan a, maka b juga prima relatif dengan a.

Bukti:

Misalkan a dan b adalah bilangan-bilangan bukat daan a=0, maka menurut algoritma pembagian diperoleh: b=aq+r dengan

Misalnya, (a,r)=1. Apakah (b,a)=1?

Misalkan (b,a)=d, maka dan d|b

Karena b=aq+r dengan d dan d|b maka d|r

Selanjutnya dan d|r, sehingga d merupakan faktor persekutuan dari a dan r.

Tetapi, karena (a,r)=1, maka d 1.

Mengingat (b,a)=d, yaitu d 1, maka d=1.

Maka, (b,a)=1

Contoh:

Misalkan 81 dan 266, dengan 266=(81)(3)+23. Perhatikan bahwa (81,23)=1, maka menurut teorema 1 (266,81)=1. Hal ini dapat dilihat pada Algorotma Euclides.

2)   Teorema 6.2

Setiap bilangan bulat n>1 dapat dibagi oleh suatu bilangan prima. Dengan perkataan lain, jika n  dan n adalah bilangan komposit, maka ada bilangan prima p sehingga.p|n

Bukti:

Cara I

1)      Ambil sembaraang bilangan positif n>1. Jika n bilangan prima maka  berarti teorema terbukti.

2)      Apabila n adalah bilangan komposit, maka n mempunyai faktor selain 1 dan n sendiri. Misalnya , yaitu maka ada  sehingga n=  dengan 1< <n.

3)      Ambil bilangan prima sehingga , dengan demikian teorema terbukti. Tetapi, jika  suatu bilangan komposit, maka  mempunyai faktor selain 1 dan , misalnya , yaitu  | sehingga ada  sehingga , 1< < .

4)      Ambil bilangan prima sehingga . Karena dan  |n maka . Jadi, n terbagi oleh suatu bilangan prima , sehingga teorema terbukti. Tetapi, jika suatu bilangan komposit, maka  mempunyai faktor selain 1 dan  , misalnya , yaitu . Ini berarti ada  sedemikian sehingga =  dengan 1< < .

5)      Ambil bilangan prima  dan  dengan dan yang berimplikasi sehingga teorema terbukti. Tetapi,  jika  suatu bilangan komposit, proses seperti di atas dapat dilanjutkan sedemikian sehingga didapatkan suatu barisan n, , ,….,dengan n> > >……>1.

Penguraian atas faktor-faktor komposit tersebut tentu berakhir pada suatu faktor prima, karena faktor-faktor tersebut selalu kurang dari bilangan yang diuraikan dan selalu lebih dari 1. Misalkan penguraian berakhir pada faktor prima , maka  dan karena , ,…..,  sehingga .

Cara II

Misalkan tidak ada bilangan prima p yang memenuhi  dan S adalah himpunan semua bilangan komposit yang tidak mempunyai faktor prima dengan S= .

Karena S  dan S N maka menurut prinsip terurut rapi , S mempunyai unsur terkecil m.

Misalkan m S maka m= . dengan 1< <m dan 1< <m, S, sebab m adalah unsur terkecil S, berarti  adalh bilangan prima atau bilangan yang mempunyai faktor prima.

Ternyata tterjadi kontradiksi karena m S mempunyai faktor prima. Jadi, S , yaitu ada bilangan prima p yang memenuhi .

Contoh:

a.       Misalkan n=17 dan n {bilangan prima}, menurut teorema 2, terdapat bilangan prima p sehingga . Pilih bilangan prima p=17, sehingga .

b.      Misal n=357, dengan n {bilangan komposit}. Menurut teorema 2, n memiliki faktor selain 1 dan 357 sendirii. Misalkan faktor lain adalah =3 yaitu , maka ada  sedemikian sehingga 357=3  dengan =119 dan 1<199< 357. Karena 119 merupakan bilangan komposit  , maka  mempunyai faktor  selain 1dan 119 sendiri. Misalkan faktor lain tersebut adalah =7 yaitu , maka ada  sedemikian sehingga 119=7  dengan =17 dan 1<17<119. Karena =17 merupakan bilangan prima, menurut teorema 2, ada bilangan prima p sedemikian sehingga . Pilih bilangan prima p=17 maka .

3)   Teorema 6.3

Setiap bilangan bulat n>1 dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.

Bukti:

Cara I

1)      Ambil sebarang bilangan bulat positif n>1. Menurut teorema 2, ada suatu bilangan prima  sedemikian sehingga . Karena itu, ada bilangan bulat positif sehingga n=  dengan 1< .

2)      =1 n= n {bilangan prima}. Tetapi, jika >1, menurut teorema 2, ada bilangan , sedemikian sehingga . Karena itu, ada  sedemikian sehingga  dengan 1< < .

3)      =1 = n= . Hal ini berarti n dapat dinyatakan sebagai perkalian bilangan-bilangan prima (teorema terbukti). Tetapi, jika >1, maka menurut teorema 2,  p {bilangan prima} . Karena itu =  dengan 1 < .

4)      =1 = n= . Hal ini berarti n dapat dinyatakan sebagai perkalian bilangan –bilangan prima (teorema terbukti). Tetapi, jika , maka proses dapat dilanjutkan sehingga pada akhirnya diperoleh .

Penguraian atas faktor-faktor prima tersebut pasti berakhir karena  dan setiap . Misalnya untuk k,  maka diperoleh n=  yaitu n dapat dinyatakan sebagai perkalian bilangan-bilangan prima.

Cara II

Bilangan bulat n>1 memiliki kemungkinan n bilangan prima atau komposit. Jika n bilangan prima maka n adalah faktor primanya sendiri. jika n bilangan komposit, maka n dapat difaktorkan katakanlah n=  dengan  dan .

Jika  bilangan prima maka ia adalah faktor prima n. jika  bukan bilangan prima, maka  dengan  dan

Dengan cara yang sama dapat pula berlaku untuk , yaitu mungkin prima atau komposit. Penguraian faktor komposit pasti berakhir karena faktor-faktornya harus lebih kecil dari yang diuraikan yaitu bilangan komposit itu sendiri, tetapi harus lebih besar dari 1. Jadi, kita dapat menyatakan n sebagai hasil kali bilangan-bilangan prima.

Suatu bilangan positif yang lebih besar dari 1 dapat dinyatakan sebagai perkalian bilangan-bilangan prima. Jika diantara faktor-faktor prima tersebut ada yang sama, maka faktor-faktor yang sama dapat ditulis dalam bentuk  dengan  adalah faktor-faktor prima dan  merupakan pangkat-pangkat positif.

Selanjutnya  disebut representasi n sebagai perkalian bilangan-bilangan prima atau sering pula disebut bentuk kanonik dari n. teorema 3 sangat membantu untuk menentukan FPB dan KPK dari 2 bilangan atau lebih dengan menyatakan bilangan-bilangan tersebut dalam bentuk kanoniknya.

Misalkan 2 bilangan a dan b, masing-masing dinyatakan dengan   dan  dimana dan , (i=1, 2, 3,…..,r). Dengan demikian FBP dari a dan badalah dan KPK a dan b adalah[a,b]

Contoh :

Ambil nilai a=112 dan b=212.

Penguraiannya menjadi faktor-faktor prima:

a=112=( )(7)= )( )( )

b=212= )(53)= )( )( )

Dengan demikian FBP dan KPK diberikan oleh:

(a,b)= = =4

[a,b]= = =

Karena a dan b keduanya positif, sifat [a,b](a,b)=ab dapat digunakan.

Bukti, [112,212](112,212)=112 212=23744=5936 . Cara ini berlaku hanya pada dua bilangan bulat positif.

4)   Teorema 6.4

Jika n suatu bilangan komposit, maka n memiliki faktor k dengan 1<k .

Bukti:

Karena n suatu bilangan komposit, ada bilangan-bilangan bulat positif k dan m sedemikian sehingga km=n dengan 1<k<n dan 1<m<n.

Apabila k dan m kedua-duanya lebih besar dari , yaitu k>  dan m> , maka n=km> =n(n>n).

Hal ini tidak mungkin sehingga salah satu dari k atau m harus lebih kecil atau sama dengan , misalnya k, yaitu 1<k . Jadi, n memiliki faktor k dengan 1<k .

Kontraposisi teorema 4.

Apabila bilangan bulat positif n tidak mempunyai faktor k dengan 1<k , maka n adalah suatu bilangan prima.

Contoh:

Apakah 1003 merupakan bilangan prima atau bukan?

Penyelesaian:

Bilangan 1003 diperiksa keterbagiannya oleh bilangan-bilangan prima yang kurang dari  yaitu 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 dan 31. Karena terdapat bilangan yang dapat membagi habis 1003 yaitu 17 maka 1003 adalaah bilangan komposit.

5)   Teorema 6.5

Jika n N (bilangan asli), maka n mempunyai faktor prima terbesar p sehingga p .

Bukti:

Misalkan tidak benar bahwa n mempunyai faktor prima terbesar p , berarti n paling sedikit mempunyai dua faktor p  dan q> . Dengan demikian, n=pq>  atau n=pq>n. Hal ini menunjukkan suatu kontradiksi (n>n) yang berarti n mempunyai faktor prima terbesar p .

Contoh:

Contoh ini merupakan prinsip kerja dari saringan Eratosthenes. Jika n=300 maka pencoretan dihentikan pada bilangan prima terbesar p  yaitu p=17. Proses yang dilakukan  adalah:

a)      Mencari bilangan prima terbesar kurang dari atau sama dengan

b)      Mencoret semua bilangan kelipatan bilangan prima yang kurang dari atau sama dengan  (kecuali bilangan-bilangan prima itu sendiri)

c)      Semua bilangan yang tersisa adalah bilangan prima.

D.    Faktorisasi Tunggal

Telah diketahui bahwa setiap bilangan bulat positif yang lebih besar dari 1 dapat dinyatakan sebagai perkalian dari bilangan-bilangan prima tertentu. Dapat dikatakan bahwa setiap bilangan bulat positif yang lebih dari 1 dapat dinyatakan sebagai hasil kali faktor-faktor prima (mungkin hanya satu faktor). Pada bagian ini dipelajari bahwa hasil kali dari faktor-faktor bilangan prima itu adalah tunggal, kecuali hanya berbeda menurut urutan dari faktor-faktor prima tersebut. Pemfaktoran suatu bilangan bulat atas faktor-faktor prima yang tunggal itu terkenal dengan namaTeorema Dasar Aritmetika (Fundamental Theorem of Arethmetic) dan disebut Faktorisasi Tunggal. Nama teorema dasar aritmetika digunakan karena memberikan dasar dalam mengembangkan teorema lain dalam aritmetika. Sebelum membicarakan faktorisasi tunggal, teorema berikut dikemukakan sebagai persiapan untuk membuktikan faktorisasi tunggal.

1)   Teorema 6.6

Jika p suatu bilangan prima dan , a, b Z, maka  atau .

Bukti:

Cara I

Karena  p suatu bilangan prima , maka p hanya mempunyai faktor 1 dan p, sehingga (a,p)=1 atau (a,p)=p untuk bilangan bulat a sembarang.

Jika p+a maka (a,p)=1. Jika dan (a,p)=1, maka . hal ini sesuai dengan teorema “jika a, b, c Z, dan (a,b)=1 maka ”

Karena p+b maka dengan cara yang sama dapat dibuktikan bahwa .

Cara II

Jika (a,p)=1 maka pada x, y c Z sehingga ax+py=1

(ax+py)b=1.b (sifat perkalian pada kesamaan)

 (sifat distributif perkaliaan)

 (sifatasosiatif perkalian)

Karena  dan  maka  dan

Karena  dan  maka

Karena  dan abx+pby=b maka

Dengan jalan yang sama, jika dianggap p+b, maka dapat dibuktikan bahwa

Teorema ini dpat diperluas untuk bilangan .

2)   Teorema 6.7

Jika p suatu bilangan prima dan maka , untuk 1 .

Bukti:

Induksi matematika diterapkan pada n, yaitu banyaknya faktor. Ambil bilangan prima p.

1)      Untuk n=1 berarti , jelas benar

2)      Untuk n=2 berarti , karena p bilangan prima maka  atau  (teorema 1)

3)      Andaikan teorema benar untuk n>2, maka diambil sebagai hipotesis induksi

4)      Apabila p pembagi perkalian sejumlah kurang dari n faktor, maka p pembagi paling kurang salah satu dari faktor-faktor itu  atau ditulis bahwa 2<t<n, yaitu p prima dan  maka  untuk suatu s dengan 2<s<t.

Pandang atau . Menurut teorema 2 atau . Jika  benar, teorema terbukti. Jika  atau keadaan lain , menurut teorema 2 lagi diperoleh bahwa  atau .

Jika  maka teorema terbukti.

Jika , maka proses seperti di atas dapat diteruskan. Berdasarkan hipotesis yang diambil, proses tersebut akan berakhir. Dengan demikian, bilangan prima p membagi salah satu dari .

Andaikan teorema 2 diterapkan untuk kasus bahwa  semuanya bilangan prima dan , maka menurut teorema 2  untuk semua k dengan 1 . Karena p dan adalah bilangan-bilangan prima dan  maka p= .

3)   Teorema 6.8

Jika  semua bilangan prima dan , maka p= untuk suatu k dengan 1 .

Bukti:

Jika  adalah bilangan prima yang memenuhi sifat , menurut teorema 2 , , ,…, dan . karena  adalah bilangan prima, maka jika , haruslah p= begitu pun  memberikan p= dan seterusnya sampai  memberikan p= . Dengan demikian diperoleh p= , p= , p= ,…, p=  atau dapat dituliskan p=  untuk k=1, 2, 3,…,n atau 1 . jadi, terbukti bahwa p=  untuk .

Selanjutnya kita akan membuktikan ketunggalan dari pemfaktoran dari suatu bilangan bulat positif  atas faktor-faktor prima. Teorema ini menyatakan bahwa jika x adalah sebarang bilangan bulat positif lebih dari 1, maka x dapatditulis sebagai x= , di mana , . masing-masing bilangan prima. Lebih dari itu, jika x=  dan x= , di mana bilangan ,  adalah bilangan prima, maka  adalah bilangan prima yang sama dengan  dalam urutan sembarang.

4)   Teorema 6.9

Pemfaktoran suatu bilangan bulat positif yang lebih besar dari satu atas faktor-faktor prima adalah tunggal, kecuali urutan dari faktor-faktornya mungkin tidak tunggal.

Bukti:

Kita menyelesaikan bukti teorema ini menjadi dua bagian. Bagian pertama menunjukkan bahwa setiap bilangan bulat positif yang lebih besar dari 1 dapat difaktorkan menjadi bilangan prima. Bagian kedua menjelaskan bahwa faktorisasi itu tunggal.

1)      Pandang bilangan bulat m sebarang yang lebih besar dari 1. Akan ditunjukkan bahwa m dapat dituliskan sebagai perkalian faktor-faktor bilangan prima. Karena m adalah bilangan yang lebih besar dari 1, maka m mungkin prima atau komposit. Andaikan m bilangan prima maka m adalah faktor primanya sendiri.

Andaikan m bilangan komposit, menurut teorema 6.3 (Setiap bilangan bulat n>1 dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.) m memiliki faktor prima , sehingga m=  dengan .

Jika bilangan prima maka pembuktian selesai. Jika komposit maka  sehingga dengan .

Jika prima maka pembuktian selesai. Tapi jikia komposit, maka  seingga  dengan  dan seterusnya.

Proses ini akan berakhir pada yang prima, misalnya , maka m= , artinya m adalah hasil kali faktor-faktor bilangan prima.

2)      Akan ditunjukkan bahwa faktorisasi itu tunggal. Andaikan bahwa pemfaktoran m atas faktor-faktor prima tidak tunggal yaitu ada m=  dan m=  dengan r s,  semuanya bilangan prima untuk i=1, 2, 3, …,r dan j=1, 2, 3,…,s serta . karena  maka  berdasarkan teorema 3 (Jika  semua bilangan prima dan , maka p= untuk suatu k dengan 1 .) untuk  bilangan prima dan  maka  untuk semua k, 1 . karena  maka .

Selanjutnya, jika dipandang yaitu . menurutteorema 3,  untuk suatu t dengan . karena  maka . Karena  dan  maka haruslah . Akibatnya ….. .

Jika proses di atas diulang maka diperoleh:

dan ….. .

dan ….. .

Jika proses ini diteruskan dan r=s maka akan berakhir pada  dan teorema terbukti. Jika r<s maka akan diperoleh 1= . Hal ini mustahil karena  itu masing-masing lebih besar dari 1, sehingga haruslah r = s dan , , … . Ini berarti bahwa m hanya dapat dinyatakan sebagai salah satu hasil kali faktor-faktor  prima saja.

Pada pemfaktoran suatu bilangan bulat positif atas faktor-faktor prima mungkin saja suatu bilangan prima akan muncul berulang-ulang, seperti 360=2.2.2.3.3.5. Faktor-faktor yang sama dapat dinyatakan sebagai bilangan berpangkat, sehingga pemfaktoran suatu bilangan bulat positif atas faktor-faktor prima dapat dinyatakan dalam bentuk kanonik. Karena itu, teorema faktorisasi tunggal tersebut dapat dinyatakan sebagai berikut:

            Setiap bilangan bulat m>1 dapat dinyatakan secara tunggal dalam bentuk kanonik  dengan  bilangan prima dan pangkat  i=1, 2, 3,…r serta .

Pembuktian teorema faktorisasi tunggal ini dapat pula diselesaikan dengan menggunakan induksi matematika.

Contoh:

Tunjukkan pemfaktoran prima dari 84!

Penyelesaian:

            Cara pemfaktoran prima dari suatu bilangan adalah menyatakan bilangan itu sebagai perkalian dua bilangan, sehingga diperoleh dua faktor. Selanjutnya, faktor-faktor yang belum meruopakan bilangan prima difaktorkan lagi. Demikian seterusnya sampai diperoleh semua faktornya adalah bilangan prima. Karena kemungkinan ada banyak cara dalam setiap langkah memfaktorkan, kemungkinan juga terdapat banyak cara dalam pelaksanaan pemfaktoran prima. Misalnya pemfaktoran prima dari 84 dilakukan dengan cara atau skema  diagram pohon. Pemfaktoran prima adalah sama yaitu:

a.       84=(2)(2)(3)(7)= (3)(7)

b.      84=(3)(2)(2)(7)= (7)

c.       84=(3)(7)(2)(2)=(3)(7)(

Jadi, jelas bahwa pemfaktoran prima dari 84 adalah tunggal, kecuali urutan faktornya bisa berbeda.

Pada pembahasan terdahulu mengenai bilangan bulat, telah dijelaskan bahwa bilangan bulat tidak terhingga banyaknya dan setiap bilangan bulat dapat difaktorkan atas faktor-faktor prima. Pertanyaan sekarang adalah :apakah banyaknya bilangan prima juga tidak terhingga?

Pada sekitar tahun 300 SM, Euclides membuktikan bahwa banyaknya bilangan prima adalah tidak terhingga. Teorema Euclides tersebut dapat dinyatakan sebagai berikut: “jika diberikan sebarang daftar bilangan prima, adalah selalu mungkin membentuk bilangan prima yang baru yang tidak terdapat dalam daftar”, jadi banyaknya bilangan prima adalah tak terhingga.

5)   Teorema 6.10

Banyaknya bilangan prima adalah tidak terhingga

Bukti :

Misalkan bahwa banyaknya bilangan prima adalah tidak terhingga yaitu  ,  … ,  dimana  2 (bilangan prima terkecil ) dan  adalah bilangan prima terbesar. Dari semua bilangan prima itu, dari p₁ hingga p_n, dapat dibentuk suatu bilangan bulat positif R dengan jalan mengalikan bersama-sama bilangan prima tersebut lalu ditambah dengan 1 yaitu ( ,  … , ) + 1. Karena R , terdapat dua kemungkinan nilai R, yaitu R mungkin merupakan bilangan komposit atau prima.

1)      Bila R bilangan prima, yaitu R = P_i (1 ) maka R | R, yaitu P_i |(P₁P₂P₃…P_n) + 1. Karena P_i | (P₁.P₂.P₃…P_i…P_n)(berdasarkan teorema “jika a, b  Z, a | b maka a|bc  C ”)

Kemudian, P_i |(P₁P₂P₃…P_n) + 1 dan P_i | (P₁.P₂.P₃…P_i…P_n), maka P_i|1 (berdasarkan teorema “jika a, b, c , a|b dan a|b + c maka a|c”). terjadi kontradiksi karena tidak ada bilangan prima yang membagi habis 1.

2)      Bila R bilangan komposit, maka ada bilangan prima P_j (1 ) sehingga P_j| R (sesuai dengan teorema “jika n  dan n adalah komposit, maka ada bilangan prima sehingga P | n”). Karena P_j|R, P_j | (P₁.P₂.P₃…P_j…P_n) + 1. Demikian pula, karena P_j|P_j maka P_j | (P₁.P₂.P₃…P_j…P_n) (berdasarkan teorema “jika a, b ).

Selanjutnya, karena P_j | (P₁.P₂.P₃…P_j…P_n) + 1 dan P_j | (P₁.P₂.P₃…P_j…P_n) maka P_j|1. Terjadi kontradiksi karena tidak ada bilangan komposit yang membagi habis 1. Jadi dapat disimpulkan bahwa banyaknya bilangan prima adalah tidak terhingga.

Pada pembuktian teorema euclides, terdapat pembentukan bilangan bulat positif R sebagai hasil kali semua bilangan prima ditambah 1. Apakah R tersebut suatu bilangan prima ? bila kita memulai untuk bilangan prima pertama yaitu 2, kita memperoleh R₁ = 2 + 1 + 3. Selanjutnya, R₂ = 2 (3) + 1 = 7, R₃ = 2(3)(5) + 1 = 31, R₄ = 2(3)(5)(7) + 1 = 211, R₅ = 2(3)(5)(7)(11) + 1 = 2311.

Ternyata bahwa R₁, R₂, R₃, R₄, dan R₅ tersebut masing-masing adalah bilangan prima. Selanjutnya: Bagaimana dengan R_6, R₇, dan R₈ ? Apakah hasil dari R_6, R₇, dan R₈ juga merupakan bilangan prima?.

R₆ = 2(3)(5)(7)(11)(13)+1 = 30031 = (59)(509)

R₇ = 2(3)(5)(7)(11)(13)(17)+ 1 = 510511 = (19)(97)(277)

R₈ = 2(3)(5)(7)(11)(13)(17)(19)+ 1 = 9699691 = (347)(27953)

Jadi, R_6, R₇, dan R₈ bukan bilangan prima.

Apakah ada tidak terhingga k sedemikian sehingga R_k suatu bilangan prima ? Demikian pula: Apakah ada tidak terhingga bilangan komposit R_k ? Perhatikan barisan bilangan prima 2, 3, 5, 7, …,P_n, dimana P_n adalah bilangan prima ke-n. Sekarang kita ingin menentukan suatu batas atas dari barisan P_n tersebut. Pada pembuktian teorema euclides dapat diambil kesimpulan bahwa P_{n + 1} P₂...P_n+1  + 1.

Sebagai contoh, jika n=2, maka ketidaksamaan tersebut menjadi P₃ +1  + 1 atau 5 (2)(3)+1=7 9+1=10. Ketidaksamaan ini menunjukkan bahwa bilangan prima ke-3 kurang dari 10. Pendekatan ini terlihat masih sangat kasar. Pendekatan yang lebih halus untuk menentukan suatu batas atas dari barisan P_n dinyatakan dalam teorema berikut ini.

6)   Teorema 6.11

Jika dalam barisan bilangan prima, p_n menyatakan bilangan prima ke-n, maka p_n

Bukti:

Pembuktian menggunakan induksi matematika untuk n, dengan dua langkah, yaitu:

1)      Untuk n=1 diperoleh p₁  =  = 2. Hal ini memang benar, karena bilangan prima pertama adalah 2.

2)      Diasumsikan bahwa p_n  benar untuk n = k, yaitu p_k . Selanjutnya harus dibuktikan bahwa p_n  benar untuk n = k + 1, yaitu p_{k + 1}  atau p_{k + 1}

Perhatikan bahwa:

p_{k + 1}  (p₁ p₂ p₃…p_k) + 1

p_{k + 1}  [2(2²)( )( )…( )] + 1

p_{k + 1}

Barisan pangkat yaitu: 1 + 2 + 2²  + 2³ +…+2^{k – 1} ternyata merupakan suatu deret geometri dengan rasio 2. Barisan itu dapat ditulis 2^k – 1, sebagai deret geometri.

Jadi, p_{k + 1}  + 1. Karena  1 untuk setiap bilangan asli k, ketidaksamaan tersebut menjadi p_{k + 1}  +  =  +  = 2².

3)      Karena teorema diasumsikan benar untuk n = 1 dan benar untuk n = k dan telah ditunjukkan benar juga untuk n = k + 1, maka teorema benar untuk setiap bilangan asli n. Jadi p_n  benar untuk setiap bilangan asli n.

7)   Teorema 6.12

Untuk n  1 ada paling sedikit n + 1 buah bilangan prima yang lebih kecil dari

Bukti:

Misalkan p_i (i = 1, 2, 3,…,n) bilangan prima, maka diperoleh p₁ p₂ p₃ … p_n P_{n + 1}

E.     Fungsi Tau ( ) dan Sigma( )

Berdasarkan sifat yang dimiliki oleh bilangan bulat dapat didefinisikan fungsi-fungsi khusus yang mempunyai peranan tertentu dalam teori bilangan. Fungsi-fungsi khusus tersebut sering disebut fungsi aritmetik (fungsi teori bilangan). Pada umumnya, fungsi aritmetik didefinisikan memounyai daerah asal pada himpunan semua bilangan positif. Apabila  suatu fungsi aritmetik, maka  : B⁺  B dengan B adalah himpunan semua bilangan bulat positif. Fungsi-fungsi khusus yang akan dikemukakan adalah fungsi tau ( ) dan fungsi sigma ).

1.    Fungsi Tau ( )

Pembahasan fungsi tau dimulai dengan sebuah definisi berikut.

Definisi 6.3

Fungsi tau  (n) menyatakan banyaknya pembagi bulat positif dari n, untuk n suatu bilangan bulat positif.

Contoh 6.7

Tentukanlah pembagi bulat positif mulai dari bilangan 1 hingga bilangan 15!

Penyelesaian:

a)         Pembagi bulat positif dari 1 adalah 1 sendiri sehingga          (1) = 1

b)        Pembagi bulat positif dari 2 adalah  1 dan 2, sehingga          (2) = 2

c)         Pembagi bulat positif dari 3 adalah 1 dan 3, sehingga  (3) = 2

d)        Pembagi bulat positif dari 4 adalah 1, 2 dan 4, sehingga  (4) = 3

e)         Pembagi bulat positif dari 5 adalah 1 dan 5, sehingga  (5) = 2

f)         Pembagi bulat positif dari 6 adalah 1, 2, 3, dan 6, sehingga  (6) = 4

Dengan cara yang sama, dapat diketahui bahwa  (7) = 2, (8) = 4,  (9) = 3,  (10) = 4,  (11) = 2,  (12) = 6, (13)=2, (14)=4, (15)=4

Berdasarkan contoh 6.7, dapat diketahui bahwa apabila p suatu bilangan prima, maka  (p)=2. Banyaknya pembagi bilangan bulat positif dari n sering dinyatakan dengan rumus yang menggunakan notasi ∑ (baca; sigma). Beberapa contoh penggunaan notasi ∑ diberikan dalam contoh berikut

Contoh 6.8

a.     = a­₁ + a₂ + a₃ + a₄

b.     = 3 + 4 + 5 + 6

c.    = 2 + 2 + 2 + 2 + 2 + 2

d.   = 1 + 2 + 7 + 14 yaitu jumlah semua pembagi bulat positif dari14.

e.     = 1 + 1 + 1 + 1 yaitu banyaknya semua pembafi bulat positif dari 14.

f.      = f(1) + f(2) + f(3) + f(6) + f(9) + f(18).

Berdasarkan beberapa contoh notasi   tersebut,  (n) dapat dirumuskan sebagai berikut:

                     (n) =  untuk n  1

Jadi  (n) merupakan penjumlahan dari 1 sebanyak pembagi bulat positif dari n.

Contoh 6.9

a.    Semua pembagi bulat positif dari 30 adalah 1, 2, 3, 5, 6, 10, 15, 30, sehingga:

= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8

b.    Semua pembagi bilangan bulat positif dari 42 adalah 1, 2, 3, 6, 7, 14, 21 dan 42 sehingga

= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8

c.    Semua pembagi bulat positif dari 48 adalah 1, 2, 3, 4, 6, 8, 12, 16, 24, dan 48 sehingga

d.   = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10

Dengan cara yang sama dapat diketahui bahwa = 1, = 1 + 1 = 2, = 1 + 1  = 2, = 1 + 1 + 1 = 3, = 1 + 1 + 1 +1 = 2,  1 + 1 + 1 + 1 = 4, = 1 + 1 = 2, = 1 + 1 + 1 +1 = 4 dan seterusnya.

Berdasarkan contoh tersebut dapat disimpulkan bahwa jika p suatu bilangan prima, pembagi bulat positifnya hanyalah 1 dan p, sehingga  (p)=2. Karena itu = 1 + 1 = 2 untuk setiap bilangan prima p. Selanjutnya,

1)   Pembagi bulat positif dari p² adalah 1, p dan p² sehingga  (p²) = = 1 + 1 + 1 = 3;

2)   Pembagi bulat positif dari p³ adalah 1, p, p², dan p³ sehingga  (p³) = = 1 + 1 + 1 + 1 = 4;

3)   Pembagi bulat positif dari p⁴ adalah 1, p, p², p³, dan p⁴ sehingga  (p³) = = 1 + 1 + 1 + 1 + 1 = 5;

Berdasarkan uraian di atas dapat disimpulkan bahwa jika k suatu bilangan bulat positif dan p adalah suatu bilangan prima maka  (p^k) = k + 1.

Contoh 6.10

Tentukan  (16),  (32),  (81)!

Penyelesaian:

a)         16 = 2⁴, sehingga  (16) =  (2⁴) = 4 + 1 = 5.

Hal ini dapat diperiksa dengan mencacah semua pembagi bulat positif dari 16 yaitu 1, 2, 4, 8, 16.

b)        32 = 2⁵, sehingga  (32) =  (2⁵) = 5 + 1 = 6

Semua pembagi bulat positif dari 32 adalah 1, 2, 4, 8, 16, 32.

c)         81 = 3⁴, sehingga  (81) =  (3⁴) = 4 + 1 = 5

Semua pembagi bulat positif dari 81 adalah 1, 3, 9, 27, 81.

Apabila p₁ dan p₂ keduanya adalah bilangan prima dan n = p₁p₂, maka pembagi bulat positif dari n adalah 1, p₁, p₂ dan p₁p₂ = n sehingga  (n) = 4. Jika m = p₁²p₂³, maka pembagi bulat positif dari m dapat disusun sebagai berikut:

1	P2	,
P1,	P1P2,	P1 ,,	P1
,	P2,	,	= m

Terlihat    pada daftar ini bahwa   (m) = ( ) = 3  4 = 12.

Contoh 6.11

Tentukan  (648),  (675), dan  (6125)!

Penyelesaian :

a)                            (648) =  (2³ 3⁴) = (3 + 1) (4 + 1) = 20

b)                           (675) =  (3³ 5²) = (3 + 1) (2 + 1) = 12

c)                            (6125) =  (5³ 7²) = (3 + 1)  (2 + 1) = 12

1)      Teorema 6. 13

Apabila n = p^kq^t dengan p dan q bilangan-bilangan prima yang berlainan dan k, t adalah bilangan-bilangan bulat positif, maka  (p^kq^t) = (k + 1) (t + 1).

Bukti:

Semua pembagi bulat positif dari n = p^kq^t dapat di susun daftar sebagai berikut:

                   1,                     p_,                            p²,                    p³,        … p^k

                   q_,                            pq,                         p²q,                        p³q,      … p^kq                                  q²,                    pq²_,                                  p²q²,                 p³q²,     … p^kq²

.                       .                       .                       .           …  .

.                       .                       .                       .           …  .

.                       .                       .                       .           …  .

q^t,                            pq^t,                         p²q^2,                      p³q^t,     … p^kq^t = n

Terlihat pada daftar tersebut bahwa:

              (n) =  (p^kq^t) =(k + 1) (t + 1).

Pada teorema dasar aritmetika, telah dijelaskan bahwa setiap bilangan bulat positif yang lebih besar dari 1 (n ) dapat difaktorkan secara tunggal atas faktor-faktor prima. Selanjutnya, n dapat ditulis dalam bentuk kanonik sebagai n =  …  dengan P_i untuk i = 1, 2,…, k adalah bilangan –bilangan prima yang berlainan dan a_i  1 untuk setiap i = 1, 2, 3,…, k. Bila telah diperoleh bentuk kanonik dari suatu bilangan bulat positif, maka dapat ditentukan banyaknya pembagi bulat positif dari n yaitu  (n) yang dijelaskan dalam teorema berikut.

2)      Teorema 6.14

Apabila bentuk kanonik dari bilangan bulat positif n adalah

 …  maka  (n) = (a₁ + 1)(a₂ + 1)(a₃ + 1)…(a_k + 1).

Bukti:

Apabila d suatu pembagi bulat positif dari n, maka d = P₁ P₂ P₃,…P_k dengan 0 t₁ a_i. Banyaknya pembagi bulat positif dari n merupakan hasil kali banyaknya pilihan, sehingga diperoleh  (n) = (a₁ + 1)(a₂ + 1)(a₃ + 1)…(a_k + 1).

Rumus  (n) tersebut sering dinyatakan dengan notasi  (baca; pil). Contoh pemakaian notasi  diberikan sebagai berikut.

Contoh 6.12

a)                    = P₁  P₂  P₃  P₄  P_5.

b)                 

c)                  

d)                  ^ai = …

e)                  

Contoh 6.13

Tentukan (2205), (9450), dan (25200)!

Penyelesaian:

a)                   2205 = 3²  5  7²

(2205) =  (3²  5  7²) = (2 + 1)(1 + 1)(1 + 1) = 18

b)                  9450 = 2  3³  5²

(9450) =  (2  3³  5² ) = (1 + 1)(3 + 1)(2 + 1) (1 + 1) = 48

c)                   25200 = 2⁴  3²  5²  7

(25200) =  (2⁴  3²  5²  7) = (4 + 1)(2 + 1)(2 + 1) (1 + 1) = 90

Contoh berikut memperlihatkan hasilkali pembagi-pembagi bulat positif dari suatu bilangan bulat positif n.

Contoh 6.14

Tentukan hasil kali semua pembagi bulat positif dari 24 dan 56!

Penyelesaian:

a)                   Pembagi bulat positif dari 24 adalah 1, 2, 3, 4, 6, 8, 12, dan 24, sehingga  (24) = 8

Hasilkali semua pembagi bulat positif dari 24 ditulis dengan notasi K(24) yaitu:

K(24)   = 1

                =  (1 )(2 )(3 )(4 )

                = 24            

                = 24⁴

b)                  Semua pembagi bulat positif dari 56 adalah 1, 2, 4, 7, 8, 14, 28, dan 56, sehingga  (56) = 8

Hasilkali semua pembagi bulat positif dari 56 adalah:

K(56)   = 1

                =  (1 )(2 )(4 )(7 )

                = 56            

                = 56⁴

Kita dapat memriksa bahwa K(2) = 2, K(3) = 3, K(5) = 5, K(7) = 7, dan seterusnya. Jadi jika p suatu bilangan orima, maka K(p) = p, K(p²) = p³, K(p³) = p⁶, K(p⁴) = p¹⁰ dan K(p^t) = p^{1/2t(t + 1)}

3)      Teorema 6.15

Apabila n suatu bilangan bulat positif, hasilkali semua pembagi bulat positif dari n adalah K(n) =  atau dapat ditulis  =

Bukti:

Misalkan d adalah suatu pembagi bulat positif dari n, ada d’ (yaitu pembagi bulat positif dari n pula) sedemikian sehingga dd’ = n. hal ini mungkin saja terjadi bahwa d = d’, yaitu jika n suatu kuadrat sempurna.

Karena banyaknya pembagi bulat positif dari n adalah  (n), dengan mengalikan setiap pembagi dari n (misalnya d) dengan membagi pasangannya (misalnya d’) sedemikian sehingga dd’= n, maka akan diperoleh bahwa hasilkali semua pembagi bulat positif dari n adalah  =

2.    Fungsi Sigma( )

Pada bagaian  sebelumnya telah dibahas  mengenai fungsi tau  yang menyatakan banyaknya pembagi bulat positif dari n,Pada bagian ini dibahas mengenai fungi sigma   yang menyatakan jumlah semua pembagi buat positif dari n.

Defenisi 6.4

Jika n suatu bilangan bulat positif,maka menyatakan jumlah semua pembagi bulat positif darin,yakni

Contoh 6.14

Tentukan ,

Penyelesaian:

a)    Pembagi buat positif dari 30 adalah 1,2,3,5,6,10,15,30,

sehingga

b)   Pembagi bulat positif dari 42 adalah 1,2,3,6,7,14,21, dan 42

sehingga 

c)    Pembagi bulat positif dari 48 adalah  1,2,3,4,6,8,12,16,24 dan 48

sehingga

Contoh 6.15

Tentukan

Penyelesaian:

a.         Pembagi bulat positif dari 2 adalah 1 dan 2 sehingga

b.         Pembagi bulat positif dari 3 adalah 1 dan 3 sehingga

c.         Pembagi bulat positif dari 5 sehingga

d.        Dengancara yang sama ,

Contoh 6.15 menunjukan bahwa jika p suatu bilangan prima, maka )=1+p+p²+p³ dan .

Rumus  dapat di bentuk dngan mengigat rumus jumlah deret geometri .

karena itu, perlu dijelaskan mengenai deret geoetri sebagai berikut.

Diketahui suatu barisan geometri a, ar, ar², ar³,….

Apabila suku-sukunya jumlahkan diperoleh =      untuk  r<1  atau

untuk  r  rumus jumlah deret geometri, diperoleh

 jadi,jika p suatu bilangan prima  dan t suatu bilangan bulat positif, maka

Contoh6.16

Tentukan 

Penyelesaian :

a)      Pembagi bulat positif dari 6 adalah 1,2,3, dan 6 sehingga

b)      Pembagi  bulat  positif dari 64 adalah 1,2,4,,8,16,32, dan64 sehingga  127. Atau =127

c)      Pembagi bulat positif dari 125 adalah 1,5,25, dan 125 sehingga =156

d)     Pembagi bulat positif dari 243 adalah 1,3,9,27,81 dan 243 sehingga

Apabila p dan q adalah dua bilangan prima  yang berbeda dan n =pq, maka semua  pembagi semua positif dari n adalah 1, jika m=  dengan p dan q dua bilangan prima yang berlainan,  maka jumlah semua pembagi bulat positif dari m dapat di susun sebagai berikut ;

+(p+pq+pq²+pq³)+(p²+p²q+p²q²+p²q³)

                   =  (1+p+p²)(1+q+q²+q³)

= 

jika  apabila n=  dengan p dan q keduanya bilangan prima yang berbeda serta k dan t bilangan bulat positif, maka ;

Contoh  6.17

Tentukanlah 

Penyelesaian :

a.        

b.        

c.        

d.        ( ) (31)(57)=1767

e.         )=(8)(133)=1064

Teorema 6.16

Jika bentuk kanonik dari bilangan bulat positif n adalah
maka

Bukti :

Setiap   suku   dari   perkalian   (1+p+ + +….+ ) )   dengan yang lainnya dan masing – masing merupakan pembagiaan darian n,  sehingga 

Berdasarkan rumus jumlah deret geometri , maka

1+

Sehingga

Contoh  6.18

Tentukan

Penyelesaian :

a.          =96

b.        

c.        

                                           =

Pada pembahasan sebelumnya, telah dijelaskan mengenai definisi   di mana d merupakan semua pembagi bulat positif dari n . karena    pembagi bulat positif dari n pula, maka rumus   dapat juga ditulis dalam bentuk :

Rumus   merupakan jumlah kebalikan dari pembagi – pembagi bulat positif       dari n.

Contoh  6.19

Tentukan

Penyelesaian:

a.    Semua pembagi bulat positif dari 12 adalah 1, 2, 3, 4, 6 dan 12 sehingga

Jumlah semua dari kebalikan pembagi dari 12 adalah:

b.    Semua pembagi bulat positif dari 18 adalah 1, 2, 3, 6, 9 dan 18, sehingga

Jumlah semua kebalikan pembagi dari 18 adalah:

c.    Semua pembagi bulat positif dari 5 adalah 1 dan 5 sehingga 

d.   Semua pembagi bulat positif dari 7 adalah 1 dan 7, sehingga

Jumlah semua dari kebalikan pembagi dari 7 adalah:

e.    Semua pembagi bulat positif dari 11 adalah 1 dan 11, sehingga

Jumlah semua kebalikan pembagi dari 1adalah:

BAB III

PENUTUP

A.    Kesimpulan

1.      Rumus Teori Bilangan Prima, Rumus atau formula itu antara lain:

·      f(n)= -n+41, untuk n N

·      f(n)= -79n+1601

·      f(n)= +1

·      Bilangan prima Sophie Germain. Sebuah bilangan prima p disebut bilangan prima Sophie Germain bila 2p+1 juga bilangan prima. Misalnya, 23 adalah bilangan prima Sophie Germain karena 2 23+1=47 juga bilangan prima. Bilangan ini diberi nama sesuai nama matematikawan Perancis Marie Sophie Germain.

·       Bilangan prima dengan rumus 3+4k, untuk k>0. Tentu, rumus ini gagal menghasilkan bilangan prima untuk k=3, karena 3+4(3)=15 bukan bilangan prima.

·      Teorema kecil Fermat menyatakan jika p adalah bilangan prima, maka untuk semua bilangan bulat a, =a(mod p). Ini berarti, jika kita mengambil sembarang bilangan a, kemudian mengalikan dengan dirinya sendiri sebanyak p kali dan mengurangi a, hasilnya akan habis dibagi dengan p.

2.      Teorema bilangan prima

·      Jika sisa pembagian b oleh a adalah prima relatif dengan a, maka b juga prima relatif dengan a.

·      Setiap bilangan bulat n>1 dapat dibagi oleh suatu bilangan prima. Dengan perkataan lain, jika n  dan n adalah bilangan komposit, maka ada bilangan prima p sehingga p|n

·      Setiap bilangan bulat n>1 dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.

·      Jika n suatu bilangan komposit, maka n memiliki faktor k dengan 1<k .

·      Jika n N (bilangan asli), maka n mempunyai faktor prima terbesar p sehingga p .

3.      Faktorisasi prima

·      Jika p suatu bilangan prima dan , a, b Z, maka  atau .

·      Jika p suatu bilangan prima dan maka , untuk 1 .

·      Jika  semua bilangan prima dan , maka p= untuk suatu k dengan 1 .

·      Pemfaktoran suatu bilangan bulat positif yang lebih besar dari satu atas faktor-faktor prima adalah tunggal, kecuali urutan dari faktor-faktornya mungkin tidak tunggal.

·      Banyaknya bilangan prima adalah tidak terhingga

·      Jika dalam barisan bilangan prima, p_n menyatakan bilangan prima ke-n, maka p_n

·      Untuk n  1 ada paling sedikit n + 1 buah bilangan prima yang lebih kecil dari

4.      Fungsi Tau ( ) dan Fungsi Sigma ( )

Fungsi tau  yang menyatakan banyaknya pembagi bulat positif dari n dan fungi sigma   yang menyatakan jumlah semua pembagi buat positif dari n.

B.     Saran

Makalah ini disusun dengan tujuan untuk menambah wawasan dan membantu memudahkan kita dalam mengikuti mata kuliah Teori Bilangan terkhusus pada materi bilangan prima. Kami sebagai penyusun memberi saran dan harapan yang besar kepada pembaca yang budiman untuk mempergunakan makalah ini sebaik mungkin. Selain itu kami juga menyadari bahwa dalam penyusunan makalah ini terdapat banyak kekurangan, maka dari itu kami bersedia menerima tiap kritikan dan saran dari pembaca yang bersifat membangun.

Semoga dengan diterbitkannya makalah ini wawasan kita mengenai mata kuliah Teori Bilangan terkhusus pada materi bilangan prima. Kami mengucapkan terimakasih dan permohonan maaf yang sebesar-besarnya kepada pembaca dan semua pihak yang telah terlibat dalam penyusunan makalah ini.

DAFTAR PUSTAKA

Tiro.MA.dkk.2008:Pengenalan Teori Bilangan(213-254). Makassar:CV. Andira Karya Mandiri.