MAKALAH ALGORITMA DAN TEORI BILANGAN BULAT

KATA PENGANTAR

Puji syukur atas kehadirat Allah SWT, karena berkat rahmat dan karunia-Nya kami dapat menyelesaikan makalah tentang Algoritma dan Teori Bilangan Bulat. Semua ini tidak terlepas dari Rahman dan Rahim serta pertolongan-Nya, sehingga semua hambatan dan kendala dalam penyusunan makalah ini dapat dilalui.

Makalah ini telah kami susun dengan maksimal dan mendapatkan bantuan dari berbagai pihak sehingga dapat memperlancar pembuatan makalah ini. Untuk itu kami menyampaikan banyak terimakasih kepada semua pihak yang telah berkontribusi dalam pembuatan makalah ini.

Terlepas dari semua itu, kami menyadari sepenuhnya bahwa masih ada kekurangan baik dari segi susunan kalimat maupun tata bahasanya. Oleh karena itu dengan tangan terbuka kami menerima segala saran dan kritik dari pembaca agar kami dapat memperbaiki makalah ini.

Akhir kata kami berharap semoga makalah tentang Algoritma dan Teori Bilangan Bulat ini dapat memberikan manfaat maupun inspirasi terhadap pembaca.

Metro, Oktober 2020

Penyusun

DAFTAR ISI

HALAMAN i

KATA PENGANTAR ii

DAFTAR ISI iii

BAB I PENDAHULUAN

Latar Belakang 1

Rumusan Masalah 2

Tujuan 2

BAB II PEMBAHASAN

Algoritma 3

Bilangan Bulat 4

Sifat Pembagian pada Bilangan Bulat 5

Pembagian Bersama Terbesar 6

Algoritma Euclidean 7

Aritmatika Modulo 8

Bilangan Prima 9

BAB III PENUTUP

Kesimpulan 17

Saran 17

DAFTAR PUSTAKA

BAB I

PENDAHULUAN

Latar Belakang

Matematika merupakan induk dari segala ilmu. Perkembangan ilmu pengetahuan dan kebudayaan manusia dalam kehidupan sehari-hari tidak lepas dari unsur matematika. Pembelajaran matematika bertujuan untuk membekali siswa agar dapat mengembangkan kemampuan berfikir logis, analitis, sistematis, kritis, dan kreatif. Kompetensi matematika tersebut diperlukan untuk menghadapi perkembangan ilmu pengetahuan dan teknologi yang berkembang sangat cepat, maka dari itu algoritma dan bilangan bulat sangat diperlukan pada zaman desawa ini.

Algortitma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis. Sedangkan Menurut KBBI, algoritma adalah urutan logis pengambilan keputusan untuk pemecahan masalah. Kata logis merupakan kata kunci dalam sebuah algoritma. Langkah-langkah di dalam algoritma harus logis, ini berarti hasil dari urutan langkah-langkah tersebut harus dapat ditentukan, benar atau salah. Langkah-langkah yang tidak benar dapat memberikan hasil yang salah.

Bilangan bulat merupakan salah satu pokok bahasan di dalam pelajaran Matematik. Bilangan bulat terdiri dari bilangan bulat positif, bilangan nol dan bilangan bulat negatif. Bilangan bulat positif merupakan bilangan asli yang digunakan dalam menghitung anggota sebuah himpunan. Bilangan-bilangan 1, 2, 3, 4, 5, 6, 7, … juga disebut bilangan yang dibilang atau bilangan-bilangan bulat positif. Dengan kata lain, bilangan asli itu bilangan yang dimulai dari bilangan 1, 2, 3 dan seterusnya.

Himpunan bilangan bulat positif, bilangan nol dan bilangan bulat negatif dinamakan himpunan bilangan bulat. Selanjutnya tidak hanya sekedar mengetahui himpunan bilangan bulat saja, tetapi juga dikaitkan dengan operasi hitung pada bilangan bulat.

Karena pentingnya penerapan Algoritma dan Teori bilangan bulat dalam kehidupan sehari-hari, maka dengan ini kami akan membahas makalah tentang “Algoritma dan Teori Bilangan Bulat”. Semoga dapat memberikan sedikit pengalaman bagi yang membaca.

