AlegsaOnline.com

Aritmeetika põhiteoreem: algarvude unikaalne faktoriseerimine

Aritmeetika põhiteoreem selgitab algarvude unikaalset faktoriseerimist: kuidas iga täisarv jaguneb priimideks ja miks see on kriitiline krüptograafias.

Autor: Leandro Alegsa Loomise kuupäev: 18. jaanuar 2022 Viimane uuendus: 3. november 2025

en.wikipedia.org · Public domain

Aritmeetika põhiteoreem (tuntud ka kui unikaalse faktoriseerimise teoreem) on arvuteooria oluline teoreem. See ütleb, et iga positiivne täisarv suurem kui 1 võib kirjutada algarvude korrutisena (või on ise algarv). Lisaks väidab teoreem, et see faktoriseerimine on ainulaadne ülesjärjestuse suhtes: kaks eri faktoriseerimist võivad erineda üksnes algarvude järjekorras.

Mida täpselt teoreem tähendab

- Algne väide: iga n > 1 on kas algarv või saab kirjutada kujul n = p1·p2·...·pk, kus p1,...,pk on algarvud.
- Unikaalsus: kui n = q1·q2·...·qm on teine faktoriseerimine algarvudest, siis k = m ja pärast algarvude ümberjärjestamist on pi = qi kõigi i jaoks.
- Märkus: arv 1 ei loeta algarvuks ega komposiidiks; tema faktoriseerimine loetakse tühjaks korrutiseks.

Lihtsad näited

6936 = 2³ × 3 × 17² või 1200 = 2⁴ × 3 × 5²

Kui keegi leiab näiliselt teise viisina kirjutada 6936 või 1200 algarvude korrutisena, siis saab algarvud õiges järjekorras panna ja näha, et need faktorisatsioonid kattuvad.

Lühikene tõestuse ülevaade

- Eksistentsi ideeks on tavaliselt tugeva induktsiooni kasutamine: kui n > 1 ja n pole algarv, siis jagub n mingi a-ga, kus 1 < a < n. Siis on b = n / a < n; eeldades, et kõik väiksemad arvud on faktoreeritavad algarvudeks, saab ka n-i faktoriseerida.
- Unikaalsuse võtmelemmaks on Euclidi lemma: kui algarv p jagab kahe arvude korrutist a·b, siis p jagab a-d või p jagab b-d. Sellele rajatud sammuga näidatakse, et kui on kaks erinevat faktoriseerimist, peab iga algarv ühest faktoriseerimisest leiduma ka teises; seega saab korrigeerida ja lõpuks jõuda identsete faktoriseerimisteni.

Rakendused ja tähendus

- Praktikas on teoreem aluseks paljudele arvuteooria ja krüptograafia meetoditele. Näiteks avaliku võtme krüptosüsteemid nagu RSA tuginevad sellele, et suurte arvude faktoriseerimine on arvutuslikult keeruline, kuigi faktorisatsioon ise on ainulaadne. (krüptograafias)
- Teoreem on oluline ka selliste mõistete arvutamisel nagu suurim ühine jagaja (GCD) ja väikseim ühine kordaja (LCM), samuti on see alguspunktiks üldisematele uurimustele algebralistes struktuurides (näiteks unikaalse faktoriseerimise puudumine mõnes algebrailises rõngas ja sellest tulenev ideede areng ideaalide suunas).

Märkused ja täpsustus

- Täpsus: unikaalsus tähendab «unikaalne ülesjärjestuse suhtes» — algarvude järjekord ei ole oluline.
- Algusajalugu: teoreemi elemendid on tuntud juba antiikajast (Euclid), formaalseks ja süsteemseks vormiks said nad hiljem, näiteks Gaussi töödes.
- Laiendused: algebrailises arvuteoorias uuritakse tingimusi, mille korral unikaalne faktoriseerimine kehtib ka muude elementide ja rõngaste puhul; mõnes kontekstis see ebaõnnestub ja tekib vajadus ideaalide ja muude üldistuste järele.

Primaarvude leidmist ja arvude faktoriseerimist nimetatakse faktoriseerimiseks, see on teoreemi praktiline pool ja ka paljude algoritmide uurimisvaldkond.

Tõend

Esimene inimene, kes tõestas teoreemi, oli Eukleidese. Esimene üksikasjalik ja korrektne tõestus oli Carl Friedrich Gaußi teoses "Disquisitiones Arithmeticae".

Mõned inimesed võivad arvata, et see teoreem kehtib kõikjal. Kuid teoreem ei ole tõene üldisemates arvusüsteemides, näiteks algebralistes täisarvudes. Esimest korda mainis seda Ernst Kummer 1843. aastal oma töös Fermat' viimase teoreemi kohta. Selle kohta rohkem teavet: loe algebraline arvuteooria.

Tõend koosneb kahest osast: esiteks näitame, et iga arvu saab kirjutada algarvude korrutisena; teiseks näitame, et kui me kirjutame arvu teist korda algarvude korrutisena, siis peavad kaks algarvude loendit olema samad.

