Pembaharuan Terakhir: 28 Maret 2017 Pengantar Teori Bilangan (Bagian 5):
Bilangan Prima dan Teorema Fundamental Aritmatika M. Zaki Riyanto Program Studi Matematika Fakultas Sains dan Teknologi UIN Sunan Kalijaga Yogyakarta
[email protected] http://zaki.sandimath.web.id
1
Bilangan Prima
Setiap bilangan bulat positif pasti memiliki suatu pembagi positif, paling tidak bilangan tersebut memiliki paling sedikit dua pembagi positif, yaitu 1 dan dirinya sendiri. Pada bagian ini akan dibahas suatu bilangan bulat positif yang memiliki tepat dua pembagi positif, yaitu 1 dan dirinya sendiri. Bilangan dengan sifat seperti ini sangat penting peranannya dalam Teori Bilangan, juga dalam berbagai aplikasinya seperti pada kriptografi. Bilangan seperti ini nantinya dinamakan dengan bilangan prima. Definisi 1.1 (Bilangan Prima dan Bilangan Komposit). Suatu Bilangan bulat p > 1 disebut prima jika p memiliki tepat dua pembagi positif, yaitu 1 dan dirinya sendiri. Bilangan bulat k > 1 disebut komposit jika k tidak prima. Dengan kata lain, k disebut komposit jika terdapat bilangan bulat a dan b dengan 1 < a, b < k sedemikian hingga k = ab. Contoh 1.1. Sepuluh bilangan prima pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23 dan 29. Sedangkan sepuluh bilangan komposit pertama adalah 4, 6, 8, 9, 10, 12, 14, 15, 16 dan 18. Lemma 1.1. Untuk setiap bilangan bulat n > 1 selalu memiliki suatu pembagi prima, yaitu terdapat suatu bilangan prima p sedemikian hingga p|n. Bukti: Lemma ini akan dibuktikan menggunakan kontradiksi. Andaikan terdapat bilangan bulat positif lebih dari 1 yang tidak memiliki pembagi prima. Misalkan n adalah
1
bilangan terkecil yang memenuhi sifat lebih dari 1 dan tidak memiliki pembagi prima. Karena n tidak memiliki pembagi prima dan n membagi habis n, maka n bukan bilangan prima atau komposit. Oleh karena itu, n dapat dinyatakan sebagai n = ab dengan 1 < a, b < n. Karena a < n, maka a memiliki pembagi prima, yaitu terdapat bilangan prima p sedemikian hingga p|a. Diketahui a|n, maka p|n yaitu p adalah pembagi prima dari n. Kontradiksi dengan pernyataan bahwa n tidak memiliki pembagi prima. Dengan demikian, dapat disimpulkan bahwa setiap bilangan bulat yang lebih dari 1 selalu memiliki suatu pembagi prima.
Teorema 1.2. Ada tak terhingga banyak bilangan prima. Bukti: Andaikan ada berhingga banyak bilangan prima, misalkan p1 , p2 , ..., pn adalah semua bilangan prima. Dibentuk M = p1 p2 · · · pn + 1. Berdasarkan Lemma 1.1, maka M memiliki suatu pembagi prima, yaitu terdapat suatu bilangan prima pi sedemikian hingga pi |M . Diketahui pi |p1 p2 · · · pn dan 1 = M −p1 p2 · · · pn , akibatnya pi |1. Hal ini tidak mungkin terjadi karena pi > 1. Oleh karena itu, yang benar adalah ada tak terhingga banyak bilangan prima.
Teorema 1.3. Jika n adalah bilangan komposit, maka n memiliki suatu pembagi prima yang √ kurang dari n. Bukti: Diketahui n adalah bilangan komposit, maka n = ab dengan a dan b adalah bilan√ √ gan bulat yang memenuhi 1 < a ≤ b < n. Andaikan b ≥ a > n, maka ab > ( n)2 = n dan √ hal ini kontradiksi dengan n = ab. Akibatnya haruslah a ≤ n. Berdasarkan Lemma 1.1, maka a pasti memiliki suatu pembagi prima, yaitu terdapat bilangan prima p < n sehingga p|a. Diperoleh bahwa p|a dan a|n, yang berarti p|n.
Teorema 1.4. Diberikan suatu bilangan prima p, maka untuk setiap bilangan bulat a dengan 1 ≤ a < p berlaku gcd(a, p) = 1, yaitu a dan p relatif prima. Bukti: Diketahui a adalah bilangan bulat dengan 1 ≤ a < p. Diketahui p adalah bilangan prima, maka p hanya memiliki dua pembagi positif yaitu 1 dan p. Diketahui a 6= p, maka 1|a dan 1|p, dan jika d|a dan d|p, maka d ≤ 1. Hal ini berakibat bahwa gcd(a, p) = 1.
Teorema 1.5. Diberikan suatu bilangan prima p, maka untuk setiap bilangan bulat a berlaku gcd(a, p) = 1 atau gcd(a, p) = p. 2
Bukti: Diberikan bilangan prima p dan bilangan bulat a. Menggunakan algoritma pembagian diperoleh bahwa a = pq + r, untuk suatu q, r ∈ Z dengan 0 ≤ r < p. Jika r = 0, yaitu p membagi habis a, maka a = pq. Diperoleh bahwa gcd(a, p) = gcd(pq, p) = p. Selanjutnya, jika r 6= 0, maka a = pq+r dengan 1 ≤ r < p. Berdasarkan Lemma 1.1 pada bagian Algoritma Euclid dan Teorema 1.4 di atas, diperoleh bahwa gcd(a, p) = gcd(pq + r, p) = gcd(r, p) = 1. Dengan demikian, terbukti bahwa gcd(a, p) = 1 atau gcd(a, p) = p.
2
Teorema Fundamental Aritmatika
Dalam kajian di Teori Bilangan, ada sebuah sifat yang sangat penting yang dimiliki oleh bilangan bulat yang berkaitan dengan bilangan prima. Sifat ini menyatakan bahwa setiap bilangan bulat yang lebih dari 1 dapat dinyatakan secara tunggal sebagai hasil kali dari sejumlah bilangan prima. Sebagai contohnya adalah 100 = 2 · 2 · 5 · 5 = 22 · 52 dan 150 = 2 · 3 · 5 · 5 = 2 · 3 · 52 . Sifat ini dinamakan dengan Teorema Fundamental Aritmatika yang akan dibahas berikut. Sebelumnya diberikan terlebih dahulu beberapa lemma pendukungnya. Lemma 2.1. Diberikan a, b, c ∈ Z dengan a, b, c > 0. Jika gcd(a, b) = 1 dan a|bc, maka a|c. Bukti: Diketahui a|bc, maka bc = am untuk suatu m ∈ Z. Diketahui gcd(a, b) = 1, maka menggunakan Teorema Bezout diperoleh bahwa terdapat m, n ∈ Z sedemikian hingga ma + nb = 1. Selanjutnya, kedua ruas dikalikan dengan c, diperoleh mac + nbc = c. Diketahui bc = am, maka c = mac + nam = a(mc + nm) yang berakibat bahwa a|c.
Lemma 2.2. Diberikan bilangan prima p dan a, b ∈ Z. Jika p|ab, maka p|a atau p|b. Bukti: Diketahui p adalah bilangan prima. Diberikan a, b ∈ Z dengan p|ab. Andaikan p tidak membagi habis a, maka gcd(a, p) = 1. Diketahui p|ab, menggunakan Lemma 2.2 diperoleh bahwa p|b. Untuk kasus p tidak membagi habis b dapat diperoleh bahwa p|a. Dengan demikian, terbukti bahwa p|a atau p|b.
3
Lemma 2.3. Diberikan bilangan prima p dan a1 , a2 , ..., an ∈ Z. Jika p|(a1 a2 · · · an ), maka p membagi salah satu dari a1 , a2 , ..., an , yaitu p|ai , untuk suatu i dengan 1 ≤ i ≤ n. Bukti: Lemma ini akan dibuktikan menggunakan induksi matematika pada n. Untuk n = 1 maka jelas pernyataan benar yaitu p|a1 . Untuk n = 2 juga benar, karena telah dibuktikan pada Lemma 2.2. Selanjutnya, diasumsikan pernyataan benar untuk n = k yaitu jika p|(a1 a2 · · · ak ), maka p|ai , untuk suatu i dengan 1 ≤ i ≤ k. Akan ditunjukkan bahwa pernyataan benar untuk n = k + 1. Dimisalkan p|(a1 a2 · · · ak ak+1 ), atau dapat ditulis p|((a1 a2 · · · ak )ak+1 ). Berdasarkan Lemma 2.2, diperoleh bahwa p|(a1 a2 · · · ak ) atau p|ak+1 . Berdasarkan asumsi induksi diperoleh bahwa p|ai untuk suatu i dengan 1 ≤ i ≤ k atau p|ak+1 . Dengan kata lain, p|ai untuk suatu i dengan 1 ≤ i ≤ k + 1.
Teorema 2.4 (Teorema Fundamental Aritmatika). Setiap bilangan bulat positif lebih dari 1 dapat dinyatakan secara tunggal sebagai hasil kali bilangan-bilangan prima. Dengan kata lain, untuk setiap bilangan bulat positif n > 1 dapat difaktorkan secara tunggal sebagai n = p1 p2 · · · ps dengan p1 , p2 , ..., ps adalah bilangan-bilangan prima dan p1 ≤ p2 ≤ ... ≤ ps . Selanjuntya, bentuk n = p1 p2 · · · ps disebut dengan faktorisasi prima dari n. Bukti: Teorema ini akan dibuktikan menggunakan kontradiksi. Diandaikan bahwa ada bilangan bulat positif lebih dari 1 yang tidak dapat dinyatakan sebagai hasil kali bilanganbilangan prima. Dipilih n adalah bilangan bulat positif lebih dari 1 yang terkecil yang tidak dapat dinyatakan sebagai hasil kali bilangan-bilangan prima, maka n bukan bilangan prima. Oleh karena itu, n = ab untuk suatu bilangan bulat a dan b dengan 1 < a, b < n. Akibatnya a dan b dapat dinyatakan sebagai hasil kali bilangan-bilangan prima. Diperoleh bahwa n = ab juga dapat dinyatakan sebagai hasil kali bilangan-bilangan prima, sehingga kontradiksi dengan pengandaian. Dengan demikian, terbukti bahwa setiap bilangan bulat positif lebih dari satu dapat dinyatakan sebagai hasil kali bilangan-bilangan prima. Selanjutnya, akan dibuktikan ketunggalan bentuk faktorisasi prima. Diberikan bilangan bulat positif n > 1. Diandaikan n memiliki dua bentuk faktorisasi prima yang berbeda, yaitu n = p1 p2 · · · ps dan n = q1 q2 · · · qt dengan p1 , p2 , ..., ps , q1 , q2 , ..., qt adalah bilanganbilangan prima dan p1 ≤ p2 ≤ ... ≤ ps dan q1 ≤ q2 ≤ ... ≤ qt . Selanjutnya, kedua bentuk faktorisasi prima dari n dibagi dengan pembagi prima yang sama dari keduanya, sehingga diperoleh pi1 pi2 ...piu = qj1 qj2 ...qjv dimana ruas kiri tidak sama dengan ruas kanan dan u, v ≥ 1. Akibatnya, bilangan prima pi1 membagi habis qj1 qj2 ...qjv . Berdasarkan Lemma 2.3 diperoleh bahwa pi1 membagi habis salah 4
satu dari qj1 , qj2 , ..., qjv , yaitu pi1 |qjw untuk suatu 1 ≤ w ≤ v. Keadaan ini tidak mungkin terjadi, sebab pi1 dan qjw keduaya adalah bilangan prima yang berbeda, sehingga timbul kontradiksi. Dengan demikian, yang benar adalah faktorisasi prima dari n adalah bersifat tunggal.
Akibat 2.5. Untuk setiap bilangan bulat positif n > 1, terdapat bilangan-bilangan prima p1 , p2 , ..., pm dan bilangan-bilangan bulat e1 , e2 , ..., em ≥ 0 sedemikian hingga n = pe11 pe22 · · · pemm . Bukti: Latihan.
3
Aplikasi Faktorisasi Prima pada Perhitungan Pembagi Persekutuan Terbesar dan Kelipatan Persekutuan Terkecil
Faktorisasi prima dari 100 adalah 100 = 22 · 52 . Faktorisasi prima dari 150 adalah 150 = 2 · 3 · 52 . Diketahui bahwa gcd(100, 150) = 50. Diketahui bahwa 100 = 22 · 30 · 52 dan 150 = 21 · 31 · 52 . Dapat dilihat bahwa gcd(100, 150) = 50 = 21 · 52 . Dapat dilihat bahwa perhitungan pembagi persekutuan terbesar dari 100 dan 150 dapat dicari menggunakan hasil faktorisasi prima dari 100 dan 150. Sifat seperti ini berlaku secara umum untuk sebarang dua bilangan bulat positif lebih dari 1 seperti diberikan pada teorema di bawah ini. Teorema 3.1. Diberikan a, b ∈ Z dengan a, b > 1. Misalkan faktorisasi prima dari a dan b adalah a = pe11 pe22 · · · pemm dan b = pf11 pf22 · · · pfmm , maka pembagi persekutuan terbesar dari a dan b adalah min(e ,f ) min(e ,f ) m ,fm ) gcd(a, b) = p1 1 1 p2 2 2 · · · pmin(e . m Bukti: Latihan. Sebagai contohnya, diketahui 100 = 22 · 30 · 52 dan 150 = 21 · 31 · 52 . Diperoleh bahwa gcd(100, 150) = 2min(2,1) · 3min(0,1) · 5min(2,2) = 21 · 30 · 52 = 50. Berikut ini diberikan pengertian dari kelipatan persekutuan terbesar (least common multiple) dari dua bilangan bulat. Definisi 3.1. Kelipatan persekutuan terkecil (least common multiple) dari dua bilangan bulat a dan b, dinotasikan dengan lcm(a, b), didefinisikan sebagai bilangan bulat positif terkecil yang habis dibagi oleh a dan b. Dengan kata lain, lcm(a, b) = l jika memenuhi: 5
(i) a|l dan b|l (ii) Jika a|c dan b|c, maka l ≤ c. Sebagai contohnya adalah lcm(4, 6) = 12, lcm(−3, 5) = 15, lcm(6, 12) = 12 dan lcm(100, 150) = 300. Diketahui faktorisasi prima dari 100 adalah 100 = 22 · 52 dan faktorisasi prima dari 150 adalah 150 = 2 · 3 · 52 . Dapat dilihat bahwa lcm(100, 150) = 300 = 22 · 3 · 52 . Teorema 3.2. Diberikan a, b ∈ Z dengan a, b > 1. Misalkan faktorisasi prima dari a dan b adalah a = pe11 pe22 · · · pemm dan b = pf11 pf22 · · · pfmm , maka kelipatan persekutuan dari a dan b adalah max(e1 ,f1 ) max(e2 ,f2 ) max(em ,fm ) lcm(a, b) = p1 p2 · · · pm . Bukti: Latihan. Sebagai contohnya, diketahui 100 = 22 · 30 · 52 dan 150 = 21 · 31 · 52 . Diperoleh bahwa lcm(100, 150) = 2max(2,1) · 3max(0,1) · 5max(2,2) = 22 · 31 · 52 = 300. Selanjutnya, berikut ini diberikan sifat-sifat yang menjelaskan hubungan antara pembagi persekutuan terbesar dan kelipatan persekutuan terkecil. Sebelumnya, diberikan lemma berikut. Lemma 3.3. Diberikan dua bilangan real x dan y, maka max(x, y) + min(x, y) = x + y. Bukti: Diberikan bilangan real x dan y. Jika x < y, maka max(x, y) + min(x, y) = y + x = x + y. Jika x = y, maka jelas max(x, y) + min(x, y) = x + y. Jika x > y, maka max(x, y) + min(x, y) = x + y.
Teorema 3.4. Diberikan a, b ∈ Z dengan a, b > 1, maka ab = lcm(a, b)gcd(a, b). Bukti: Diberikan faktorisasi prima dari a dan b yaitu a = pe11 pe22 · · · pemm dan b = pf11 pf22 · · · pfmm . Menggunakan Lemma 3.3 dapat diperoleh: max(e ,f ) max(e ,f )
max(e ,f ) min(e ,f ) min(e ,f )
min(e ,fm )
1 1 2 2 lcm(a, b)gcd(a, b) = p1 p2 · · · pm m m p1 1 1 p2 2 2 · · · pm m max(e1 ,f1 )+min(e1 ,f1 ) max(e2 ,f2 )+min(e2 ,f2 ) max(e ,f )+min(em ,fm ) = p1 p2 · · · pm m m em +fm = pe11 +f1 pe22 +f2 · · · pm = pe11 pe22 · · · pemm pf11 pf22 · · · pfmm = ab.
Dengan demikian, terbukti bahwa ab = lcm(a, b)gcd(a, b).
6
4
Soal-soal Latihan
(1) Buktikan bahwa setiap bilangan prima yang tidak sama dengan 2 adalah bilangan ganjil. (2) Tentukan semua pembagi prima dari 10!. (3) Tentukan bilangan prima terkecil di antara 100 dan 200. (4) Tunjukkan bahwa setiap bilangan bulat lebih dari 11 dapat dinyatakan sebagai jumlahan dua bilangan komposit. (5) Diberikan a adalah bilangan bulat positif yang tidak memiliki pembagi prima p dengan √ 1 < p < a. Buktikan bahwa a adalah bilangan prima. (6) Tentukan faktorisasi prima dari 500, 5040 dan 9999. (7) Tentukan semua pembagi prima dari 100.000 dan 10!. (8) Diberikan a dan b adalah bilangan bulat positif. Buktikan bahwa jika a3 |b2 , maka a|b. (9) Diberikan bilangan prima p dan a ∈ Z. Jika p|a2 , buktikan bahwa p|a. (10) Diberikan bilangan prima p dan a, n ∈ Z dengan n¿0. Jika p|an , buktikan bahwa p|a. (11) Diberikan bilangan prima p dan bilangan bulat positif n, maka pa dikatakan tepat membagi n, dinotasikan dengan pa ||n jika pa |n dan pa+1 tidak membagi habis n. Sebagai contohnya adalah 23 ||40, sebab 24 tidak membagi habis 40. (a) Buktikan bahwa jika pa ||m dan pb ||n, maka pa+b ||mn. (b) Buktikan bahwa jika pa ||m, maka pab ||mb . (c) Buktikan bahwa jika pa ||m dan pb ||n dengan a 6= b, maka pmin(a,b) ||(m + n). (12) Diberikan bilangan bulat positif n > 1. Buktikan bahwa
Pn
1 i=1 i
bukan bilangan bulat.
(13) Diberikan a, b, c ∈ Z. Buktikan bahwa lcm(a, b)|c jika dan hanya jika a|c dan b|c. (14) Diberikan a, b, c ∈ Z dengan c|ab. Buktikan bahwa c|(gcd(a, c)gcd(b, c)). (15) Diberikan a, b, n ∈ Z dengan a, b, n > 0. Jika a dan b relatif prima, buktikan bahwa an dan bn juga relatif prima. (16) Diberikan a, b ∈ Z dengan a, b > 0. Buktikan bahwa gcd(a, b) = gcd(a + b, lcm(a, b)). (17) Diberikan a, b, c ∈ Z dengan a, b, c > 0. Buktikan bahwa gcd(lcm(a, b), c) = lcm(gcd(a, c), gcd(b, c)). 7
(18) Diberikan a, b, c ∈ Z dengan a, b, c > 0. Buktikan bahwa lcm(gcd(a, b), c) = gcd(lcm(a, c), lcm(b, c)). (19) Tunjukkan bahwa ada tak terhingga banyak bilangan prima yang berbentuk 6n + 5, dengan n adalah bilangan bulat positif. (20) Sebuah toko komputer menjual flashdisk dengan harga di bawah harga normal Rp 99.000 melalui potongan harga, tetapi dijual di atas Rp 1.000. Jika toko komputer tersebut berhasil menjual sejumlah flashdisk dengan harga total Rp 8.137.000 dan potongan harga berupa bilangan bulat, tentukan banyaknya flashdisk yang terjual.
Pustaka [1] Rosen Kenneth, H., 2011, Elementary Number Theory and Its Applications, Sixth Edition, Pearson Education, USA. [2] Sukirman, 2006, Pengantar Teori Bilangan, Penerbit Hanggar Kreator, Yogyakarta.
8
