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 (p2
+ 1)((q – 2) dan diketahui bilangan
itu tidak habis membagi bilangan pertama p2
+ 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 p1,
p2, p3, ..., pL,
dengan pL merupakan
bilangan prima terakhir. Selanjutnya bentuklah bilangan seperti berikut.
N
= p1.p2.p3...pL + 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 pL 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 p1.p2.p3...pL
karena ini kita andaikan sebagai daftar semua faktor prima. Dengan demikian, p1.p2.p3...pL habis dibagi p.
Selanjutnya, karena N habis dibagi p, demikian pula dengan p1.p2.p3...pL,
maka selisihnya, yaitu N - p1.p2.p3...pL juga habis dibagi p. Tetapi dari N = p1.p2.p3...pL
+ 1 dapat kita ketahui bahwa N - p1.p2.p3...pL = 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 = p1p2 ... pn dan N = q1q2 ... qk
dan anggaplah kedua faktorisasi dari N
itu memiliki faktor prima yang sama, yaitu p1.
Selanjutnya kita atur bilangan prima dalam faktorisasi N sedemikian hingga p1
pada urutan pertama. Ini berarti, kita dapat mengasumsikan bahwa p1 = q1. Jadi, N = p1p2 ... pn
dan N = p1q2
... qk. Bagilah
masing-masing dengan p1
sehingga diperoleh N/p1 = p2
... pn dan N/p1 = q2
... qk. Ini menunjukkan
bahwa bilangan N/p1 dapat difaktorkan dengan dua cara berbeda,
yaitu p2
... pn dan q2 ... qk. 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
= p1p2 ... pn
dan N = q1q2
... qk dengan tidak ada p dan q yang sama. Dengan demikian p1
¹ q1
dan misalkan p1 < q1. 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 = (q1
– p1)q2 ... qk.
Pertama kita amati bahwa (q1 – p1) < q1.
Selanjutnya kalikan kedua ruas pertidaksamaan dengan q2 ... qk
tuntuk memperoleh:
(q1 – p1)q2
... qk < q1q2 ... qk.
Karena (q1 – p1)q2
... qk = P dan q1q2
... qk = 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
= (q1 – p1)q2 ... qk.
Semua faktor dari q merupakan
bilangan prima dan tidak ada satupun diantaranya p1, tetapi q1
– p1 mungkin bukan prima
dan memiliki faktor p1.
Jika q1 – p1 memiliki faktor p1, maka:
q1 –
p1 = kp1
untuk suatu bilangan k, dan dengan menyelesaikannya untuk q1 diperoleh:
q1 =
kp1 + p1 = (k + 1)p1.
Hal itu berarti q1 merupakan kelipatan dari
bilangan prima p1. Tetapi
ini merupakan hal yang tidak mungkin, karena q1 merupakan bilangan prima yang hanya memiliki faktor 1
dan dirinya sendiri. Jadi, faktorisasi P
= (q1 – p1)q2 ... qk
tidak memuat p1.
Selanjutnya kita cari
faktorisasi P yang memuat p1. Berdasarkan hal ini dan
mengingat bahwa faktorisasi P = (q1 – p1)q2
... qk tidak memuat p1, akan memberikan kepada
kita bahwa terdapat dua faktorisasi dari P
yang merupakan kontradiksi yang kita cari. Kita mulai dengan menjabarkan
persamaan,
P =
(q1 – p1)q2
... qk
= q1q2 ... qk – p1q2 ... qk
= N
– p1q2 ... qk
(di awal kita tahu bahwa N = q1q2 ... qk)
= p1p2 ... pk – p1q2 ... qk (p1p2 ... pk merupakan faktorisasi lain dari N)
= p1(p2 ... pk – q2
... qk)
Faktorisasi
terakhir menunjukkan bahwa faktorisasi dari P
memuat p1.
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 = p1(p2 ... pk – q2
... qk) memuat faktor p1. Faktorisasi lainnya dari P = (q1
– p1)q2 ... qk
tidak memuat faktor p1.
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 2log 3 irasional”. Kita lakukan pembuktian ini dengan
kontradiksi. Misalkan 2log 3 rasional, sehingga 2log 3 = a/b dengan a
dan b bilangan bulat positif. Ini
berarti bahwa 2a/b = 3 Selanjutnya
pangkatkan kedua ruas dengan b untuk
memperoleh 2a
= 3b. Misalkan N = 2a
= 3b. 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 2log
3 rasional salah. Jadi, 2log 3 adalah irasional.
Alternatif
bukti lainnya, yaitu bahwa pada persamaan 2a
= 3b, 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 = 23 dan 27 = 33
adalah relatif prima, karena keduanya tidak memiliki faktor prima yang sama.
Hal yang sama berlaku untuk 18 dan 35 karena 18 = 2 x 32 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.