FAKTA TENTANG BILANGAN PRIMA

 Oleh: Yuliyanto

Bilangan N = 49.725 menyatakan usia sekelompok remaja yang dikalikan. Berapa banyak remaja dan berapa usia mereka? Jelaskan bagaimana Anda menemukan jawaban tersebut.

Kita perlu belajar banyak mengenai pemfaktoran bilangan bulat untuk menyelesaikan permasalahan di atas. Bagaimana kita bisa mengetahui banyak remaja dalam kelompok itu? Apakah hasilnya merupakan bilangan prima?  Selama proses menyelesaikan, kita perlu mengembangkan ide intuitif tentang beberapa sifat bilangan prima yang akan kita bahas lebih lanjut di bagian ini.

Topik yang sangat penting dalam materi ini adalah konsep bilangan prima. Sebuah bilangan bulat N yang lebih dari 1 merupakan bilangan prima apabila satu-satunya cara menyatakan pemfaktorannya adalah 1 x N. Sebagai contoh, 2 merupakan bilangan prima karena satu-satunya cara memfaktorkan bilangan itu adalah 1 x 2. (Kita anggap faktorisasi 2 x 1 sebagai faktorisasi yang sama, walaupun urutannya berbeda). Demikian pula, 3 merupakan bilangan prima. Perhatikan bahwa bilangan prima merupakan bilangan yang lebih besar dari 1.

Bilangan bulat lebih dari 1 yang bukan prima disebut bilangan komposit. Ini berarti bahwa bilangan bulat tersebut dapat difaktorkan menjadi dua atau lebih bilangan prima. Sebagai contoh, 9 merupakan bilangan komposit, karena dapat difaktorkan menjadi 3 x 3. Demikian pula 14 juga merupakan bilangan komposit, karena dapat difaktorkan menjadi 2 x 7. Dalam menemukan faktor persekutuan terbesar (FPB) dari beberapa bilangan, seringkali kita harus memfaktorkan bilangan-bilangan itu ke dalam faktor-faktor primanya. Kita akan membahasnya lebih banyak nanti. Sebagai contoh, 36 = 4 x 9 = 2 x 2 x 3 x 3. Meskipun tampak jelas bahwa setiap bilangan komposit dapat difaktorkan ke dalam faktor-faktor primanya, kita harus benar-benar meyakininya.

Untuk keperluan tersebut, perhatikan teorema yang mengatakan bahwa, “Setiap bilangan komposit N dapat difaktorkan ke dalam faktor prima”. Bukti dari teorema ini cukup mudah. Ingat bahwa bilangan asli, meliputi 1, 2, 3, ... . Selanjutnya, jika N bilangan komposit, maka N dapat difaktorkan menjadi dua bilangan asli yang lebih kecil, a dan b. Jika keduanya prima, selesailah bukti kita. Jika tidak, maka setiap faktor komposit dapat difaktorkan dalam bilangan asli yang lebih kecil. Jika bilangan-bilangan asli yang lebih kecil itu semuanya prima, selesailah pembuktian kita. Jika tidak, setiap faktor komposit dapat difaktorkan menjadi bilangan asli yang lebih kecil. Kata kunci dalam pembuktian ini yaitu “lebih kecil”. Kita tidak mungkin terus memfaktorkan tanpa batas, karena setiap kali kita memfaktorkan, kita peroleh faktor bilangan asli yang lebih kecil, dan banyak bilangan asli yang lebih kecil dari N itu berhingga. Jadi, prosesnya harus diakhiri setelah kita tidak dapat menemukan lagi faktor bilangan asli yang lebih kecil. Pada kondisi tersebut setiap bilangan dalam faktorisasi N merupakan bilangan prima.

Teorema di atas membawa akibat, yaitu “Setiap bilangan bulat N > 1 dapat merupakan bilangan prima atau dapat difaktorkan menjadi bilangan prima”. Kita mulai pembuktian ini dengan mengingat bahwa salah satu kemungkinan dari N yaitu merupakan bilangan prima atau komposit. Jika bilangan prima, selesai pembuktian kita. Jika komposit, maka berdasarkan teorema sebelumnya dapat difaktorkan menjadi bilangan-bilangan prima.