Rumusan Masalah

Berdasarkan latar belakang di atas, maka rumusan masalah dalam makalah ini adalah sebagai berikut.

Apa itu algoritma ?

Apa pengertian bilangan bulat?

Bagimana sifat pembagian pada bilangan bulat?

Apa itu pembagian bersama terbesar?

Apa itu algoritma euclidean?

Apa itu aritmatika modulo?

Apa itu bilangan prima?

Tujuan

Tujuan dari penulisan makalah ini adalah sebagai berikut :

Untuk mengetahui algoritma.

Untuk mengetahui pengertian bilangan bulat

Untuk mengetahui sifat pembagian pada bilangan bulat

Untuk mengetahui pembagian bersama terbesar

Untuk mengetahui algoritma euclidean

Untuk mengetahui aritmatika modulo

Untuk mengetahui bilangan prima

BAB II

PEMBAHASAN

Algoritma

Algoritma adalah urutan langkah-langkah untuk memecahkan suatu masalah.sebenarnya terdapat beberapa definisi lain dari algoritma - tetapi pada prinsipnya adalah sama, dengan definisi yang diungkapkan di atas, antara lain:

Algoritma adalah deretan langkah-langkah komputasi yang mentransformasikan data masukan menjadi keluaran.

Algoritma adalah deretan instruksi yang jelas untuk memecahkan masalah, yaitu memperoleh keluaran yang diinginkan dari suatu masukan dalam jumlah waktu yang terbatas.

Algoritma adalah prosedur komputasi yang terdefinisi dengan baik yang menggunakan beberapa nilai sebagai masukan dan menghasilkan beberapa nilai yang disebut keluaran. Jadi, algoritma adalah deretan langkah komputasi yang mentransformasikan masukan menjadi keluaran.

Algoritma adalah deskripsi dari suatu pola tingkah laku yang dinyatakan secara primitif yaitu aksi-aksi yang didefenisikan sebelumnya dan diberi nama, dan diasumsikan sebelumnya bahwa aksi-aksi tersebut dapat kerjakan sehingga dapat menyebabkan kejadian.

Jadi dapat ditarik kesimpulan bahwa Algoritma merupkan urutan perintah atau langkah-langkah logis penyelesaian masalah yang disusun secara sistematis dan logis.

Sejarah Algoritma

Algoritma berasal dari nama penulis buku, yakni Abu Ja`far Muhammad Ibnu Musa Al-Khwarizmi yang berasal dari Uzbekistan. Orang Barat menyebut Al-Khwarizmi dengan Algorism.

Pada saat itu, Al-Khwarizmi menulis buku dengan judul Al Jabar wal-Muqabala yang artinya `Buku Pemugaran dan Pengurangan` (The book of Restoration and Reduction). Dari judul buku tersebut, kita juga memperoleh kata “aljabar” atau biasa dikenal dengan algebra.

Abu Abdullah Ibnu Musa al-Khawarizmi (770M-840M) lahir di Khawarizm (Kheva), kota yang berada di selatan Sungai Oxus (sekarang disebut Uzbekistan) pada 770 M. Al Khawarizmi merupakan salah satu ilmuan terkenal di zamannya. Ada beberapa cabang ilmu matematika yang berhasil ditemukannya, antara lain yang dikenal sebagai astronom dan geografer.

Awalnya, algoritma merupakan istilah yang merujuk kepada aturan-aturan aritmetis yang berguna untuk menyelesaikan persoalan dengan menggunakan bilangan numeric Arab.

Pada tahun 1950, kata algoritma pertama kali digunakan pada "algoritma Euclidean" (Euclid`s algorithm). Euclid, seorang matematikawan Yunani (lahir pada tahun 350 M), dalam bukunya yang berjudul Element menuliskan langkah-langkah untuk menemukan pembagi bersama terbesar (common greatest divisor atau gcd), dari dua buah bilangan bulat, m dan n [KNU73] (tentu saja Eulid tidak menyebut metodenya itu sebagai algoritma, baru di abad modernlah orang-orang menyebut metodenya itu sebagai "algoritma Euclidean"). Pembagi bersama terbesar dari dua buah bilangan bulat tak negatif adalah bilangan bulat positif terbesar yang habis membagi kedua bilangan tersebut.

