2.1 Bilangan prima dan faktorisasi prima

BAB 2 BILANGAN PRIMA 2.1

Bilangan prima dan faktorisasi prima

Definisi 2.1.1. Bilangan bulat p > 1 dikatakan prima jika ia hanya mempunyai pembagi p dan 1. Dengan kata lain bilangan prima tidak mempunyai pembagi selain dari 1 dan dirinya sendiri. Berdasarkan definisi ini, 1 bukanlah bilangan prima. Bilangan prima terkecil adalah 2 yang merupakan bilangan genap. Sedangkan bilangan prima lainnya, seperti 3, 5, 7, 11, · · · semuanya bilangan ganjil. Ingat, sebaliknya bilangan ganjil belum tentu prima; misalnya 9 ganjil tapi bukan prima. Bilangan bukan prima seperti 4, 6, 8, 9, · · · disebut bilangan komposit. Bila n komposit maka ia dapat dinyatakan sebagai n = ab dimana a, b ∈ Z, 1 < a < n, 1 < b < n. Teorema 2.1.1. Misalkan p prima dan a, b bilangan bulat sebarang. Maka berlaku pernyataan berikut: (i) p membagi a, atau kalau tidak, a dan p koprima. (ii) jika p membagi ab maka p membagi a atau p membagi b. Bukti. (i) Diperhatikan gcd(a, p) haruslah pembagi positif p, jadi ia mesti 1 atau p. Untuk kasus gcd(a, p) = p maka disimpulkan p membagi a. Kalau tidak maka gcd(a, p) = 1, ini berarti a dan p koprima. (ii) Bila p tidak membagi a maka haruslah gcd(a, p) = 1. Dengan identitas Bezout, terdapat u, v ∈ Z sehingga 1 = au + pv. Jadi, b = aub + pvb dan karena p|b maka p|aub|; dan juga jelas bahwa p|pvb. Karena itu disimpulkan p|b := aub + pvb. Diperhatikan bahwa p prima pada teorema ini merupakan syarat perlu agar teorema ini berlaku. Bila p tidak prima, pernyataan pada teorema ini dapat saja salah. Misalkan ambil a = 6, b = 10 dan p = 4. Disini p|ab tetapi p tidak membagi a dan tidak membagi b.

1

2

Teori Bilangan by J.Hernadi

Akibat 2.1.1. Jika p prima dan p membagi a1 · · · an maka p membagi ai untuk suatu i, 1 ≤ i ≤ n. Bukti. Dibuktikan dengan induksi matematika. Untuk n=1, berarti p|a1 maka secara otomatis p|a1 . Andaikan berlaku untuk n = k, yaitu jika p|a1 · · · ak maka p|ai untuk suatu 1 ≤ i ≤ k. Untuk n = k + 1, tulis a = a1 · · · ak dan b = ak+1 . Berdasarkan Teorema 2.1.1(ii), p|a atau p|b. Bila kasus p|a terjadi maka berdasarkan hipotesis p|ai untuk suatu 1 ≤ i ≤ k. Bila kasus p|b terjadi maka p|ak+1 . Jadi p|ai untuk suatu 1 ≤ i ≤ k + 1. Ini berarti berlaku untuk n = k + 1. Akibat 2.1.2. Jika p, q1 , · · · q2 semuanya bilangan prima dan p|q1 · · · qn maka p = qk untuk suatu k, 0 ≤ k ≤ n. Berangkat dari hasil ini kita akan sampai pada hasil utama topik ini yaitu Teorema Fundamental Aritmatika (TFA) berikut. Teorema 2.1.2 (Teorema Fundamental Aritmatika). Setiap bilangan bulat n > 1 dapat disajikan sebagai perkalian bilangan prima berpangkat, yaitu n = pe11 · · · pekk , dimana p1 , · · · , pk bilangan prima berbeda dan e1 , · · · , ek bilangan bulat positif. Selanjutnya, representasi ini tunggal terlepas dari permutasi faktor-faktornya. Sebelum dibuktikan, perhatikan ilustrasi berikut: 200 = 23 ·52 = 52 ·23 . Teorema ini mengatakan bahwa bilangan prima merupakan balok-balok pembangun (building blocks) bilangan bulat. Inilah alasan mengapa bilangan prima sangat penting pada teori bilangan dan aplikasinya. Bukti. Dibuktikan dengan prinsip induksi kuat. Untuk n = 2, dapat ditulis n = 21 yaitu p1 = 2 dan e1 = 1. Andai teorema berlaku untuk semua bilangan bulat m, 1 < m < n yaitu m dapat disajikan sebagai perkalian bilangan-bilangan prima berpangkat. Sekarang untuk bilangan n, bila n prima maka n = n1 , beres. Tapi bila n komposit maka dapat ditulis n = ab dengan 1 < a, b < n. Karena berdasarkan hipotesis a dan b dapat disajikan sebagai perkalian bilangan-bilangan prima berpangkat, maka begitu juga dengan n. Terbukti bahwa setiap bilangan n > 1 dapat disajikan sebagai perkalian bilangan prima berpangkat. Selanjutnya dibuktikan bahwa representasi ini tunggal. Misalkan ada dua representasi berikut: n = p1 · · · pm = q1 · · · qt .

