Secara umum, teori bilangan mengkaji sifat-sifat bilangan bulat positif. G.H. Hardy adalah matematikawan Inggris yang cemerlang. Ia mengalami kedua Perang Dunia dan melakukan banyak penelitian dalam teori bilangan. Ia juga seorang pasifis yang merasa senang karena, menurut pandangannya, penelitiannya tidak “berguna”. Dalam esainya tahun 1940, A Mathematician’s Apology, ia menulis bahwa “[b]elum ditemukan kegunaan teori bilangan atau relativitas bagi tujuan peperangan apa pun, dan tampaknya sangat kecil kemungkinan bahwa siapa pun akan menemukannya selama bertahun-tahun.” 1
G.H. Hardy, A Mathematician’s Apology, Cambridge University Press, hlm. 140. (cetakan 1993)
Ia tidak menyangka bahwa gagasan matematika paling murni dari teori bilangan segera menjadi sangat diperlukan bagi teknik kriptografi yang menjaga keamanan komunikasi. Bidang yang kita bahas di sini bukan teori bilangan, tetapi kita akan beberapa kali melihat bagaimana teknik kombinatorial digunakan dalam teori bilangan.
Bentuklah suatu barisan bilangan bulat positif dengan aturan berikut. Mulailah dengan bilangan bulat positif \(n>1\text{.}\) Jika \(n\) ganjil, suku berikutnya adalah \(3n+1\text{.}\) Jika \(n\) genap, suku berikutnya adalah \(n/2\text{.}\) Berhentilah jika Anda mencapai \(1\text{.}\) Sebagai contoh, jika kita mulai dengan \(28\text{,}\) barisannya adalah
Namun, bilangan bulat \(22\) juga muncul dalam barisan pertama, sehingga sejak titik ini kedua barisan akan sama. Barisan yang dibentuk dengan aturan ini disebut barisan Collatz.
Pilihlah suatu bilangan antara \(100\) dan \(200\text{,}\) lalu tuliskan barisan yang Anda peroleh. Apa pun pilihan Anda, proses tersebut pada akhirnya akan berhenti pada \(1\text{.}\) Namun, adakah bilangan bulat positif \(n\) (yang mungkin sangat besar) sedemikian sehingga jika kita mulai dari \(n\text{,}\) kita tidak pernah mencapai \(1\text{?}\)
Siswa sekolah menengah pertama diajari menjumlahkan pecahan dengan mencari kelipatan persekutuan terkecil (KPK). Sebagai contoh, kelipatan persekutuan terkecil dari \(15\) dan \(12\) adalah \(60\text{,}\) sehingga:
Hal itu sangat mudah jika kita dapat memfaktorkannya menjadi faktor-faktor prima. Sebagai contoh, perhatikan masalah mencari kelipatan persekutuan terkecil dari \(351785000\) dan \(316752027900\) jika kita kebetulan mengetahui bahwa
Jadi, untuk mencari kelipatan persekutuan terkecil dari dua bilangan, kita hanya perlu memfaktorkannya menjadi faktor-faktor prima. Kedengarannya tidak terlalu sulit. Sebagai permulaan, dapatkah Anda memfaktorkan \(1961\text{?}\) Baiklah, bagaimana dengan \(1348433\text{?}\) Sekarang mari kita coba tantangan yang sesungguhnya. Misalkan Anda diberi tahu bahwa bilangan bulat
\begin{align*}
c = \amp\,\, 5568490117077035708244283173335040521716369235589951150965\\
\amp\,\, 2043138898236817075547572153799
\end{align*}
merupakan hasil kali dua bilangan prima \(a\) dan \(b\text{.}\) Dapatkah Anda menemukan keduanya?
Bagaimana jika pemfaktoran ternyata sulit? Dapatkah Anda mencari kelipatan persekutuan terkecil dari dua bilangan bulat yang relatif besar, misalnya masing-masing memiliki sekitar \(500\) digit, dengan metode lain? Bagaimana seharusnya siswa sekolah menengah pertama diajari menjumlahkan pecahan?
Sebagai selingan, perhatikan bahwa kebanyakan kalkulator tidak dapat menjumlahkan atau mengalikan dua bilangan yang masing-masing terdiri atas \(20\) digit, apalagi dua bilangan dengan lebih dari \(500\) digit. Namun, menulis program komputer yang melakukan pekerjaan tersebut bagi kita relatif mudah. Tersedia pula beberapa perangkat lunak matematika yang canggih. Dua contoh komersial yang sangat terkenal ialah Maple® dan Mathematica®. Dalam buku ini, sesekali kita akan menggunakan sistem aljabar komputer sumber terbuka SageMath. Sesekali kami menyematkan sel SageMath interaktif di dalam buku, tetapi Anda juga dapat menggunakan SageMath secara gratis melalui CoCalc. Sebagai contoh, sel SageMath di bawah ini akan menghasilkan faktorisasi yang ditampilkan di atas.
Jika Anda membaca buku ini melalui peramban web, silakan ubah bilangan bulat dalam sel SageMath di atas menjadi bilangan bulat lain, mungkin yang lebih besar, lalu klik kembali tombolnya untuk memperoleh faktorisasi prima dari bilangan baru tersebut.
Berikut cara kami menyusun soal tantangan tersebut. Mula-mula, kami menemukan situs web yang memuat daftar bilangan prima besar dan memperoleh dua nilai berikut:
\begin{align*}
a \amp = 2425967623052370772757633156976982469681\quad\text{and}\\
b \amp = 22953686867719691230002707821868552601124472329079.
\end{align*}
Kode SageMath di bawah ini menghitung \(a\times b\) dan mengembalikan hasilnya seketika.
Di sisi lain, jika Anda meminta SageMath memfaktorkan \(c\text{,}\) seperti dalam sel di bawah ini, Anda mungkin harus menunggu lama. Jika Anda memperoleh jawaban dalam waktu dua menit atau kurang, silakan kirimkan email kepada kami agar kami dapat memperbarui buku ini dengan bilangan prima \(a\) dan \(b\) yang lebih besar!
Secara keseluruhan terdapat \(22\) partisi dan, sebagaimana ditandai, tepat \(6\) di antaranya merupakan partisi dari \(8\) menjadi bagian-bagian ganjil. Selain itu, tepat \(6\) di antaranya merupakan partisi dari \(8\) menjadi bagian-bagian berbeda.
Bagaimana reaksi Anda jika kami meminta Anda mencari banyaknya partisi bilangan bulat dari \(25892\text{?}\) Apakah menurut Anda banyaknya partisi dari \(25892\) menjadi bagian-bagian ganjil sama dengan banyaknya partisi dari \(25892\) menjadi bagian-bagian berbeda? Adakah cara untuk menjawab pertanyaan ini tanpa benar-benar menghitung banyaknya partisi dari setiap jenis?