Bilangan Bulat

Bilangan bulat adalah bilangan yang tidak memiliki pecahan desimal, misalnya 8, 21, 8765, -34, 0, dan sebagainya. Lawan dari bilangan bulat adalah bilangan riil yang mempunyai titik desimal seperti 8.0, 34.25, 0.02, dan sebagainya.

Di dalam bilangan bulat terdapat bilangan genap dan ganjil :

Bilangan bulat genap { …, -6, -4, -2, 0, 2, 4, 6, … }

Bilangan bulat ganjil { …, -5, -3, -1, 1, 3, 5, … }

Sifat Pembagian pada Bilangan Bulat

Pembahasan bilangan bulat kita mulai dari sifat pembagian (division). Mengapa pembagian? Karena salah satu konsep bilangan bulat yang berguna dalam aritmatika komputer adalah bilangan prima. Bilangan prima adalah bilangan yang hanya habis dibagi oleh 1 dan dirinya sendiri. Bahkan, sembarang bilangan bulat positif dapat dinyatakan sebagai hasil perkalian satu atau lebih bilangan prima.

Definisi 5.2.

Misalkan a dan b adalah dua buah bilangan bulat dengan syarat a≠0. Kita menyatakan bahwa a habis membagi b (a divides b) jika terdapat bilangan bulat c. Sedemikian sehingga b=ac.

Notasi : a|b jika b=ac,c∈Z dan a≠0

(Ingatlah bahwa Z = himpunan bilangan bulat)

Dengan kata lain, jika b dibagi dengan a, maka hasil pembagiannya berupa bilangan bulat. Kadang-kadang pernyataan “a habis membagi b” ditulis juga “b kelipatan a”.

Sebagai contoh:

4|12 karena 12:4=3 (bilangan bulat) atau 12=4×3. Tetapi 4 tidak habis membagi 13 karena 13:4=3.25 (bukan bilangan bulat).

Secara umum, jika hasil pembagian bilangan bulat dinyatakan sebagai bilangan bulat positif, maka selalu terdapat (1) hasil bagi dan (2) sisa pembagian. Misalnya, 13:4 memberikan hasil bagi 3 dan sisa 1. Kasus khusus, jika a habis membagi b, maka sisa pembagian adalah 0, misalnya 12:4 memberikan hasil bagi 3 dan sisa 0. Perhatikan juga bahwa sisa hasil pembagian selalu lebih besar atau sama dengan nol tetapi lebih kecil dari pembagi. Sifat ini kita tuangkan dalam teorema 5.1 berikut.

Teorema 5.1. Misalkan m dan n adalah dua buah bilangan bulat dengan syarat n>0. Jika m dibagi dengan n maka terdapat dua buah bilangan bulat unik q(quotient) dan r(remainder), sedemikian sehingga

m=nq+r dengan 0≤r<n.

Teorema 5.1 sering disebut juga teorema Euclidean (dari nama ilmuwan Yunani yang bernama Euclid, lahir pada tahun 350 sebelum Masehi). Bilangan n disebut pembagi (divisor), m disebut yang dibagi (dividend), q disebut hasil bagi (quotient), dan r disebut sisa (remainder). Notasi yang digunakan untuk mengekspresikan hasil bagi dan sisa adalah dengan menggunakan operator mod dan div seperti berikut:

q=m div n, r=m mod r

Contoh:

1987 jika dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47. Jadi, kita dapat menuliskan bahwa

1987=97.20+47

atau diekspresikan sebagai 1987 div 97 = 20 dan 1987 mod 97 = 47.

Begitu juga, jika -22 dibagi dengan 3 dapat dituliskan sebagai

-22=3(-8)+2

atau diekspresikan sebagai -22 div 3 = -8 dan -22 mod 3 = 2.

Ingatlah bahwa sisa pembagian tidak boleh negatif, jadi kita tidak dapat menuliskan

-22=3(-7)-1

karena r=-1 tidak memenuhi syarat 0≤r<n.

Sebaliknya, jika 24 dibagi dengan 3, maka kita dapat menuliskan

24=3.8+0

Karena r=0 memenuhi syarat 0≤r<n.

Pembagi Bersama Terbesar (PBB) = Faktor Persekutuan Terbesar (FPB)