(*)

Disini terdapat kemungkinan faktor prima yang sama dan dapat disusun ulang secara terurut sehingga p1 ≤ p2 ≤ · · · ≤ pm dan q1 ≤ · · · ≤ qt , m ≤ t.

(**)

3


Karena p1 |n maka berdasarkan Akibat 2.1.1 p1 |qj untuk suatu j = 1, · · · , t. Dikarenakan urutan (**) maka diperoleh p1 ≥ q1 dan q1 ≥ p1 , sehingga diperoleh p1 = q1 . Selanjutnya, kedua ruas (*) dikansel p1 dan q1 diperoleh bentuk p2 · · · pm = q2 · · · qt . Argumen yang sama, diperoleh p2 = q2 dan p3 · · · pm = q3 · · · qt . Bila cara ini diteruskan dan seandainya m < t maka diperoleh bentuk terakhir 1 = qm+1 · · · qt , dan hal ini tidaklah mungkin (kontradiksi) karena qj > 1. Jadi haruslah m = t dan p1 = q1 , p2 = q2 , · · · , pm = qm . Terbukti representasi ini tunggal. Contoh 2.1.1. 360 = 23 · 32 · 5, 4725 = 33 · 52 · 7, 17460 = 23 · 32 · 5 · 72. Kita dapat menggunakan TFA untuk menyajikan perkalian, pembagian, pangkat, gcd dan lcm dua bilangan bulat dalam bentuk perkalian bilanganbilangan prima berpangkat. Misalkan a = pe11 · · · pekk dan b = pf11 · · · pfkk , ei , fi ≥ 0 maka berlaku ab = pe11 +f1 · · · pekk +fk a/b = pe11 −f1 · · · pekk −fk (asalkan b|a) 1 k am = pme · · · pme 1 k min{e1 ,f1 }

· · · pk

max{e1 ,f1 }

· · · pk

gcd(a, b) = p1 lcm(a, b) = p1

min{ek ,fk } max{ek ,fk }

.

Contoh 2.1.2. Misalkan a = 132 dan b = 400. Tentukan gcd dan lcm dari a dan b? Penyelesaian. Dengan menggunakan diagram pohon, anda dengan mudah mendapatkan faktorisasi berikut: 132 = 22 · 3 · 11 dan 400 = 24 · 52 . Agar bentuknya kompatibel tulis dalam bentuk: 132 = 22 · 3 · 50 · 11 dan 400 = 24 · 30 · 52 · 110 . Sehingga diperoleh gcd(132, 400) = = lcm(132, 400) = =

2min{2,4} · 3min{1,0} · 5min{0,2} · 11min{1,0} 22 · 30 · 50 · 110 = 4 2max{2,4} · 3max{1,0} · 5max{0,2} · 11max{1,0} 24 · 31 · 52 · 111 = 13200

4


Latihan 2.1.1. Dengan menggunakan TFA, temukan gcd dari (132,1995), (400,1995) dan (132,400,1995). Bilangan bulat n dikatakan bilangan kuadrat sempurna jika ada bilangan bulat m sehingga n = m2 . Contoh bilangan kuadrat sempurna: 4, 9, 16. Bilangan 24 dan 54 tidak ada yang kuadarat sempurna tetapi hasil kalinya 24 × 54 = 362 merupakan bilangan kuadrat sempurna. √ Teorema 2.1.3. Bila m bukan bilangan kuadrat sempurna maka m bilangan irrasional. √ Penyelesaian. Dibuktikan√kontraposisinya, yaitu jika m√rasional maka m kuadrat sempurna. Karena m rasional maka dapat ditulis m = ab dimana a dan b bulat positif. Kemudian dikuadratkan, diperoleh: a2 m = 2. b Misalkan a dan b mempunyai faktorisasi prima sebagai berikut: a = pe11 · · · pekk dan b = pf11 · · · pfkk , ei , fi ≥ 0 maka berlaku 2ek 1 a2 p2e 1 · · · pk m = 2 = 2f = b p1 1 · · · pk2fk

