Asas Teori Nombor
Teori nombor ialah cabang matematik yang mengkaji sifat-sifat integer. Walaupun kelihatan mudah—memandangkan integer hanya merangkumi …, -2, -1, 0, 1, 2, …—teori nombor mempunyai struktur yang sangat kaya. Banyak konsep penting dalam matematik moden, kriptografi dan sains komputer berakar umbi dalam idea asas teori nombor , seperti kebolehbahagian, keprimaan dan kekongruenan. Artikel ini mengulas asas utama teori nombor: kebolehbahagian dan algoritma Euclid, nombor perdana dan pemfaktoran , modulo aritmetik dan beberapa aplikasi dan arah lanjutan.
1. Nombor bulat dan operasi asas
Teori nombor secara amnya beroperasi pada set integer, yang dilambangkan dengan ℤ. Operasi asas yang digunakan ialah penambahan, penolakan dan pendaraban. Tidak seperti nombor nisbah atau nyata, pembahagian dengan integer tidak selalunya menghasilkan integer. Di sinilah konsep pembahagian dengan baki menjadi penting.
Satu hubungan penting dalam teori nombor ialah kebolehbahagian. Bagi integer \(a\) dan \(b\), kita menulis \(a \mid b\) jika terdapat integer \(k\) supaya \(b = ak\). Contohnya, \(3 \mid 12\) kerana \(12 = 3 \darab 4\), tetapi \(5 \nmid 12\) kerana tiada integer \(k\) yang mana \(12 = 5k\).
Kebolehbahagian mempunyai sifat asas berikut:
– Jika \(a \mid b\) dan \(a \mid c\), maka \(a \mid (b+c)\) dan \(a \mid (bc)\).
– Jika \(a \mid b\), maka bagi setiap integer \(k\), \(a \mid (bk)\).
– Jika \(a \mid b\) dan \(b \mid c\), maka \(a \mid c\).
Sifat-sifat mudah ini berfungsi sebagai alat untuk membuktikan banyak pernyataan tentang integer.
2. Algoritma pembahagian
Teorem pembahagian menyatakan: bagi setiap integer \(a\) dan integer positif \(b\), terdapat integer unik \(q\) dan \(r\) supaya:
\[
a = bq + r,\quad 0 \le r < b \] Di sini \(q\) dipanggil hasil bahagi dan \(r\) dipanggil baki. Contoh: jika \(a=29\) dan \(b=5\), maka \(29 = 5\cdot 5 + 4\), jadi \(q=5\) dan \(r=4\). Konsep ini penting kerana ia merupakan asas Operasi modulo dan algoritma Euclid untuk mencari GCD. 3. Pembahagi Sepunya Terbesar (GCD) dan algoritma Euclid Bagi dua integer \(a\) dan \(b\) (bukan kedua-duanya sifar), pembahagi sepunya terbesar atau GCD—dilambangkan \(\gcd(a,b)\)—ialah integer positif terbesar yang membahagikan kedua-duanya. Cara paling berkesan untuk mengira GCD ialah algoritma Euclid. Mengikut teorem bahagi, jika: \[ a = bq + r \] maka: \[ \gcd(a,b) = \gcd(b,r) \] Proses ini diulang sehingga baki \(r\) ialah 0. Dalam langkah terakhir, GCD ialah pembahagi bukan sifar terakhir. Contoh ringkas: cari \(\gcd(48,18)\). – \(48 = 18\cdot 2 + 12\) – \(18 = 12\cdot 1 + 6\) – \(12 = 6\cdot 2 + 0\) Kemudian \(\gcd(48,18)=6\). Algoritma Euclid sangat penting kerana ia pantas walaupun untuk nombor yang besar, menjadikannya sangat berguna dalam pengiraan. 4. Gabungan linear dan identiti Bézout Satu hasil asas ialah identiti Bézout: untuk integer \(a\) dan \(b\) yang kedua-duanya bukan sifar, terdapat integer \(x\) dan \(y\) supaya: \[ \gcd(a,b) = ax + by \] Ini bermakna GCD boleh ditulis sebagai gabungan linear \(a\) dan \(b\). Nilai \(x\) dan \(y\) boleh didapati dengan algoritma Euclid yang dilanjutkan. Identiti Bézout adalah kunci dalam menyelesaikan: – persamaan Diophantine linear \(ax+by=c\), – mencari songsangan modulonya (penting dalam kriptografi). 5. Nombor perdana dan pemfaktoran Nombor perdana ialah integer positif yang lebih besar daripada 1 yang hanya mempunyai dua pembahagi positif: 1 dan dirinya sendiri. Nombor seperti 2, 3, 5, 7, 11 adalah nombor perdana. Nombor yang lebih besar daripada 1 tetapi bukan nombor perdana dipanggil komposit, contohnya 12, 21, 35. Konsep yang paling terkenal ialah Teorem Asas Aritmetik: setiap integer \(n>1\) boleh ditulis secara unik (mengikut tertib) sebagai hasil darab nombor perdana:
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
contohnya:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Keunikan pemfaktoran ini merupakan asas kepada banyak topik lanjutan, termasuk kriptografi RSA yang bergantung pada kesukaran pemfaktoran nombor yang besar.
6. Kongruensi dan modulo aritmetik
Modulo aritmetik mengkaji nombor berdasarkan baki pembahagian. Kita katakan:
\[
a \equiv b \pmod{m}
\]
jika \(m \mid (ab)\), ia bermakna \(a\) dan \(b\) mempunyai baki yang sama apabila dibahagikan dengan \(m\).
Contoh: \(17 \equiv 5 \pmod{12}\) kerana \(17-5=12\) boleh dibahagi dengan 12. Dalam modulo 12, 17 dan 5 dianggap setara.
Kongruensi mempunyai sifat yang sama 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}\).
Aritmetik Modulo sangat berguna untuk:
– menentukan corak berkala,
– semak gandaan,
– mereka bentuk algoritma pengiraan yang cekap,
– dan kriptografi moden.
7. Persamaan songsang dan kongruen modulo
Suatu nombor \(a\) mempunyai modulo songsang \(m\) jika terdapat nombor \(x\) seperti berikut:
\[
kapak \equiv 1 \pmod{m}
\]
Songsangan ini wujud jika dan hanya jika \(\gcd(a,m)=1\). Contohnya, 3 mempunyai modulo songsang 7 kerana \(3\cdot 5=15\equiv 1 \pmod{7}\), jadi songsangannya ialah 5.
Konsep modulo songsang memudahkan penyelesaian persamaan seperti:
\[
ax \equiv b \pmod{m}
\]
Jika songsangan bagi \(a^{-1}\) wujud, maka penyelesaiannya boleh diperoleh dengan mendarabkan kedua-dua belah:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Teorem kecil Fermat dan teorem Euler
Dua hasil terkenal dalam teori nombor asas ialah:
1. Teorem Kecil Fermat: jika \(p\) ialah nombor perdana dan \(a\) tidak boleh dibahagi dengan \(p\), maka:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Teorem Euler (pengitlakan): jika \(\gcd(a,m)=1\), maka:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
di mana \(\varphi(m)\) ialah fungsi totien Euler (bilangan nombor antara 1 dan \(m\) yang relatifnya nombor perdana kepada \(m\)).
Teorem-teorem ini mendasari pelbagai kaedah kriptografi dan teknik pengiraan modulo pantas.
9. Aplikasi dan arahan lanjutan
Walaupun ia bermula sebagai soalan mudah tentang integer, teori nombor kini telah menjadi bidang yang luas. Aplikasinya termasuk:
– Kriptografi: RSA, Diffie–Hellman dan lengkung eliptik menggunakan sifat perdana, kongruen dan modulo songsang.
– Sains komputer: hashing, penjana nombor rawak dan algoritma pengkomputeran nombor besar.
– Kombinatorik dan teori pengekodan: membina kod pembetulan ralat dan struktur diskret.
Topik lanjutan yang sering dikaji selepas asas-asas ini termasuk persamaan Diofantin tak linear, residu kuadratik, teori nombor algebra dan taburan nombor perdana.
penutup
Asas teori nombor terletak pada konsep kebolehbahagi, FPB, nombor perdana dan kongruen. Daripada algoritma Euclid hingga aritmetik modulo, setiap idea membentuk asas untuk memahami struktur integer dan membuka jalan untuk aplikasi dunia sebenar, terutamanya dalam era digital. Menguasai konsep asas ini menyediakan alat yang berkuasa untuk menganalisis masalah matematik diskret dan mendalami topik yang lebih mendalam dalam teori nombor moden.