Pembagi bersama terbesar (PBB) dalam bahasa Inggris dikenal dengan istilah greatest common divisor atau gcd. Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga da dan db. Notasinya: PBB (a,b)=d.

Contoh:

Tentukan PBB (45,36).

Faktor pembagi 45:1,3,5,9,15,45;

Faktor pembagi 36:1,2,3,4,9,12,18,36;

Faktor pembagi bersama dari 45 dan 36 adalah 1,3,9.

PBB (45,36) = 9.

PBB tidak terbatas hanya pada PBB dua buah bilangan bulat tetapi bisa lebih dari dua.

Sifat-Sifat dari PBB

Misalkan a,b,dan c adalah bilangan bulat.

Jika c adalah PBB dari a dan b maka c |(a+b)

Jika c adalah PBB dari a dan b maka c |(a – b)

Jika c adalah PBB dari a dan b maka c |ab.

Contoh:

PBB (64,8) = 8.

8 PBB dari 64 dan 8 maka 8|(64+8) = 8|72

8 PBB dari 64 dan 8 maka 8|(64 – 8)= 8|5

8 | 64 maka 8 | 64.8 = 8|512

Algoritma Euclidean

Algoritma euclidean digunakan untuk mencari PBB dari dua buah bilangan.

Misalkan m dan n adalah bilangan bulat tak negatif dengan m ≥ n. Misalkan r0 = m dan r1=n.

Lakukan secara berturut-turut pembagian untuk memperoleh

r0 = r1q1 + r2 0≤ r2 ≤ r1

r1 = r2q2 + r3 0≤ r3 ≤ r2

rn-2 = rn-1qn-1 + rn 0≤ rn ≤ rn-1

rn-1 = rnqn + 0

Aturan Algoritma Euclidan

Jik n = 0 maka m adalah PBB (m,n), tetapi jika n≠0 lanjutkan langkah ke 2.

Bagilah m dengan n dan misalkan r adalah sisanya.

Gantilah dengan nilai n dan nilai n dengan nilai r, lalu ulang kembali ke langkah 1.

Contoh :

Tentukan PBB dari 53 dan 7 !

Pembahasan :

53 = 7(7) + 4

7 = 1(4) + 3

4 = 1 (3) + 1

3 = 1 (3) + 0 ( karena sisanya sudah 0, maka PBB-nya adalah sisa sebelumnya)

PBB(53,7) = 1

Tentukan PBB dari 80 dan 12 !

Pembahasan :

80 = 6.12 +8

12 = 1.8 + 2

8 = 2.4 +0

Maka PBB (80,12) = 4

Arimatika Modulo

Misalkan a dan m bilangan (m>0). Operasi a modulo m, memberikan sisa jika a dibagi dengan m.

Notasi: a mod m = r sedimikian sehingga

a = mq +r, dengan 0≤ r < m

M disebut modulus atau modulo, dan hasil aritmetika modulo m terletak di dalam himpunan {0,1,2,.....,m-1}.

Contoh ;

Beberapa hasil operasi dengan operator modular :

23 mod 5 = 3 karena (23 = 5.4 + 3)

27 mod 3 = 0 karena (27 = 3.9 +0 )

6 mod 8 = 6 karena (6 = 8.0 +6)

0 mod 12 = 0 karena (0 = 12.0 + 0)

-41 mod 9= 4 karena (-41 = 9.(-5) +4)

Karena a negatif, bagi |a| dengan m mendapatkan sisa r’. Mak a mod m=m-r’ bila r’ <0. Jadi |-41| mod 9=5, sehigga -41 mod 9= 9-5 =4

-39 mod 9= 4 karena ( -39 =13(-3) +0)

Contoh :

33 mod 9 = 15

33-15= mod 9 karena 33-15 = 18 kelipatan dari 9

Bilangan Prima

Jika p adalah suatu bilangan bulat positip lebih dari 1 yang mempunyai pembagi hanya 1 dan p maka p disebut bilangan prima. Bilangan bulat yang lebih dari 1 dan bukan bilangan prima disebut bilangan komposit.

Contoh bilangan prima: 2,3,5,7,11,13,17,19,23,29,31,37,41,47,53,59,61,...

