Algteguriteks lahutus

**Algteguriteks lahutus** ehk **lahutus algteguriteks** on positiivse naturaalarvu n\in\N esitus algarvude p\in\mathbb P, korrutisena. Neid 
algarve nimetatakse siis arvu n algteguriteks. See esitus on ühene (kui mitte arvestada tegurite järjekorda; see on multihulk).

**Algteguriteks lahutamine** on üks arvuteooria põhilisi ja klassikalisi tööriistu. Seda käsitleb aritmeetika põhiteoreem. 

Seni ei ole teada efektiivset algteguriteks lahutamise meetodit mis tahes arvu jaoks.  

## Definitsioonid
Olgu n positiivne naturaalarv. Arvu p nimetatakse arvu n algteguriks,
* kui p on arvu n jagaja ja
* p on algarv.

Algteguriteks lahutus on arvu n esitus tema algtegurite korrutisena.  Et naturaalarvude korrutamine on kommutatiivne ja assotsiatiivne, on algtegurite järjekord arvuteooria seisukohast ebaoluline. Arvu 1 lahutust algteguriteks võib vaadelda tühja korrutisena.   Kui n ise on algarv, siis ta on ise ainuke algtegur.  Kui algtegureid on rohkem kui üks, siis nimetatakse arvu  n  kordarvuks. Üks algtegur võib korrutises esineda mitu korda ning seetõttu on algtegurite arvust rääkides tarvis täpsustada, kas jutt on erinevate algtegurite arvust või tegurite arvust kordsust arvestades. Korduvalt esinevad tegurid saab astmenäitajate abil kergesti loetavalt kokku võtta. Kui M erinevat algtegurit p_1, \dots, p_M on kasvavalt järjestatud (p_k ), siis räägitakse ka kanoonilisest algteguriteks lahutusest:
:n=p_1^{e_1} \cdot p_2^{e_2} \dotsm p_M^{e_M} = \prod_{k=1}^{M} p_k^{e_k}

Algteguri p_k astmenäitaja e_k on algteguri p_k  kordsus arvus n. Ta näitab, mitu korda n jagub arvuga p_k. Kordsust arvestades on arvul n siis N=e_1 + \dots + e_M=\sum_{k=1}^M e_k algtegurit.

Üks samaväärne kirjutusviis on :n = \prod_{p\in\mathbb P} p^{e_p}~,
kusjuures astmenäitajad e_p\in\N_0 on nullist erinevad ainult lõpliku arvu p\in\mathbb P korral.

## Algteguriteks lahutamise näiteid
:30 = 2 \cdot 3 \cdot 5
:37 = 37 \  (algarv)
:1001 = 7 \cdot 11 \cdot 13
:1024 = \underbrace {2 \cdots 2}_{\text{10 korda}} = 2^{10} (kahe aste)
:6936 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 17 \cdot 17, kanoonilisel kujul 2^3 \cdot 3 \cdot 17^2
:10000 = 2^4 \cdot 5^4  (kümne aste)

## Aritmeetika põhiteoreem

Väited algteguriteks lahutuse olemasolu kohta iga positiivse naturaalarvu korral ja selle ühesuse kohta kanoonilisel kujul on aritmeetika põhiteoreem. Kumbki väide formuleeritakse ja tõestatakse eraldi. Tõestused on elementaarsed, klassikaliselt formuleeritakse need vastuväitelistena ja need kasutavad naturaalarvude hulga täielikku järjestatust. Aritmeetika põhiteoreemi tõestas esimest korda täielikult ja korrektselt Carl Friedrich Gauß  teoses "Disquisitiones arithmeticae". Pisut teisel kujul oli see teoreem tuntud juba Eukleidesele.

### Olemasolu tõestus
Arvu 1\in\N kohta ei ole midagi tõestada. Iga algarv on ise enda lahutus algteguriteks. Jääb üle näidata, et ülejäänud naturaalarvude puhul on lahutus algteguriteks olemas. 

Oletame, et ülejäänud naturaalarvude seas on selliseid, mille korral algteguriteks lahutust ei eksisteeri. Et naturaalarvude hulk \N 
on täielikult järjestatud, siis on selliste arvude seas olemas vähim, nimelt n. Et  n>1 ei ole algarv, eksisteerivad arvul n  mittetriviaalsed jagajad  a,b \in \N, nii et a\cdot b=n, kusjuures 1 . Et n on vähim arv, mille puhul  algteguriteks lahutust ei ole olemas, siis eksisteerib arvu a korral (või vastavalt arvu b korral) algteguriteks lahutus a = \Pi p_i (või vastavalt b = \Pi q_j). Siis on \Pi p_i \cdot \Pi q_j arvu n algteguriteks lahutus, ja see on oletusega vastuolus.

### Ühesuse tõestus
Arvu 1\in\N ja algarvude puhul pole midagi näidata. Jääb näidata, et ülejäänud positiivsete naturaalarvude korral eksisteerib ülimalt üks lahutus algteguriteks. 

Oletame, et ülejäänud arvude seas eksisteerivad niisugused, millel eksisteerib mitu erinevat algarvudeks lahutust. Et naturaalarvude hulk on täielikult järjestatud, siis nende seas eksisteerib vähim niisugune arv n. Kui arvul n eksisteerib mitu erinevat algteguriteks lahutust, siis tal eksisteerib kaks erinevat algteguriteks lahutust \Pi_{i=1}^r p_i ja \Pi_{j=1}^s q_j. Peale selle, n ei ole algarv, järelikult r, s \geq 2.

Peale selle võib eeldada, et  \{p_1, \cdots, p_r\} \cap \{q_1, \cdots, q_s\} = \emptyset . Tõepoolest, kui mõni tegur oleks ühine, näiteks   p_1 = q_1, siis oleks \frac{n}{p_1} . Et n on vähim kahe erineva algteguriteks lahutusega arv, oleks \{p_2, \cdots, p_r\} = \{q_2, \cdots, q_s\}, nii et ülaltoodud algteguriteks lahutused oleksid identsed, ja see oleks vastuolus  arvu n valikuga.

Et p_1 jagab korrutist  n = \Pi q_j, siis Eukleidese lemma järgi jagab p_1 ka mõnd selle korrutise sobivalt valitud jagajat.  See ei saa olla mõni algteguritest  \{q_1, \cdots, q_s\}, sest muidu oleks p_1 \in \{q_1, \cdots, q_s\}. Järelikult jagab p_1 mõnd hulga \{q_1, \cdots, q_s\} s-1 erineva elemendi korrutist. Seda argumenti saa korrata, st p_1 jagab mõnd hulga \{q_1, \cdots, q_s\} s-2 erineva elemendi korrutist jne. Lõpuks peab  p_1 jagama mõnd hulga \{q_1, \cdots, q_s\} elementi. Et tegu on algarvudega, on seega p_1 \in \{ q_1, \cdots, q_s\}. See on vastuolu.

## Viited