Fototry ny Teorian'ny Isa
Sampan'ny matematika izay mandalina ny toetran'ny isa manontolo ny teôrian'ny isa. Na dia toa tsotra aza—satria ny isa manontolo dia ahitana fotsiny ny …, -2, -1, 0, 1, 2, …—ny teôrian'ny isa dia manana rafitra manankarena miavaka. Maro amin'ireo foto-kevitra manan-danja amin'ny matematika maoderina, ny cryptography, ary ny siansa informatika no miorim-paka amin'ny hevitra fototra momba ny teôrian'ny isa , toy ny fizarazarana, ny primeness, ary ny congruence. Ity lahatsoratra ity dia mandinika ireo fototra lehibe amin'ny teôrian'ny isa: ny fizarazarana sy ny algorithm an'i Euclid, ny isa voalohany sy ny factorization , ny modulo arithmetic, ary ny fampiharana sy ny torolàlana mandroso sasany.
1. Isa manontolo sy asa fototra
Amin'ny ankapobeny, ny teôrian'ny isa dia miasa amin'ny andiana isa manontolo, izay asehon'ny ℤ. Ny asa fototra ampiasaina dia ny fanampiana, ny fanalana ary ny fampitomboana. Tsy toy ny isa ara-drariny na tena izy, ny fizarana amin'ny isa manontolo dia tsy miteraka isa manontolo foana. Eto no mahatonga ny foto-kevitry ny fizarana amin'ny ambiny ho fototra.
Ny fifandraisana manan-danja iray amin'ny teôrian'ny isa dia ny fizarazarana. Ho an'ny isa manontolo \(a\) sy \(b\), dia manoratra \(a \mid b\) isika raha misy isa manontolo \(k\) ka \(b = ak\). Ohatra, \(3 \mid 12\) satria \(12 = 3 \in 4\), fa \(5 \nmid 12\) satria tsy misy isa manontolo \(k\) izay \(12 = 5k\).
Ny fizarazarana dia manana ireto toetra fototra manaraka ireto:
– Raha toa ka \(a \mid b\) sy \(a \mid c\), dia \(a \mid (b+c)\) sy \(a \mid (bc)\).
– Raha toa ka \(a \mid b\), dia ho an'ny isa manontolo \(k\) rehetra, \(a \mid (bk)\).
– Raha \(a \mid b\) sy \(b \mid c\), dia \(a \mid c\).
Ireo toetra tsotra ireo dia ampiasaina ho fitaovana hanaporofoana fanambarana maro momba ny isa manontolo.
2. Algôritma fizarana
Ny teôrema fizarana dia milaza hoe: ho an'ny isa manontolo \(a\) sy isa manontolo tsara \(b\), dia misy isa manontolo tokana \(q\) sy \(r\) toy izao manaraka izao:
\[
a = bq + r,\quad 0 \le r < b \] Eto ny \(q\) dia antsoina hoe quotient ary ny \(r\) dia antsoina hoe remais. Ohatra: raha \(a=29\) sy \(b=5\), dia \(29 = 5\cdot 5 + 4\), ka ny \(q=5\) sy \(r=4\. Zava-dehibe ity hevitra ity satria io no fototra Ny fandidiana modulo sy ny algorithm an'i Euclid mba hahitana ny GCD. 3. Mpizara iraisana lehibe indrindra (GCD) sy ny algorithm an'i Euclid Ho an'ny isa manontolo roa \(a\) sy \(b\) (tsy samy aotra), ny mpizara iraisana lehibe indrindra na GCD—izay aseho hoe \(\gcd(a,b)\)—no isa manontolo tsara lehibe indrindra izay mizara azy roa. Ny fomba mahomby indrindra hikajiana ny GCD dia ny algorithm an'i Euclid. Araka ny teôrema fizarana, raha: \[ a = bq + r \] dia: \[ \gcd(a,b) = \gcd(b,r) \] Averina ity dingana ity mandra-pahatongan'ny ambiny \(r\) ho 0. Amin'ny dingana farany, ny GCD no mpizara farany tsy aotra. Ohatra haingana: tadiavo \(\gcd(48,18)\). – \(48 = 18\cdot 2 + 12\) – \(18 = 12\cdot 1 + 6\) – \(12 = 6\cdot 2 + 0\) Dia \(\gcd(48,18)=6\). Tena zava-dehibe ny algorithman'i Euclid satria haingana na dia amin'ny isa maro aza, ka mahatonga azy io ho tena ilaina amin'ny kajy. 4. Fitambarana mitongilana sy ny maha-izy azy an'i Bézout Ny vokatra fototra iray dia ny maha-izy azy an'i Bézout: ho an'ny isa manontolo \(a\) sy \(b\) izay tsy samy aotra, dia misy isa manontolo \(x\) sy \(y\) toy izao: \[ \gcd(a,b) = ax + by \] Midika izany fa ny GCD dia azo soratana ho fitambarana mitongilana an'i \(a\) sy \(b\). Ny sandan'ny \(x\) sy \(y\) dia azo hita amin'ny algorithman'i Euclid mivelatra. Ny maha-izy an'i Bézout dia zava-dehibe amin'ny famahana: – ny fampitoviana Diophantine lineary \(ax+by=c\), – ny fitadiavana ny modulo inverse-ny (zava-dehibe amin'ny cryptography). 5. Isa voalohany sy ny factorization Ny isa voalohany dia isa manontolo tsara mihoatra ny 1 izay manana divisora tsara roa ihany: 1 sy ny tenany. Ny isa toy ny 2, 3, 5, 7, 11 dia isa voalohany. Ny isa lehibe kokoa noho ny 1 fa tsy isa voalohany dia antsoina hoe composite, ohatra 12, 21, 35. Ny hevitra malaza indrindra dia ny Theorem Fundamental of Arithmetic: ny isa manontolo rehetra \(n>1\) dia azo soratana amin'ny fomba tokana (arakaraka ny filaharany) ho vokatra avy amin'ny isa voalohany:
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
ohatra:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Io maha-tokana ny factorization io no fototry ny lohahevitra mandroso maro, anisan'izany ny RSA cryptography izay miantehitra amin'ny fahasarotan'ny factoring isa lehibe.
6. Fifanarahana sy aritmetika modulo
Ny Modulo arithmetic dia mandalina ny isa mifototra amin'ny ambin'ny fizarana. Hoy isika hoe:
\[
a \equiv b \pmod{m}
\]
Raha \(m \mid (ab)\), midika izany fa mitovy ny ambiny \(a\) sy \(b\) rehefa zaraina amin'ny \(m\).
Ohatra: \(17 \equiv 5 \pmod{12}\) satria ny \(17-5=12\) dia azo zaraina amin'ny 12. Ao amin'ny modulo 12, ny 17 sy 5 dia heverina ho mitovy.
Ny fifanandrifian-javatra dia manana toetra mitovy amin'ny asa mahazatra:
– Raha \(a \equiv b \pmod{m}\) sy \(c \equiv d \pmod{m}\), dia
\(a+c \equiv b+d \pmod{m}\) sy \(ac \equiv bd \pmod{m}\).
Tena ilaina amin'ny:
- mamaritra ny lamina miverimberina,
- jereo ireo maromaro,
- famolavolana algorithm informatika mahomby,
– ary ny fanafenana miafina maoderina.
7. Fifandanjana mifamadika sy mifanandrify Modulo
Manana modulo mivadika ny isa \(a\) raha misy isa \(x\) toy izao manaraka izao:
\[
ax \equiv 1 \pmod{m}
\]
Misy ity inverse ity raha toa ka \(\gcd(a,m)=1\ ary raha toa ka \(\gcd(a,m)=1\) ihany. Ohatra, ny 3 dia manana inverse modulo 7 satria \(3\cdot 5=15\equiv 1 \pmod{7}\), ka ny inverse-ny dia 5.
Ny foto-kevitry ny modulo inverse dia manamora ny famahana ny equations toy ny:
\[
ax \equiv b \pmod{m}
\]
Raha misy ny mifamadika amin'ny \(a^{-1}\), dia azo ny vahaolana amin'ny fampitomboana ny lafiny roa:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Ny teôrema kelin'i Fermat sy ny teôrema an'i Euler
Ireto misy valiny roa malaza amin'ny teoria isa fototra:
1. Teôrema Kely an'i Fermat: raha isa voalohany ny \(p\) ary tsy azo zaraina amin'ny \(p\ ny \(a\), dia:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Teôrema Euler (fanamafisana): raha \(\gcd(a,m)=1\), dia:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
izay \(\varphi(m)\) no fiasan'ny totien an'i Euler (ny isan'ny isa eo anelanelan'ny 1 sy \(m\) izay tena prima amin'ny \(m\)).
Ireo teôrema ireo no fototry ny fomba fanafenana isan-karazany sy ny teknika kajy modulo haingana.
9. Fampiharana sy torolàlana mandroso
Na dia fanontaniana tsotra momba ny isa manontolo aza no niandohany, dia lasa sehatra midadasika kokoa ankehitriny ny teôrian'ny isa. Ireto ny fampiharana azy:
– Kriptografia: Ny RSA, Diffie–Hellman, ary ny fiolahana eliptika dia mampiasa toetra prime, congruence, ary modulo inverse.
– Siansa informatika: hashing, mpamorona isa kisendrasendra, ary algorithm informatika isa be dia be.
– Kombinatorika sy teorian'ny kaody: fananganana kaody fanitsiana fahadisoana sy rafitra misaraka.
Ireo lohahevitra mandroso izay matetika ianarana aorian'ireo fototra ireo dia ahitana ny fampitoviana Diophantine tsy lineary, ny residues quadratic, ny teorian'ny isa algebraika, ary ny fizarana ny isa prime.
Penutup
Ny fototry ny teôrian'ny isa dia miorina amin'ny foto-kevitra momba ny fizarazarana, ny GCF, ny isa voalohany, ary ny fifanarahan-kevitra. Manomboka amin'ny algorithm an'i Euclid ka hatramin'ny aritmetika modulo, ny hevitra tsirairay dia mamorona fototra ho an'ny fahatakarana ny rafitry ny isa manontolo ary manokatra lalana ho an'ny fampiharana amin'izao tontolo izao, indrindra amin'ny vanim-potoana nomerika. Ny fahaizana mifehy ireo foto-kevitra fototra ireo dia manome fitaovana mahery vaika ho an'ny famakafakana olana matematika misaraka sy ny fidirana amin'ny lohahevitra lalindalina kokoa amin'ny teôrian'ny isa maoderina.