Karena:

2 hanya mempunyai pembagi 1 dan 2

3 hanya mempunyai pembagi 1 dan 3

5 hanya mempunyai pembagi 1 dan 5

Dst

Contoh bilangan komposit: 4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,...

Karena:

Pembagi 4 adalah 1,2, dan 4 (tidak hanya 1 dan 4)

Pembagi 6 juga bukan hanya 1 dan 6

Pembagi 15 juga bukan hanya 1 dan 15.

Dst

Bilangan prima dapat dipandang sebagai bilangan asli lebih dari 1 yang mempunyai tepat dua faktor, yaitu 1 dan dirinya sendiri. Bilangan komposit dapat dipandang sebagai bilangan asli yang mempunyai lebih dari dua faktor. Faktor dari 4 adalah 1,2, dan 4. faktor dari 6 adalah 1, 2, 3, dan 6.

Mencari Bilangan Prima

Para ilmuwan matematika di masa lalu telah melakukan usaha mencari formula untuk menentukan bentuk umum bilangan prima, contohnya:

Erastosthenes, seorang ahli matematika Yunani telah membuat klasifikasi bilangan pada tahun 300 SM yang dikenal dengan istilah saringan Erastosthenes (the sieve Erastosthenes). Adapun proses menentukan bilangan prima <100 adalah sebagai berikut:.

Dicoret angka 1.

Dicoret kelipatan dua kecuali 2.

Dicoret kelipatan tiga kecuali 3.

Dicoret kelipatan lima kecuali 5.

Dicoret kelipatan tujuh kecuali 7.

Maka yang tersisa adalah angka-angka yang menunjukkan bilangan prima <100.

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

51 52 53 54 55 56 57 58 59 60

61 62 63 64 65 66 67 68 69 70

71 72 73 74 75 76 77 78 79 80

81 82 83 84 85 86 87 88 89 90

91 92 93 94 95 96 97 98 99 100

f(n)= n^2 – n+41 pernah muncul sebagai usaha untuk menentukan formula bilangan prima. Ternyata untuk n = 41 diperoleh f(n)= 1681, dan 1681 habis dibagi 1,41, dan 1681. Jadi 1681 bukan bilangan prima, dan rumus tersebut gagal untuk menentukan formula bilangan prima karena tidak berlaku untuk setiap n.

Dengan pengecekan secara tabel diperoleh bilangan prima sebagai berikut:

n f(n) n f(n) n f(n) n f(n)

1 41 11 151 21 461 31 971

2 43 12 173 22 503 32 1033

3 47 13 197 23 547 33 1097

4 53 14 223 24 593 34 1163

5 61 15 252 25 641 35 1231

6 71 16 281 26 691 36 1301

7 83 17 313 27 743 37 1373

8 97 18 347 28 797 38 1447

9 113 19 383 29 853 39 1523

10 131 21 421 30 911 40 1601

Rumus f(n)=n^2 – 79n+1601 pernah muncul sebagai usaha untuk menentukan formula bilangan prima. Ternyata untuk n=81 diperoleh:

f(81)=81^2– 79.81+1601=1763= 41× 43.

Dengan demikian, 1,41,43, dan 1763 merupakan pembagi dari 1763 sehingga 1763 mempunyai lebih dari dua faktor. Jadi 1763 bukan bil prima, dan rumus f(n)=n^2 – 79n+1601 gagal untuk menentukan formula bilangan prima.

Rumus Fermat, yaitu f(n)=2^(2^n )+1. Ternyata untuk n=5 diperoleh:

f(5)=2^(2^5 )+1=2^32+1

=4294967296+1

= 4294967297

=6700417×641 (habis dibagi oleh 641).

Dengan demikian, 1,641, dan 6700417 merupakan pembagi dari 4294967297 atau 2^(2^5 )+1 sehingga rumus tersebut tidak berhasil sebagai formula bil prima untuk n = 5.

Dalil-dalil tentang Bilangan Prima

Dalil 3.1

Jika p adalah bilangan prima dan p│ab, maka p│a atau p│b

Bukti:

Anggaplah p ┼ a, karena p adalah suatu bilangan prima, maka p hanya mempunyai faktor 1 dan p sehingga (a,p)=1

