Memahami hasil faktorisasi prima
Tabel di bawah menunjukkan faktorisasi prima dari beberapa bilangan yang familier untuk mengilustrasikan cara kerja notasi eksponen.
| Bilangan | Faktorisasi prima | Banyak pembagi |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (bilangan prima) | 17 (dirinya sendiri, eksponen 1) | 2 |
| 1.024 | 2¹⁰ | 11 |
- Faktorisasi bilangan prima itu sendiri hanyalah dirinya sendiri dengan eksponen 1, dan selalu memiliki tepat 2 pembagi: 1 dan dirinya sendiri. Ini justru merupakan sifat yang mendefinisikan bilangan prima.
- Bilangan 1 bukan prima maupun komposit dan tidak memiliki faktorisasi prima (bilangan ini adalah hasil kali kosong); kalkulator ini mensyaratkan input 2 atau lebih besar.
- Untuk bilangan yang sangat besar, pembagian percobaan menjadi lambat secara komputasi karena harus menguji kandidat bilangan prima hingga akar kuadrat bilangan tersebut — inilah alasan memfaktorkan bilangan yang sangat besar (ratusan digit) sulit secara komputasi dan menjadi dasar keamanan enkripsi RSA.
Apa itu faktorisasi prima?
Faktorisasi prima adalah proses menguraikan suatu bilangan bulat menjadi kumpulan bilangan prima yang jika dikalikan menghasilkan bilangan tersebut. Bilangan prima adalah bilangan bulat lebih besar dari 1 dengan tepat dua pembagi positif: 1 dan dirinya sendiri (2, 3, 5, 7, 11, 13, ... adalah beberapa bilangan prima pertama). Misalnya, 360 difaktorkan menjadi 2³ × 3² × 5, artinya 360 = 2×2×2×3×3×5.
Teorema dasar aritmetika, salah satu hasil terpenting dalam teori bilangan, menjamin bahwa setiap bilangan bulat lebih besar dari 1 memiliki satu dan hanya satu faktorisasi prima, terlepas dari urutan penulisan faktornya. Keunikan ini yang membuat faktorisasi prima menjadi operasi yang terdefinisi dengan baik dan dapat diandalkan, bukan salah satu dari beberapa jawaban yang sama-sama sah.
Faktorisasi prima mendasari bidang-bidang inti matematika dan ilmu komputer: digunakan untuk menemukan faktor persekutuan terbesar dan kelipatan persekutuan terkecil dari bilangan-bilangan, untuk menentukan semua pembagi suatu bilangan, untuk menyederhanakan pecahan dan bentuk akar, dan — untuk bilangan yang sangat besar — kesulitan komputasinya menjadi dasar matematis kriptografi kunci publik RSA, yang mengandalkan fakta bahwa memfaktorkan bilangan besar jauh lebih sulit daripada mengalikan faktor-faktornya.
Cara menggunakan kalkulator faktorisasi prima ini
- Masukkan bilangan bulat 2 atau lebih besar (hingga 1 triliun).
- Kalkulator membagi berulang kali dengan faktor prima terkecil yang mungkin hingga hanya tersisa 1, mengikuti metode pembagian percobaan standar.
- Baca faktorisasi prima dalam bentuk eksponen (misalnya 2³ × 3² × 5), di mana setiap eksponen menunjukkan berapa kali bilangan prima tersebut muncul dalam hasil kali.
- Tinjau total banyak pembagi positif yang dimiliki bilangan tersebut, dan jumlah semua pembagi itu — keduanya diturunkan langsung dari faktorisasi prima.
Cara menghitung faktorisasi prima, banyak pembagi dan jumlah pembagi
Pembagian percobaan menemukan faktorisasi prima dengan menguji kandidat bilangan prima berurutan, dimulai dari 2, membagi bilangan tersebut dengan setiap prima sebanyak mungkin selama masih habis dibagi, lalu berpindah ke kandidat berikutnya. Contoh perhitungan: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45 (tidak lagi habis dibagi 2, jadi 2 muncul 3 kali); 45 ÷ 3 = 15, ÷3 = 5 (tidak lagi habis dibagi 3, jadi 3 muncul 2 kali); 5 ÷ 5 = 1 (5 muncul sekali). Hasil: 360 = 2³ × 3² × 5.
Setelah faktorisasi prima n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ diketahui, total banyak pembagi positif (termasuk 1 dan n itu sendiri) ditemukan dengan menambahkan 1 ke setiap eksponen dan mengalikan hasilnya: (e₁+1) × (e₂+1) × ... × (eₖ+1). Contoh perhitungan untuk 360 = 2³ × 3² × 5¹: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 pembagi.
Jumlah semua pembagi ditemukan menggunakan rumus jumlah-pembagi yang bersifat multiplikatif: untuk setiap pangkat prima p^e dalam faktorisasi, kontribusinya adalah (p^(e+1) − 1) ÷ (p − 1) — jumlah deret geometri 1 + p + p² + ... + p^e — dan kontribusi-kontribusi ini dikalikan bersama di semua faktor prima. Contoh perhitungan untuk 360: suku 2³ berkontribusi (2⁴−1)/(2−1) = 15, suku 3² berkontribusi (3³−1)/(3−1) = 13, dan suku 5¹ berkontribusi (5²−1)/(5−1) = 6; mengalikan 15 × 13 × 6 = 1.170, jumlah dari semua 24 pembagi 360.
Kesalahan umum
- Menghentikan faktorisasi terlalu dini sebelum mencapai 1 — setiap faktor yang ditemukan harus dibagi habis sepenuhnya (bukan hanya sekali) sebelum berpindah ke kandidat bilangan prima berikutnya.
- Memperlakukan 1 sebagai bilangan prima — menurut konvensi matematika modern, 1 bukan prima maupun komposit, dan menyertakannya dalam faktorisasi akan melanggar keunikan yang dijamin oleh teorema dasar aritmetika.
- Lupa bahwa eksponen (bukan hanya bilangan prima dasarnya) penting untuk menghitung banyak pembagi — rumus banyak pembagi menggunakan (eksponen + 1) untuk setiap bilangan prima, bukan hanya jumlah bilangan prima yang berbeda.
- Mengasumsikan setiap bilangan besar memiliki faktor prima kecil — banyak bilangan besar (terutama hasil kali dua bilangan prima besar) sama sekali tidak memiliki faktor kecil, yang justru merupakan sifat yang membuatnya berguna untuk aplikasi kriptografi.
Pertanyaan yang sering diajukan
Bagaimana cara menemukan faktorisasi prima suatu bilangan?
Bagi bilangan tersebut berulang kali dengan bilangan prima terkecil yang membaginya habis, lanjutkan dengan bilangan prima yang sama hingga tidak lagi habis dibagi, lalu pindah ke bilangan prima berikutnya, dan ulangi hingga hasil bagi yang tersisa adalah 1. Untuk 360: bagi dengan 2 tiga kali (360→180→90→45), lalu dengan 3 dua kali (45→15→5), lalu dengan 5 sekali (5→1), menghasilkan 360 = 2³ × 3² × 5.
Berapa banyak pembagi yang dimiliki suatu bilangan?
Tambahkan 1 ke setiap eksponen dalam faktorisasi prima dan kalikan hasilnya. Untuk 360 = 2³ × 3² × 5¹, banyak pembaginya adalah (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. Ini menghitung semua pembagi positif, termasuk 1 dan bilangan itu sendiri.
Apa itu teorema dasar aritmetika?
Teorema dasar aritmetika menyatakan bahwa setiap bilangan bulat lebih besar dari 1 dapat ditulis sebagai hasil kali bilangan prima dengan tepat satu cara, terlepas dari urutan penulisan bilangan primanya. Keunikan ini yang membuat faktorisasi prima menjadi operasi yang terdefinisi dengan baik, bukan salah satu dari beberapa jawaban yang sama-sama sah, dan mendasari banyak bagian teori bilangan.
Apakah 1 adalah bilangan prima?
Tidak. Menurut konvensi matematika modern, 1 bukan prima maupun komposit. Bilangan prima didefinisikan sebagai memiliki tepat dua pembagi positif berbeda (1 dan dirinya sendiri); bilangan 1 hanya memiliki satu pembagi positif (dirinya sendiri), sehingga tidak memenuhi definisi tersebut. Mengecualikan 1 dari bilangan prima juga diperlukan agar teorema dasar aritmetika berlaku, karena jika tidak, suatu bilangan bisa 'difaktorkan' dengan sejumlah faktor 1 tambahan mana pun.
Mengapa faktorisasi prima penting untuk enkripsi?
Kriptografi kunci publik RSA modern mengandalkan fakta bahwa mengalikan dua bilangan prima besar itu mudah secara komputasi, tetapi memfaktorkan kembali hasil kalinya yang besar menjadi bilangan prima aslinya sangat sulit secara komputasi menggunakan algoritma klasik yang dikenal saat ini. Asimetri ini — mudah mengalikan, sulit memfaktorkan — memungkinkan kunci publik (hasil kali) dibagikan secara terbuka sementara kunci privat (faktor prima) tetap rahasia dan secara efektif tidak dapat dipulihkan dalam kerangka waktu praktis untuk bilangan prima yang cukup besar.
Bagaimana cara menemukan jumlah semua pembagi suatu bilangan?
Menggunakan faktorisasi prima n = p₁^e₁ × p₂^e₂ × ..., hitung (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1) untuk setiap faktor prima dan kalikan hasilnya. Untuk 360 = 2³ × 3² × 5: suku 2³ memberikan (2⁴−1)/(2−1)=15, suku 3² memberikan (3³−1)/(3−1)=13, dan suku 5¹ memberikan (5²−1)/(5−1)=6; mengalikan 15×13×6 = 1.170, jumlah semua pembagi 360.
Referensi
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)