¶2

µ p1e1 −f1

· · · pekk −fk

.

Ini berarti m bilangan kuadrat sempurna. Contoh 2.1.3. Dengan Teorema ini kita memperoleh bahwa gan irrasional.

√ √ √ 2, 3, 6 bilan1

Latihan 2.1.2. Jika m dan n bilangan bulat positif, tentukan syarat agar m n rasional. Petunjuk: perhatikan ilustrasi berikut: adakah n bulat yang membuat 1 1 1 1 1 1 1 n , 2 n , 3 n , 7 n , 8 n , 9 n rasional. Ingat bilangan bulat juga bilangan rasional.

2.2

Distribusi bilangan prima

Mungkin muncul dibenak kita pertanyaan berikut: apakah ada bilangan prima terbesar dan kalau ada berapa bilangan prima tersebut? Jawaban terhadap pertanyaan ini akan terjawab melalui teorema berikut. Teorema 2.2.1. Terdapat takberhingga banyak bilangan prima. Bukti. Bukti dengan kontradiksi. Andai hanya terdapat berhingga banyak bilangan prima, katakan mereka adalah p1 , p2 , · · · , pk . Misalkan m = (p1 · · · pk ) + 1.

5


Karena m > 1 maka berdasarkan TFA maka m dapat dibagi oleh suatu bilangan prima, katakan bilangan prima tersebut p. Ini berarti p haruslah salah satu dari p1 , p2 , · · · , pk . Jadi diperoleh: p|p1 · · · pk , dan p|m ⇒ p|m − p1 · · · pk = 1. Hal ini kontradiksi karena p > 1 sehingga p|1 tidaklah mungkin. Dengan demikian kita dapat memastikan bahwa tidak ada bilangan prima terbesar. Beberapa bilangan prima terurut adalah p1 = 2, p2 = 3, p3 = 5, p4 = 7. Pertanyaan selanjutnya adalah bagaimana pola distribusi bilangan prima? Lebih spesifiknya, ada berapa banyak bilangan prima yang kurang dari 10, antara 1 dan 1000, antara 1001 dan 2000, antara 2001 dan 3000, dan seterusnya? n−1

Akibat 2.2.1. Bila pn bilangan prima ke-n maka ia memenuhi pn ≤ 22 semua n ≥ 1.

untuk

Bukti. Buktikan dengan induksi matematika. Sesungguhnya estimasi ini terlalu lemah. Misalnya,untuk n = 4 diperoleh 2 = 256 tetapi p4 = 7, jadi masih terlalu lebar. Untuk suatu bilangan real x, misalkan π(x) menyatakan banyaknya bilangan prima yang kurang dari atau sama dengan x. Misalnya π(1) = 0 karena tidak ada bilangan prima yang dimaksud, π(5) = π(5.5) = 3 karena bilangan prima yang dimaksud adalah 2, 3, 5. Berkaitan dengan akibat di atas, berlaku estimasi berikut: π(x) ≥ blg lg xc + 1 23

dimana lg x :=2 log x. Sekali lagi estimasi ini terlalu longgar. Sebagai ilustrasi, untuk x = 109 maka blg lg xc + 1 = 5 tetapi kenyataannya banyak bilangan prima yang kurang dari 109 sangat banyak, diperkirakan 5 × 107 . Gauss pada tahun 1793 memberikan konjektur sebagai berikut: Z x dt x π(x) ≈ atau π(x) ≈ . ln x 2 ln t Ini berarti berlaku

π(x) x ln x

→ 1, untuk x → ∞.

Konjektur ini akhirnya dibuktikan oleh Hadamard dan de la Val´ee Poussin pada tahun 1896. Dapat juga dinyatakan bahwa perbandingan 1 π(x) ≈ → 0. bxc ln x Dengan menggunakan pola ini maka dapat disimpulkan bahwa distribusi bilangan prima semakin lama semakin jarang. Misalnya ada 168 prima diantara 1 dan 1000, ada 135 prima diantara 1001 dan 2000, kemudian ada 127 prima diantara 2001 dan 3000, dan seterusnya. Coba periksa! Latihan 2.2.1. Temukan cara untuk mendapatkan semua bilangan prima diantara 1 dan 100.