Tõendi esimene osa

Näitame, et kui mitte iga arv, mis on suurem kui 1, ei ole võimalik kirjutada algarvude korrutisena, siis jõuame mingi võimatuse juurde. Nii et pärast seda järeldame, et peab olema tõsi, et iga arvu saab kirjutada algarvude korrutisena.

Nii et vaadake nüüd, mis juhtub, kui keegi ütleb, et ta teab positiivset täisarvu, mis on suurem kui 1 ja mida ei saa kirjutada algarvude korrutisena. Sellisel juhul palume tal nimetada kõik arvud, mis on suuremad kui 1 ja mida ei saa kirjutada algarvude korrutisena. Üks neist arvudest peab olema väikseim: nimetame seda n. Loomulikult ei saa see arv n olla 1. Veelgi enam, see ei saa olla algarv, sest algarv on ühe algarvu "produkt": tema ise. Seega peab see olema arvude korrutis. Seega -

n = ab

kus nii a kui ka b on positiivsed täisarvud, mis on muidugi väiksemad kui n. Aga: n oli väikseim arv, mida ei saa kirjutada algarvude korrutisena. Seega peab olema võimalik kirjutada a ja b algarvude produktidena, sest mõlemad on väiksemad kui n. Aga siis on toode

n = ab

saab kirjutada ka algarvude korrutisena. See on võimatu, sest me ütlesime, et n ei saa kirjutada algarvude korrutisena.

Oleme nüüd näidanud, et see on võimatu, kui teoreemi esimene osa ei oleks tõene. Sellega oleme nüüd tõestanud teoreemi esimese osa.

Tõendi teine osa

Nüüd peame tõestama, et on ainult üks võimalus kirjutada positiivset arvu, mis on suurem kui 1, algarvude korrutisena.

Selleks kasutame järgmist lemmat: kui algarv p jagab produkti ab, siis jagab ta kas a või b (Eukleidese lema). Kõigepealt tõestame nüüd seda lemmat. Oletame nüüd, et p ei jaga a. Siis on p ja a koopriimsed ja meil on Bezouti identiteet, mis ütleb, et peavad olema sellised täisarvud x ja y, et

px + ay = 1.

Korrutades kõike b-ga saadakse

pbx + aby = b,

Tuletame meelde, et ab võib olla jagatud p-ga. Seega on meil nüüd vasakul poolel kaks terminit, mis on jagatavad p-ga. Seega on ka paremal poolel olev termin jagatav p-ga. Oleme nüüd tõestanud, et kui p ei jaga a, siis peab ta jagama b. See tõestab lemmat.

Nüüd tõestame, et saame täisarvu, mis on suurem kui 1, kirjutada ainult ühel viisil algarvude korrutisena. Võtame kaks algarvude A ja B produkti, millel on sama tulemus. Seega teame produktide tulemuse kohta, et A = B. Võtame mis tahes algarvu p esimesest produktist A. See jagab A, seega jagab ta ka B. Kasutades mitu korda lemmat, mida me just tõestasime, näeme, et p peab siis jagama vähemalt ühe teguri b B-st. Kuid kõik tegurid on ise algarvud, seega ka b on algarv. Kuid me teame, et p on samuti primaarne, seega peab p olema võrdne b-ga. Seega jagame nüüd A-i p-ga ja jagame ka B-i p-ga. Ja saame tulemuse A* = B*. Jällegi võime võtta esimesest produktist A* priimuse p ja leida, et see on võrdne mingi arvuga produktis B*. Sel viisil jätkates näeme lõpuks, et kahe produkti algtegurid peavad olema täpselt samad. See tõestab, et me saame positiivset täisarvu kirjutada priimuste tootena ainult ühel ja ainuüksi viisil.

Küsimused ja vastused

K: Mis on aritmeetika põhiteoreem?

V: Aritmeetika põhiteoreem on arvuteooria teoreem, mis väidab, et iga positiivset täisarvu, mis on suurem kui 1, saab kirjutada algarvude korrutisena ja selle kirjutamiseks on ainult üks viis.

K: Kuidas saab seda teoreemi kasutada?

V: Seda teoreemi saab kasutada krüptograafias.

K: Mis juhtub, kui kaks inimest leiavad kaks erinevat viisi ühe ja sama arvu kirjutamiseks?

V: Kui kaks inimest leiavad kaks erinevat viisi ühe ja sama arvu kirjutamiseks, siis ainus asi, mis võib olla erinev, on järjekord, milles priimused on kirjutatud.

K: Mis on faktoriseerimine?

V: Faktoriseerimine on kõikide algarvude leidmine, mis moodustavad antud arvu.

K: Kas 6936 on näide algarvust?

V: Ei, 6936 ei ole algarv; seda võib kirjutada kui 23 - 3 - 172.

Ei, 6936 ei ole algarv; seda võib kirjutada kui 23 - 3 - 172.