Fa'avae o le Teori o Numera
O le teoria o numera o se lala o le matematika e suʻesuʻeina meatotino o numera atoa. E ui lava e foliga faigofie—talu ai o numera atoa e aofia ai …, -2, -1, 0, 1, 2, …—o le teoria o numera e iai se fausaga e matua mauoa lava. O le tele o manatu taua i le matematika faʻaonaponei, faʻailoga faalilolilo, ma le saienisi komepiuta e faʻavae i manatu autu o le teoria o numera , e pei o le vaevaeina, le primeness, ma le congruence. O lenei tusiga e iloiloina ai faavae autu o le teoria o numera: le vaevaeina ma le algorithm a Euclid, numera muamua ma le factorization , modulo arithmetic, ma nisi o faʻaoga ma faʻatonuga faʻapitoa.
1. Aofa'i atoa ma galuega fa'avae
E masani ona fa'agaoioia le teoria o numera i luga o le seti o numera atoa, e fa'ailoa mai e le ℤ. O galuega fa'avae e fa'aaogaina o le fa'aopoopoga, to'esega, ma le fa'atelega. E le pei o numera fa'atatau po'o numera moni, o le vaevaeina i numera atoa e le o taimi uma e i'u ai i se numera atoa. O iinei e avea ai le manatu o le vaevaeina ma le vaega totoe ma totonugalemu.
O se tasi o sootaga taua i le teoria o numera o le vaevaeina. Mo numera atoa \(a\) ma le \(b\), matou te tusia le \(a \mid b\) pe afai e iai se numera atoa \(k\) e pei o le \(b = ak\). Mo se faʻataʻitaʻiga, \(3 \mid 12\) ona \(12 = 3 \times 4\), ae \(5 \nmid 12\) ona e leai se numera atoa \(k\) e \(12 = 5k\).
O le vaevaeina e iai ona uiga autū nei:
– Afai o le \(a \mid b\) ma le \(a \mid c\), ona sosoo ai lea ma le \(a \mid (b+c)\) ma le \(a \mid (bc)\).
– Afai o le \(a \mid b\), ona mo numera atoa o \(k\), \(a \mid (bk)\).
– Afai o le \(a \mid b\) ma le \(b \mid c\), ona \(a \mid c\ lea).
O nei meatotino faigofie e fai ma meafaigaluega e faʻamaonia ai le tele o faʻamatalaga e uiga i numera atoa.
2. Algoritma o le vaevaega
O le teorama o le vaevaega e faapea: mo numera atoa \(a\) ma numera atoa lelei \(b\), e iai se numera atoa tulaga ese \(q\) ma le \(r\) e faapea:
\[
a = bq + r,\quad 0 \le r < b \] O iinei e ta'ua ai le \(q\) o le quotient ma le \(r\) e ta'ua o le remain. Fa'ata'ita'iga: afai o le \(a=29\) ma le \(b=5\), ona \(29 = 5\cdot 5 + 4\), ina ia \(q=5\) ma le \(r=4\). E tāua lenei manatu auā o le faavae lea fa'agaioiga modulo ma le algorithm a Euclid e su'e ai le GCD. 3. Vaevaega Lautele Sili (GCD) ma le algorithm a Euclid Mo numera atoa e lua \(a\) ma le \(b\) (e le o le zero uma), o le vaevaega lautele sili po'o le GCD—ua fa'ailoa mai o le \(\gcd(a,b)\)—o le numera atoa sili lea ona tele e vaevaeina uma. O le auala sili ona lelei e fuafua ai le GCD o le algorithm a Euclid. E tusa ai ma le teorama vaevaeina, afai: \[ a = bq + r \] ona: \[ \gcd(a,b) = \gcd(b,r) \] O lenei faiga e toe fai se'ia o'o ina 0 le vaega o totoe \(r\). I le la'asaga mulimuli, o le GCD o le vaevaega mulimuli e le o le zero. Fa'ata'ita'iga vave: su'e \(\gcd(48,18)\). – \(48 = 18\cdot 2 + 12\) – \(18 = 12\cdot 1 + 6\) – \(12 = 6\cdot 2 + 0\) Ona \(\gcd(48,18)=6\). E matuā tāua tele le algorithm a Euclid auā e vave e tusa lava pe tele ni numera, ma e matuā aogā ai i le fa’atusatusaga. 4. Tu’ufa’atasiga fa’asolosolo ma le fa’asinomaga o Bézout O se tasi o taunuuga autū o le fa’asinomaga o Bézout: mo numera atoa \(a\) ma le \(b\) e lē o ni zero uma, e iai numera atoa \(x\) ma le \(y\) e pei o lea: \[ \gcd(a,b) = ax + by \] O lona uiga e mafai ona tusia le GCD o se tu’ufa’atasiga fa’asolosolo o le \(a\) ma le \(b\). O tau o le \(x\) ma le \(y\) e mafai ona maua i le algorithm fa’alauteleina a Euclid. O le faasinomaga o Bézout e taua tele i le foiaina o: – le fua fa'atatau laina Diophantine \(ax+by=c\), – le sailia o lona modulo inverse (taua i le cryptography). 5. Numera muamua ma le factorization O se numera muamua o se numera atoa lelei e sili atu i le 1 e na'o le lua ona vaevaega lelei: 1 ma ia lava. O numera e pei o le 2, 3, 5, 7, 11 e muamua. O numera e sili atu i le 1 ae le o le muamua e ta'ua o le composite, mo se fa'ata'ita'iga 12, 21, 35. O le manatu sili ona lauiloa o le Fundamental Theorem of Arithmetic: o numera atoa \(n>1\) e mafai ona tusia tulaga ese (e tusa ai ma le fa'atonuga) o se oloa o numera muamua:
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Faamata:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
O lenei tulaga ese o le factorization o le faavae lea o le tele o mataupu maualuluga, e aofia ai le RSA cryptography lea e faalagolago i le faigata o le factoring o numera tetele.
6. Fa'atusatusaga ma le fa'asologa o numera
E suʻesuʻe e le Modulo arithmetic numera e faʻavae i luga o le vaega o totoe o le vaevaega. Matou te fai atu:
\[
a \equiv b \pmod{m}
\]
afai o le \(m \mid (ab)\), o lona uiga o le \(a\) ma le \(b\) e tutusa le vaega totoe pe a vaevaeina i le \(m\).
Fa'ata'ita'iga: \(17 \equiv 5 \pmod{12}\) auā e mafai ona vaevaeina le \(17-5=12\) i le 12. I le modulo 12, e manatu le 17 ma le 5 e tutusa.
E tutusa lava uiga o le tutusa ma galuega masani:
– Afai o le \(a \equiv b \pmod{m}\) ma le \(c \equiv d \pmod{m}\), ona
\(a+c \equiv b+d \pmod{m}\) ma le \(ac \equiv bd \pmod{m}\).
E matuā aogā tele le Modulo arithmetic mo:
– fuafua mamanu faavaitaimi,
– siaki ni fa'atelega,
– le mamanuina o algorithms fa'akomepiuta lelei,
– ma le fa'ailoga faalilolilo fa'aonaponei.
7. Fa'atusatusaga fa'afeagai ma le tutusa o modulo
O se numera \(a\) e iai le inverse modulo \(m\) pe afai e iai se numera \(x\) e faapea:
\[
ax \equiv 1 \pmod{m}
\]
E iai lenei fa'afeagai pe afai ma na'o le \(\gcd(a,m)=1\). Mo se fa'ata'ita'iga, o le 3 e iai le fa'afeagai modulo 7 ona o le \(3\cdot 5=15\equiv 1 \pmod{7}\), o lona fa'afeagai la o le 5.
O le manatu o le modulo inverse e faigofie ai ona foia ni fuafuaga e pei o:
\[
ax \equiv b \pmod{m}
\]
Afai e iai le fa'afeagai o le \(a^{-1}\), e mafai ona maua le tali e ala i le fa'ateleina o itu uma e lua:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. O le teorama laʻititi a Fermat ma le teorama a Euler
E lua taunuuga lauiloa i le a'oa'oga numera fa'avae:
1. Teorema Laʻititi a Fermat: afai o le \(p\) o le numera muamua ma e le mafai ona vaevaeina le \(a\) e le \(p\), ona:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Teorama a Euler (fa'alauteleina): afai \(\gcd(a,m)=1\), ona:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
lea o le \(\varphi(m)\) o le galuega faatino totien a Euler (le aofaʻi o numera i le va o le 1 ma le \(m\) e fai si numera muamua i le \(m\)).
O nei a'oa'oga fa'avae e fa'avae ai metotia eseese o fa'ailoga faalilolilo ma metotia fa'akomepiuta vave (modulo calculation).
9. Talosaga ma faʻatonuga faʻapitoa
E ui na amata mai o se fesili faigofie e uiga i numera atoa, ae ua avea nei le teoria o numera ma se matata lautele. O ona faʻaoga e aofia ai:
– Fa'ailoga Fa'alilolilo: O le RSA, Diffie–Hellman, ma le elliptic curves e fa'aogaina ai meatotino autū, tutusa, ma le modulo inverse.
– Saienisi komepiuta: hashing, generators random numbers, ma algorithms computing numera tele.
– Tu'ufa'atasiga ma le a'oa'oga o fa'ailoga numera: fausiaina o fa'ailoga fa'asa'o mea sese ma fausaga tu'ueseese.
O autu maualuluga e masani ona suʻesuʻeina pe a uma nei mea faavae e aofia ai faʻatusatusaga Diophantine e le o ni laina, toega o quadratic, le teoria o numera algebraic, ma le tufatufaina atu o numera autu.
Fa'ato'a
O faavae o le teoria o numera e faalagolago i manatu o le vaevaeina, GCF, numera autu, ma le tutusa. Mai le algorithm a Euclid i le modulo arithmetic, o manatu taitasi e fausia ai le faavae mo le malamalama i le fausaga o numera atoa ma saunia ai le ala mo talosaga i le lalolagi moni, aemaise lava i le vaitaimi numera. O le puleaina o nei manatu faavae e maua ai meafaigaluega malolosi mo le iloiloina o faafitauli o le matematika eseese ma le suʻesuʻeina o autu loloto i le teoria o numera i aso nei.