Teorema di atas kelihatannya seperti biasa. Tetapi faktanya setiap bilangan dapat difaktorkan menjadi bilangan prima, dan hal ini bisa menjadi sangat sulit apabila bilangannya sangat besar. Padahal fakta inilah yang menjadi dasar keamanan nasional. Banyak rahasia negara yang dienkripsi (seperti nomor kartu kredit dalam transaksi online) menggunakan skema yang hanya dapat dipecahkan jika faktor prima dari bilangan besar tertentu dapat ditemukan. Masalahnya, bilangan-bilangan itu sangat besar (terdiri dari beberapa ratus digit), dan untuk menemukan faktor-faktor primanya, bahkan menggunakan komputer canggih pun bisa memakan waktu puluhan tahun. Jadi, untuk saat ini, atau sampai ada orang yang bisa menemukan cara cepat untuk memfaktorkan bilangan sepeti itu menjadi bilangan prima, semua akan aman. Skema enkripsi ini merupakan penerapan bilangan prima yang menarik, dan kita akan membahasnya lebih lanjut di bagian ini.

Teorema berikutnya yang tidak kalah pentingnya, yaitu “Jika bilangan prima p habis membagi hasil kali ab, maka bilangan prima p harus membagi a atau b”. Anda mungkin berpikiran bahwa hal ini sudah jelas. Kita hanya memfaktorkan a dan b menjadi bilangan prima, dan jika p membagi hasil kali bilangan-bilangan prima itu, maka itu salah satunya. Masalah sebenarnya yaitu kemungkinan terdapat lebih dari satu cara memfaktorkan bilangan menjadi bilangan prima, dan salah satu diantaranya mungkin tidak melibatkan bilangan prima p. Ini merupakan masalah yang hampir tidak kelihatan, dan setelah kita bahas di akhir bagian nanti, kita akan mengetahui bukti teorema ini.

Perhatikan kata “prima” dalam teorema tersebut. Akan menjadi tidak benar hasilnya apabila kata “prima” itu dihilangkan. Sebagai contoh, 18 dapat difaktorkan menjadi 2 dan 9, dan bilangan komposit 6 habis membagi 2 x 9. Tetapi bilangan komposit 6 tidak habis membagi 2 atau 9.