6


2.3

Bilangan Fermat dan prima Mersenne

Diperhatikan bilangan prima 3, 5, 7, 17, 31, · · · ,. Bilangan prima ini mempunyai bentuk 2n ± 1, katakan 3 = 22 − 1, 5 = 22 + 1, 7 = 23 − 1 dan lain-lain. Banyak sekali bilangan prima berbentuk seperti ini. Tetapi tidak semua bilangan dalam bentuk 2n ± 1 merupakan bilangan prima, misalnya 33 = 25 + 1 bukan prima. Teorema 2.3.1. Jika 2m + 1 prima maka m = 2n untuk suatu bilangan bulat n ≥ 0. Bukti. Dibuktikan kontraposisinya. Diketahui m bukan merupakan pangkat dari 2. Berarti ia berbentuk m = 2n q dimana q > 1 ganjil. Ilustrasi: 7 = 20 × 7; 14 = 21 × 7; 24 = 24 × 3. Diperhatikan fungsi f (t) = tq + 1 mempunyai nilai nol di t = −1, sebab q ganjil. Tegasnya, ia dapat difaktorkan sebagai tq + 1 = (t + 1)(tq−1 − tq−2 + tq−3 − · · · − t + 1). n

Jadi t+1 adalah salah satu faktor sejati dari tq +1. Ambil t = x2 , maka diperoleh ¡ n ¢q n n g(x) := f (x2 ) = x2 + 1 = x2 q + 1 = xm + 1. n

Dengan mengambil x = 2 kita dapatkan bahwa 22 + 1 adalah faktor sejati dari g(2) = xm + 1 sehingga xm + 1 bukan prima. n

Bilangan Fn := 22 + 1 disebut bilangan Fermat dan bilangan ini yang prima disebut bilangan prima Fermat. Konjektur Fermat mengatakan bahwa Fn prima untuk setiap n > 0. Beberapa diantaranya untuk n = 0, 1, 2, 3, 4 bilangan yang dimaksud adalah Fn = 3, 5, 17, 257, 65537 kesemuanya adalah prima. Tetapi pada tahun 1732 Euler menunjukkan bilangan Fermat berikutnya, yaitu 5

F5 = 22 + 1 = 4294967297 = 641 × 6700417 ternyata bukan prima. Walaupun tidak semua bilangan Fermat prima namun setiap pasang bilangan Fermat adalah koprima. Fakta ini dapat digunakan sebagai bukti alternatif mengenai ketakberhinggaan banyak bilangan prima. Latihan 2.3.1. Jika a ≥ 2 dan am + 1 prima (misalnya 62 + 1 = 37) maka a genap dan m bilangan pangkat dari 2. Teorema 2.3.2. Jika m > 1 dan am − 1 prima maka a = 2 dan m prima. Bukti. Bilangan yang berbentuk 2p −1 dimana p prima disebut bilangan Mersenne dan bilangan ini yang prima disebut bilangan prima Mersenne, dikembangkan oleh ybs pada tahun 1644. Untuk beberapa bilangan prima p = 2, 3, 5, 7, bilangan Mersenne yang bersesuaian adalah Mp = 3, 7, 31, 127. Kelihatannya prima semua, tetapi M11 = 2047 = 23 × 89 ternyata bukan prima. Namun tidak banyak bilangan Mersenne yang prima. Pada saat itu baru ditemukan 32 buah bilangan prima Mersenne. Yang terakhir ditemukan pada tahun 1996 oleh David Slowinski and Joel Armengaud M1257787 dan M1398269 dengan bantuan komputer mutakhir.

7


2.4

Uji primalitas dan faktorisasi

Dua pertanyaan yang semestinya muncul dibenak kita berkitan dengan teori yang baru saja kita bahas adalah sebagai berikut: (1) Bagaimana kita memastikan suatu bilangan bulat n > 1 yang diberikan adalah prima atau bukan? (2) Bagaimana cara memperoleh faktorisasi prima berpangkat dari bilangan bulat n? Pertanyaan (1) berkaitan dengan uji primalitas, teorema berikut dapat digunakan sebagai acuan. Teorema 2.4.1. Bilangan √ bulat n > 1 komposit jika hanya jika ia dapat dibagi oleh bilangan prima p ≤ n. Bukti. Contoh 2.4.1. 97 prima karena ia tidak terbagi oleh semua prima≤ oleh 2, 3, 5 dan 7.