Menurut dalil sebelumnya, jika p│ab dan (a,p)=1 maka p│b. sebaliknya jika dianggap p ┼ b, maka (b,p)=1. Menurut dalil sebelumnya, jika p│ab dan (b,p) = 1 maka p│a. Jadi p adalah bilangan prima dan p│ab, maka p│a atau p│b. (terbukti).

Dalil 3.2

Jika p adalah suatu bilangan prima dan p│a_1 a_2 a_3 … a_n, maka p membagi paling sedikit

satu faktor a_i (1≤ i≤ n ).

Bukti:

Diketahui p│a_1 a_2 a_3 … a_n atau p│a_1 (a_2 a_3 … a_n), maka menurut dalil sebelumnya, p│a_1 atau p │a_2 a_3 … a_n.

Jika p│a_1 maka terbukti p paling sedikit membagi satu faktor a_i. Jika p ┼ a_1, maka menurut dalil sebelumnya, p│a_2 (a_3 a_4 … a_n), yang berakibat p│a_2 atau p│a_3 a_4 … a_n. Demikian seterusnya diperoleh p│a_(n-1) a_n sehingga p membagi paling sedikit satu faktor a_i. (terbukti)

Dalil 3.3 (Teorema Dasar Aritmatika)

Jika n adalah sebarang bilangan bulat positip lebih dari 1, maka n dapat dinyatakan secara tunggal sebagai hasil kali faktor-faktor prima.

Bukti:

Diketahui n∈Z^+ dan n>1, maka n adalah suatu bilangan prima atau n suatu bilangan komposit.

Jika n adalah prima, maka terbukti n mempunyai faktor prima n.

Jika n bilangan komposit, maka terdapat bilangan-bilangan bulat n_1,n_2 dengan (1<n_1,n_2<n) sehingga n=n_1 n_2.

Jika n_1 dan n_2 keduanya bilangan prima maka terbukti n mempunyai faktor prima.

Dalam hal yang lain ada bilangan bulat n_1,n_2, dan n_3 dengan 1<n_1,n_2,〖 n〗_3<n sehingga n=n_1.n_2.n_3. Demikian seterusnya sehingga diperoleh n=n_1.n_2.n_3.… .n_k dengan

1<n_1,〖 n〗_2,n_3,… ,n_k<n dan n_1,〖 n〗_2,n_3,… ,n_k adalah bilangan-bilangan prima.

Untuk menunjukkan ketunggalan pemfaktoran prima, diandaikan pemafktorannya tidak tunggal, yaitu

n = a_1·a_2·a_3·a_4·… ·a_p dan

n = b_1·b_2·b_3·b_4·… ·b_p

dengan a_i dan b_i adalah bilangan prima.

a_1│n berati a_1│b_1·b_2·b_3·b_4·… ·b_p

a_1 adalah bilangan prima, maka menurut dalil sebelumnya a_1│b_i

untuk beberapa i. Di pihak lain, b_i juga suatu bilangan prima (mempunyai faktor 1 dan b_i), maka a_1 =b_i.

n = a_1·a_2·a_3·a_4·… ·a_p dan

n = b_1·b_2·b_3·b_4·… ·b_p

Hal ini berarti n =a_1·a_2·a_3·a_4·… ·a_p = b_1·b_2·b_3·b_4·… ·b_p

seandainya tempat a_i di b_1 maka a_1=b_1 sehingga diperoleh

a_2·a_3·a_4·… ·a_p=b_2·b_3·b_4·… ·b_p.

Jika proses yang sama dilakukan, maka diperoleh

a_2 = b_2,a_3=b_3,a_4=b_4 dan seterusnya.

Jika p<q, diperolah

b_(p+1) b_(p+2) ...b_q = 1.

Hal ini tidak mungkin terjadi, sebab tidak ada bilangan-bilangan prima yang hasil kalinya 1, artinya terjadi kontradiksi.

Jika p>q, diperoleh

a_(p+1) a_(p+2) ...a_q= 1

Hal ini juga tidak mungkin, yang berarti terjadi kontradiksi.

Berdasarkan dua hal tersebut maka yang benar haruslah p=q yaitu pemfaktorannya n adalah tunggal. (terbukti)

