Dasar-dasar Teori Bilangan
Teori bilangan adalah cabang matematika yang mempelajari sifat-sifat bilangan bulat. Meski tampak sederhana—karena bilangan bulat hanya mencakup …, -2, -1, 0, 1, 2, …—teori bilangan menyimpan struktur yang sangat kaya. Banyak konsep penting dalam matematika modern, kriptografi, dan ilmu komputer berakar dari gagasan-gagasan dasar teori bilangan, seperti pembagian, prima, dan kongruensi. Artikel ini mengulas fondasi utama teori bilangan: pembagian dan algoritma Euclid, bilangan prima dan faktorisasi, aritmetika modulo, serta beberapa aplikasi dan arah lanjutan.
1. Bilangan bulat dan operasi dasar
Teori bilangan umumnya bekerja di himpunan bilangan bulat, dilambangkan dengan ℤ . Operasi dasar yang digunakan ialah penjumlahan, pengurangan, dan perkalian. Berbeda dari bilangan rasional atau real, pembagian di bilangan bulat tidak selalu menghasilkan bilangan bulat. Di sinilah konsep pembagian dengan sisa menjadi sentral.
Salah satu relasi penting di teori bilangan adalah “habis membagi” atau divisibilitas. Untuk bilangan bulat \(a\) dan \(b\), kita menulis \(a \mid b\) jika ada bilangan bulat \(k\) sehingga \(b = ak\). Misalnya, \(3 \mid 12\) karena \(12 = 3 \times 4\), namun \(5 \nmid 12\) karena tidak ada bilangan bulat \(k\) dengan \(12 = 5k\).
Divisibilitas memiliki sifat-sifat dasar:
– Jika \(a \mid b\) dan \(a \mid c\), maka \(a \mid (b+c)\) dan \(a \mid (b-c)\).
– Jika \(a \mid b\), maka untuk setiap \(k\) bilangan bulat, \(a \mid (bk)\).
– Jika \(a \mid b\) dan \(b \mid c\), maka \(a \mid c\).
Sifat-sifat sederhana ini menjadi alat untuk membuktikan banyak pernyataan tentang bilangan bulat.
2. Algoritma pembagian
Teorema pembagian (division algorithm) menyatakan: untuk setiap bilangan bulat \(a\) dan bilangan bulat positif \(b\), terdapat bilangan bulat unik \(q\) dan \(r\) sehingga:
\[
a = bq + r,\quad 0 \le r < b
\]
Di sini \(q\) disebut hasil bagi (quotient) dan \(r\) disebut sisa (remainder). Contoh: jika \(a=29\) dan \(b=5\), maka \(29 = 5\cdot 5 + 4\), sehingga \(q=5\) dan \(r=4\).
Konsep ini penting karena menjadi dasar operasi modulo dan algoritma Euclid untuk mencari FPB.
3. Faktor persekutuan terbesar (FPB) dan algoritma Euclid
Untuk dua bilangan bulat \(a\) dan \(b\) (tidak keduanya nol), faktor persekutuan terbesar atau FPB —dilambangkan \(\gcd(a,b)\)—adalah bilangan bulat positif terbesar yang membagi keduanya.
Cara paling efisien untuk menghitung FPB adalah algoritma Euclid . Berdasarkan teorema pembagian, jika:
\[
a = bq + r
\]
maka:
\[
\gcd(a,b) = \gcd(b,r)
\]
Proses ini diulang sampai sisa \(r\) menjadi 0. Pada langkah terakhir, FPB adalah bilangan pembagi terakhir yang bukan nol.
Contoh cepat: cari \(\gcd(48,18)\).
- \(48 = 18\cdot 2 + 12\)
- \(18 = 12\cdot 1 + 6\)
- \(12 = 6\cdot 2 + 0\)
Maka \(\gcd(48,18)=6\).
Algoritma Euclid sangat penting karena cepat bahkan untuk bilangan besar, sehingga sangat berguna dalam komputasi.
4. Kombinasi linear dan identitas Bézout
Salah satu hasil fundamental adalah identitas Bézout : untuk bilangan bulat \(a\) dan \(b\) yang tidak keduanya nol, terdapat bilangan bulat \(x\) dan \(y\) sehingga:
\[
\gcd(a,b) = ax + by
\]
Artinya FPB dapat ditulis sebagai kombinasi linear dari \(a\) dan \(b\). Nilai \(x\) dan \(y\) dapat ditemukan dengan algoritma Euclid diperluas .
Identitas Bézout menjadi kunci dalam menyelesaikan:
- persamaan Diofantin linear \(ax+by=c\),
- mencari invers modulo (penting dalam kriptografi).
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Misalnya:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Keunikan faktorisasi ini adalah fondasi banyak topik lanjutan, termasuk kriptografi RSA yang bergantung pada kesulitan memfaktorkan bilangan besar.
6. Kongruensi dan aritmetika modulo
Aritmetika modulo mempelajari bilangan berdasarkan sisa pembagian. Kita mengatakan:
\[
a \equiv b \pmod{m}
\]
jika \(m \mid (a-b)\), artinya \(a\) dan \(b\) memiliki sisa yang sama ketika dibagi \(m\).
Contoh: \(17 \equiv 5 \pmod{12}\) karena \(17-5=12\) habis dibagi 12. Dalam modulo 12, 17 dan 5 dianggap setara.
Kongruensi memiliki sifat-sifat seperti operasi biasa:
– Jika \(a \equiv b \pmod{m}\) dan \(c \equiv d \pmod{m}\), maka
\(a+c \equiv b+d \pmod{m}\) dan \(ac \equiv bd \pmod{m}\).
Aritmetika modulo sangat berguna untuk:
– menentukan pola periodik,
– mengecek kelipatan,
– merancang algoritma komputasi yang efisien,
– serta kriptografi modern.
7. Invers modulo dan persamaan kongruensi
Bilangan \(a\) memiliki invers modulo \(m\) jika ada bilangan \(x\) sehingga:
\[
ax \equiv 1 \pmod{m}
\]
Invers ini ada jika dan hanya jika \(\gcd(a,m)=1\). Misalnya, 3 memiliki invers modulo 7 karena \(3\cdot 5=15\equiv 1 \pmod{7}\), jadi inversnya adalah 5.
Konsep invers modulo mempermudah penyelesaian persamaan seperti:
\[
ax \equiv b \pmod{m}
\]
Jika invers \(a^{-1}\) ada, maka solusi dapat diperoleh dengan mengalikan kedua sisi:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Teorema kecil Fermat dan teorema Euler
Dua hasil terkenal di teori bilangan elementer adalah:
1. Teorema Kecil Fermat : jika \(p\) prima dan \(a\) tidak habis dibagi \(p\), maka:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Teorema Euler (generalisasi): jika \(\gcd(a,m)=1\), maka:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
di mana \(\varphi(m)\) adalah fungsi totien Euler (jumlah bilangan antara 1 sampai \(m\) yang relatif prima terhadap \(m\)).
Teorema-teorema ini mendasari berbagai metode kriptografi dan teknik penghitungan modulo cepat.
9. Aplikasi dan arah lanjutan
Walau bermula dari pertanyaan sederhana tentang bilangan bulat, teori bilangan kini menjadi bidang yang luas. Aplikasinya mencakup:
– Kriptografi : RSA, Diffie–Hellman, dan kurva eliptik menggunakan sifat prima, kongruensi, dan invers modulo.
– Ilmu komputer : hashing, generator bilangan acak, dan algoritma komputasi bilangan besar.
– Kombinatorika dan coding theory : membangun kode koreksi kesalahan dan struktur diskret.
Topik lanjutan yang sering dipelajari setelah dasar-dasar ini meliputi persamaan Diofantin non-linear, residu kuadrat, teori bilangan aljabar, serta distribusi bilangan prima.
Penutup
Dasar-dasar teori bilangan bertumpu pada konsep pembagian, FPB, bilangan prima, dan kongruensi. Dari algoritma Euclid hingga aritmetika modulo, setiap ide membentuk fondasi untuk memahami struktur bilangan bulat sekaligus membuka jalan menuju aplikasi nyata, khususnya di era digital. Dengan menguasai konsep-konsep elementer ini, kita memiliki alat yang kuat untuk menganalisis masalah matematika diskret dan menyelami topik-topik yang lebih mendalam dalam teori bilangan modern.