√

97, yaitu

Untuk bilangan besar masih sulit mendeteksi primalitasnya karena kita perlu memastikan suatu bilangan bulat n dapat dibagi oleh banyak bilangan prima. Untuk itu diperhatikan bentuk desimal bilangan bulat n = ak ak−1 · · · a1 a0 ditulis sebagai n = a0 + a1 10 + a2 102 + · · · + ak 10k , ak 6= 0, 0 ≤ ai ≤ 9. Dengan mudah dapat dipikirkan bahwa 1. n habis dibagi 2 jika a0 habis dibagi 2, yaitu a0 = 2, 4, 6 atau 8. 2. n habis dibagi 5 jika a0 = 0 atau 5. 3. n habis dibagi 3 jika jumlah angka-angkanya habis dibagi 3, yaitu a0 + a1 + · · · + ak habis dibagi 3. Fakta ini dapat ditunjukkan dengan menggunakan formula binomial pada suku 10i = (9+1)1 dan diperoleh bentuk 10i = 9q+1. Coba selidiki sendiri. 4. n habis dibagi 11 jika jumlahan berikut (−1)k ak + (−1)k−1 ak−1 + · · · − a1 + a0 habis dibagi 11. Fakta ini dapat ditelusuri pada kenyataan bahwa 10i = (11 − 1)i = 11q + (−1)i . Contoh 2.4.2. Selidikilah apakah 38203 habis dibagi 3?, apakah habis dibagi 11?


8

Penyelesaian. Diperhatikan 3 + 8 + 2 + 0 + 3 = 16, bilangan ini tidak habis dibagi 3, jadi ia tidak habis dibagi 3. Selanjutnya, diketahui k = 4 sehingga diperoleh 3 − 8 + 2 − 0 + 3 = 0 habis dibagi 11, jadi ia habis dibagi 11. Faktanya 38203 = 11 × 3473. Latihan 2.4.1. Selidikilah apakah 8703585473 habis dibagi 3?, apakah habis dibagi 11? Latihan 2.4.2. Apakan bilangan berikut: 157, 221, 641, 1103 prima? Latihan 2.4.3. Temukan kriteri suatu bilangan bulat habis dibagi 4, juga habis dibagi 6. Latihan 2.4.4. Faktorkan 247 dan 6887. Latihan 2.4.5. Faktorkan 3992003. Gunakan bantuan program komputer bila diperlukan.

Latihan Tambahan 1. For which primes p is p2 + 2 also prime? 2. Show that if p > 1 and p divides (p − 1)! + 1, then p is prime. 3. It has been conjectured that there are infinitely many primes of the form n2 − 2. Exhibit five such primes. 4. Prove each of the assertions below: a. Any prime of the form 3n + 1 is also of the form 6m + 1. b. Each integer of the form 3n + 2 has a prime factor of this form. c. The only prime of the form n3 − 1 is 7. [Hint: Write n3 − 1 as (n − 1)(n2 + n + 1)]. d. The only prime p for which 3p + 1 is a perfect square is p = 5. e. The only prime of the form n2 − 4 is 5. 5. If p > 5 is a prime number, show that p2 + 2 is composite. [Hint: p takes one of the forms 6k + 1 or 6k + 5.] 6. Establish each of the following statements: a. Every integer of the form n4 + 4, with n > 1, is composite. [Hint: Write n4 + 4 as a product of two quadratic factors.] b If n > 4 is composite, then n divides (n1)!. c. Any integer of the form 8n + 1, where n > 1, is composite. [Hint: (2n + l)|(23n + 1).]


9

d. Each integer n > 11 can be written as the sum of two composite numbers. [Hint: If n is even, say n = 2k, then n6 = 2(k3); for n odd, consider the integer n − 9.] 7. If p > q > 5 and p and q are both primes, prove that 24|(p2 − q 2 ). 8. Show that F0 F1 ...Fn−1 = Fn − 2 for all n > 1. 9. Evaluate the Mersenne number M17 , and determine whether it is prime. 10. It has been conjectured that every even integer can be written as the difference of two consecutive primes in infinitely many ways. For example, 6 = 29 − 23 = 137 − 131 = 599 − 593 = 1019 − 1013. Express the integer 10 as the difference of two consecutive primes in 15 ways.

2.1 Bilangan prima dan faktorisasi prima

Recommend Documents