Dalil 3.4

Terdapat tak terhingga banyaknya bilangan prima.

Bukti:

Andaikan banyaknya bilangan prima terhingga, yaitu: h_1,h_2,h_3,h_4,… ,h_k.

selanjutnya perhatikan bilangan n=(h_1 h_2 h_3 h_4  … h_k)+1, maka ada dua kemungkinan nilai n, yaitu bilangan komposit atau prima.

Kemungkinan I:

Jika n adalah suatu bilangan komposit, maka menurut dalil sebelumnya, n dapat dinyatakan sebagai hasil kali bilangan-bilangan prima yang terdapat dalam h_1,h_2,h_3,h_4,… ,h_k. Misalkan h_i adalah faktor prima dari n, maka h_i│n atau h_i│(h_1 h_2 h_3 h_4  … h_k)+1, sehingga menurut dalil sebelumnya, h_i│1. Dengan demikian terjadi kontradiksi.

Jadi banyaknya bilangan prima adalah tak hingga.

Kemungkinan II:

Jika n adalah suatu bilangan prima, maka

n =h_j ,(j = 1,2,3,...,k)

h_j│n berarti h_j│(h_1 h_2 h_3 h_4  … h_k) + 1

h_j│ h_1,h_2,h_3,h_4,… ,h_k dan h_j │ (h_1 h_2 h_3 h_4  … h_k) + 1

maka menurut dalil sebelumnya, h_i│1. Dengan demikian terjadi kontradiksi.

Jadi yang benar, banyaknya bilangan prima adalah tak hingga.

Selanjutnya dalil-dalil yang berkaitan dengan keprimaan dapat digunakan untuk menentukan faktor-faktor persekutuan terbesar dan persekutuan terkecil dari dua bilangan dengan lebih sederhana.

Contoh.

Carilah (24,80) dan [24,80]

Jawab

24 =2 (12) = 2(2.6) = 2 (2.2.3)

= 2^3.3

80= 2 (40) = 2 (2.20) = 2 (2.2.10) = 2(2.2.2.5)

= 2^4.5

Karena (24,80) tidak dapat memuat faktor 2 lebih dari 3, maka (24,80) = 2^3= 8

[24,80]=2^4.3.5=16.3.5=80.3=240

BAB III

PENUTUP

Kesimpulan

Di dalam makalah ini terdapat beberapa point point yang dibahas, sehingga terdapat beberapa kesimpulan :

Bilangan bulat adalah bilangan yang tidak memiliki pecahan desimal, dan terbagi menjadi dua yaitu bilangan bulat positif dan bilangan bulat negatif.

Misalkan a dan b adalah dua buah bilangan bulat tidak nol. Pembagi bersama terbesar dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga da dan db. Notasinya: PBB (a,b)=d.

Jika p adalah suatu bilangan bulat positip lebih dari 1 yang mempunyai pembagi hanya 1 dan p maka p disebut bilangan prima.

Beberapa dalil untuk membuktikan bilangan prima :

Jika p adalah bilangan prima dan p│ab, maka p│a atau p│b .

Jika p adalah suatu bilangan prima dan p│a_1 a_2 a_3 … a_n, maka p membagi paling sedikit.

Jika n adalah sebarang bilangan bulat positip lebih dari 1, maka n dapat dinyatakan secara tunggal sebagai hasil kali faktor-faktor prima.

Terdapat tak terhingga banyaknya bilangan prima. Jika n adalah suatu bilangan prima, maka n =h_j ,(j = 1,2,3,...,k)

Saran

Di dalam makalah ini penulis bertujuan agar pembaca dapat memahami dari makalah ini. Penulis sangat berharap kritik dan saran dari pembaca, karena di saat pembuatan makalah ini tentunya masih terdapat beberapa kekurang, sehingga masukan yang membangun akan memotivasi penulis dalam penyusunan makalh ini.

DAFTAR PUSTAKA

Rinaldi Munir. 2010. Matematika Diskrit, Bandung : Informatika Bandung

Pratama Yulian Surya. 2019. Teori Bilangan Bahan Ajar, Metro

Sumber online, https://www.academia.edu/25418848/Teori_Bilangan_Aritmatika_Modulo, diakses pada 19 oktober 2020