Teorema tersebut sering digunakan dalam pembuktian. Sebagai contoh, jika diketahui bahwa 3 habis membagi beberapa bilangan (p² + 1)((q – 2) dan diketahui bilangan itu tidak habis membagi bilangan pertama p² + 1, maka bilangan itu harus membagi bilangan kedua q – 2, karena 3 meruakan bilangan prima.

Jika kita membuat daftar bilangan prima secara berurutan, kita miliki: 2, 3, 5, 7, 11, 13, 19, dan seterusnya, tampak tidak terdapat beda yang khusus diantara bilangan prima yang berurutan. Sebagai contoh, 2 dan 3 memiliki beda 1, 3 dan 5 memiliki beda 2, 5 dan 7 memiliki beda 2, 7 dan 11 memiliki beda 4. Hal yang wajar muncul pertanyaan, seberapa besar selisish atau beda antara dua bilangan prima berurutan? Mungkinkah beda antara dua bilangan prima berurutan 10.000? Dengan kata lain dapatkah kita menemukan 10.000 bilangan bulat berurutan yang merupakan bilangan komposit, atau harus prima dalam daftar 10.000 bilangan berurutan? Secara mengejutkan, jawabannya adalah kita dapat menemukan 10.000 bilangan berurutan yang merupakan bilangan komposit. Kenyataannya, hal itu dapat kita tunjukkan kepada Anda. Bilangan-bilangan itu adalah (10.001)! + 2, (10.001)! + 3, (10.001)! + 4 + ... + (10.001)! + 10.001. Ingat kembali bahwa 10.001! merupakan perkalian semua bilangan bulat dari 1 sampai 10.001. Kata kunci untuk membuktikan bahwa itu semua bilangan komposit adalah bahwa 10.001! habis dibagi berturut-turut oleh 2, 3, 4, dan seterusnya hingga 10.001. Sehingga, bilangan pertama, yaitu (10.001)! + 2 merupakan penjumlahan dua bilangan yang habis dibagi 2, oleh karenanya bilangan itu juga habis dibagi 2. Bilangan kedua, (10.001!) + 3 merupakan penjumlahan penjumlahan dua bilangan yang masing-masing habis dibagi 3, sehingga bilangan itu juga habis dibagi 3. Dengan cara yang sama, bilangan berikutnya merupakan penjumlahan dua bilangan yang masing-masing habis dibagi 4. Oleh karenanya bilangan itu juga habis dibagi 4. Demikian seterusnya, dan kita melihat bahwa masing-masing dari 10.000 bilangan dalam kumpulan bilangan tersebut merupakan bilangan komposit.

Teorema yang mendukung uraian terakhir yaitu “Jika N merupakan bilangan bulat positif, terdapat deretan N bilangan komposit berurutan”. Untuk membuktikannya, perhatikan N buah bilangan, (N + 1)! + 2, (N + 1)! + 3, (N + 1)! + 4, ..., (N + 1)! + (N + 1). Mengingat bahwa (N + 1)! dapat dibagi oleh semua bilangan bulat dari 2 hingga N + 1, dan dengan menggunakan argumentasi yang sama pada uraian sebelumnya, kita ketahui bahwa masing-masing merupakan  bilangan komposit. Artinya, bilangan pertama merupakan bilangan komposit karena merupakan penjumlahan dua bilangan yang masing-masing habis dibagi 2. Bilangan kedua merupakan bilangan komposit karena merupakan penjumlahan dua bilangan yang masing-masing habis dibagi 3, demikian seterusnya.

Dengan demikian, kita dapat menemukan satu juta, satu milyar, atau bahkan satu trilyun bilangan berurutan dengan tidak terdapat bilangan prima di dalamnya. Hal ini seperti menunjukkan bahwa bilangan prima menjadi semakin langka, dan mungkin hanya terdapat sejumlah bilangan prima yang terbatas. Dan bahkan jika banyak bilangan prima berhingga, bagaimana mungkin membuktikannya? Terdapat tak terhingga banyak bilangan prima, seperti kita ketahui, dan Euclid membuktikannya dengan cara berikut. Bukti ini tentu diperhitungkan sebagai salah satu dari bukti paling efisien, cerdik,dan elegan dalam matematika.

Menggunakan bukti dengan kontradiksi, andaikan banyak bilangan prima berhingga. Kita sebut bilangan-bilangan tersebut p₁, p₂, p₃, ..., p_L, dengan p_L merupakan bilangan prima terakhir. Selanjutnya bentuklah bilangan seperti berikut.

                              N = p₁.p₂.p₃...p_L + 1

Berdasarkan uraian sebelumnya kita tahu bahwa bilangan N dapat merupakan bilangan prima atau dapat difaktorkan menjadi bilangan prima, dan dalam kasus terakhir berarti memiliki faktor prima, p. Bilangan N tidak mungkin merupakan bilanga prima, karena lebih besar dari p_L yang merupakan bilangan prima terbesar. Jadi, haruslah N dapat difaktorkan menjadi bilangan prima yang memiliki faktor prima p. Tetapi p harus merupakan salah satu bilangan prima pada perkalian p₁.p₂.p₃...p_L karena ini kita andaikan sebagai daftar semua faktor prima. Dengan demikian, p₁.p₂.p₃...p_L habis dibagi p.

Selanjutnya, karena N habis dibagi p, demikian pula dengan p₁.p₂.p₃...p_L, maka selisihnya, yaitu N - p₁.p₂.p₃...p_L juga habis dibagi p. Tetapi dari N = p₁.p₂.p₃...p_L + 1 dapat kita ketahui bahwa N - p₁.p₂.p₃...p_L = 1. Ini berarti 1 habis dibagi p. Bagaimana ini bisa terjadi karena bilangan prima p lebih dari 1? Pengandaian bahwa banyak bilangan prima beringga mengakibatkan kontradiksi bahwa p harus membagi 1. Pengandaian salah, jadi haruslah banyak bilangan prima itu tak berhingga.

Sekarang kita kembali ke bukti teorema, bahwa “Jika bilangan prima p habis membagi hasil kali ab, maka bilangan prima p harus membagi a atau b”, yang kita janjikan di awal. Tetapi sebelumnya kita harus membuktikan sesuatu yang berkaitan. Tujuannya untuk menunjukkan bahwa ketika kita memfaktorkan sebuah bilangan prima, faktorisasinya adalah unik. Hal ini setara dengan “Jika terdapat bilangan terkecil N yang dapat difaktorkan menjadi bilangan prima dengan dua cara berbeda, maka bilangan prima apapun dalam faktorisasi N tidak akan terdapat pada faktorisasi N lainnya”.

Kita akan membuktikannya dengan kontradiksi. Ingat bahwa kita misalkan N mewakili bilangan terkecil yang dapat difaktorkan menjadi bilangan prima dengan dua cara berbeda. Misalkan dua cara pemfaktoran dari N adalah N = p₁p₂ ... p_n dan N = q₁q₂ ... q_k dan anggaplah kedua faktorisasi dari N itu memiliki faktor prima yang sama, yaitu p₁. Selanjutnya kita atur bilangan prima dalam faktorisasi N sedemikian hingga p₁ pada urutan pertama. Ini berarti, kita dapat mengasumsikan bahwa p₁ = q₁. Jadi, N = p₁p₂ ... p_n dan N = p₁q₂ ... q_k. Bagilah masing-masing dengan p₁ sehingga diperoleh N/p₁ = p₂ ... p_n dan N/p₁ = q₂ ... q_k. Ini menunjukkan bahwa bilangan N/p₁ dapat difaktorkan dengan dua cara berbeda, yaitu p₂ ... p_n dan q₂ ... q_k. Tetapi bilangan ini lebih kecil dari N, dan ini bertentangan dengan fakta bahwa N merupakan bilangan terkecil yang dapat difaktorkan dengan dua cara berbeda. Kontradiksi ini muncul akibat pengandaian bahwa N dapat difaktorkan dengan dua cara berbeda dengan faktor prima yang sama. Ini menunjukkan bahwa, jika terdapat bilangan terkecil yang dapat difaktorkan dengan dua cara berbeda, keduanya tidak dapat memiliki faktor yang sama.

Teorema berikutnya, bahwa “Sebarang bilangan asli yang lebih dari 1 dapat difatorkan menjadi bilangan prima hanya dengan satu cara (mengabaikan urutan penulisannya)”. Kembali kita gunakan kontradiksi dalam pembuktian ini, dan andaikan tidak demikian adanya. Ini berarti, terdapat beberapa bilangan asli yang tidak dapat difaktorkan hanya dengan satu cara. Sehingga harus ada bilangan asli terkecil yang tidak dapat difaktorkan menjadi bilangan prima hanya dengan satu cara, misalkan bilangan itu N. Berdasarkan uraian sebelumnya kita tahu bahwa N memiliki dua faktorisasi yang berbeda, yaitu misalkan N = p₁p₂ ... p_n dan N = q₁q₂ ... q_k dengan tidak ada p dan q yang sama. Dengan demikian p₁ ¹ q₁ dan misalkan p₁ < q₁. Kita akan membangun bilangan P yang lebih kecil dari N dengan dua faktorisasi berbeda, dan ini akan bertentangan dengan fakta bahwa N adalah bilangan terkecil.

Tetapkan P = (q₁ – p₁)q₂ ... q_k.

Pertama kita amati bahwa (q₁ – p₁) < q₁. Selanjutnya kalikan kedua ruas pertidaksamaan dengan q₂ ... q_k tuntuk memperoleh:

(q₁ – p₁)q₂ ... q_k < q₁q₂ ... q_k.

Karena (q₁ – p₁)q₂ ... q_k = P dan q₁q₂ ... q_k = N, maka kita peroleh P = N.

Sampai di sini kita telah menunjukkan bahwa P < N. Sekarang kita akan menunjukkan bahwa P memiliki dua faktorisasi yang berbeda.

Faktorisasi pertama dari P seperti dinyatakan sebelumnya, yaitu P = (q₁ – p₁)q₂ ... q_k. Semua faktor dari q merupakan bilangan prima dan tidak ada satupun diantaranya p₁, tetapi q₁ – p₁ mungkin bukan prima dan memiliki faktor p₁. Jika q₁ – p₁ memiliki faktor p₁, maka:

q₁ – p₁ = kp₁

untuk suatu bilangan k, dan dengan menyelesaikannya untuk q₁ diperoleh:

q₁ = kp₁ + p₁ = (k + 1)p₁.

Hal itu berarti q₁ merupakan kelipatan dari bilangan prima p₁. Tetapi ini merupakan hal yang tidak mungkin, karena q₁ merupakan bilangan prima yang hanya memiliki faktor 1 dan dirinya sendiri. Jadi, faktorisasi P = (q₁ – p₁)q₂ ... q_k tidak memuat p₁.

Selanjutnya kita cari faktorisasi P yang memuat p₁. Berdasarkan hal ini dan mengingat bahwa faktorisasi P = (q₁ – p₁)q₂ ... q_k tidak memuat p₁, akan memberikan kepada kita bahwa terdapat dua faktorisasi dari P yang merupakan kontradiksi yang kita cari. Kita mulai dengan menjabarkan persamaan,

P   = (q₁ – p₁)q₂ ... q_k

      = q₁q₂ ... q_k – p₁q₂ ... q_k

      = N – p₁q₂ ... q_k (di awal kita tahu bahwa N = q₁q₂ ... q_k)

      = p₁p₂ ... p_k – p₁q₂ ... q_k (p₁p₂ ... p_k merupakan faktorisasi lain dari N)

      = p₁(p₂ ... p_k – q₂ ... q_k)

Faktorisasi terakhir menunjukkan bahwa faktorisasi dari P memuat p₁.

Sekarang mari kita rangkum. Di awal kita ambil bilangan terkecil N yang tidak memiliki faktorisasi unik, dan menghasilkan bilangan P yang lebih kecil yang tidak memiliki faktorisasi unik. Salah satu faktorisasi dari P = p₁(p₂ ... p_k – q₂ ... q_k) memuat faktor p₁. Faktorisasi lainnya dari P = (q₁ – p₁)q₂ ... q_k tidak memuat faktor p₁. Ini bertentangan dengan fakta bahwa N merupakan bilangan terkecil yang tidak memiliki faktorisasi unik. Kontradiksi ini muncul akibat dari asumsi bahwa ada beberapa bilangan yang tidak memiliki faktorisasi unik. Jadi, asumsi salah, dan ini menunjukkan bahwa semua bilangan asli lebih dari 1 dapat difaktorkan menjadi bilangan prima dengan cara yang unik.

Salah satu contoh penggunaan teorema terakhir adalah pada soal berikut: “Tunjukkan bahwa ²log 3 irasional”. Kita lakukan pembuktian ini dengan kontradiksi. Misalkan ²log 3 rasional, sehingga ²log 3 = a/b dengan a dan b bilangan bulat positif. Ini berarti bahwa 2^a/b = 3 Selanjutnya pangkatkan kedua ruas dengan b untuk memperoleh 2^a = 3^b. Misalkan N = 2^a = 3^b. Ini berarti bilangan N dapat dinyatakan sebagai perkalian bilangan prima dengan dua cara berbeda. Faktorisasi pertama adalah perkalian dari 2, dan yang kedua adalah perkalian dari 3. Ini bertentangan dengan teorema 6, sehingga pengandaian bahwa ²log 3 rasional salah. Jadi, ²log 3 adalah irasional.

Alternatif bukti lainnya, yaitu bahwa pada persamaan 2^a = 3^b, kita melihat kontradiksi, karena ruas kiri persamaan merupakan bilangan genap, sedangkan ruas kanan merupakan bilangan ganjil.

Sekarang kita dapat membuktikan teorema bahwa “Jika bilangan prima p habis membagi hasil kali ab, maka bilangan prima p harus membagi a atau b”. Jika p habis membagi ab, maka pk = ab untuk suatu bilangan bulat k. Faktorkan kedua ruas persamaan itu menjadi bilangan prima. Karena hanya terdapat satu cara memfaktorkan suatu bilangan menjadi bilangan prima, dan p merupakan faktor pada ruas kiri persamaan, maka p juga harus merupakan faktor pada ruas kanan. Ini berarti, p harus merupakan faktor dari a atau b, dan selesailah pembuktian kita.

Jika a dan b merupakan bilangan positif yang tidak memiliki faktor prima yang sama, kita katakan a dan b relatif prima. Jadi, 8 = 2³ dan 27 = 3³ adalah relatif prima, karena keduanya tidak memiliki faktor prima yang sama. Hal yang sama berlaku untuk 18 dan 35 karena 18 = 2 x 3² dan 35 = 5 x 7. Jika bilangan rasional a/b dalam bentuk paling sederhana, maka a dan b relatif prima.

Teorema terakhir pada bagian ini, adalah “Jika a dan b relatif prima dan jika a membagi kb untuk suatu bilangan bulat k, maka a harus membagi k”. Jika a membagi kb, maka semua faktor prima dari a membagi kb. Tetapi karena a dan b tidak memiliki faktor persekutuan (relatif prima), maka semua faktor prima dari a harus membagi k. Dan jika semua faktor prima dari a membagi k, maka k memuat semua faktor prima dari a dan karena itu merupakan kelipatan dari a. Jadi, a membagi k.

 

Artikel diadaptasi dan dimodifikasi dari “Basics of Number Theory” dalam buku “The Mathematics That Every Secondary School  Math Teacher Needs To Know”, Second Edition, Alan Sutan dan Alice F., Routledge, 2018, halaman 41 – 46.