Algteguriteks lahutus

Algteguriteks lahutus ehk lahutus algteguriteks on positiivse naturaalarvu $n\in \mathbb {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.

Arv	Tegurid üksikult	Tegurite arv	Tegurid kanooniliselt
1	–	0	–
2	$2$	1	$2$
3	$3$	1	$3$
4	$2\cdot 2$	2	$2^{2}$
5	$5$	1	$5$
6	$2\cdot 3$	2	$2\cdot 3$
7	$7$	1	$7$
8	$2\cdot 2\cdot 2$	3	$2^{3}$
9	$3\cdot 3$	2	$3^{2}$
10	$2\cdot 5$	2	$2\cdot 5$
11	$11$	1	$11$
12	$2\cdot 2\cdot 3$	3	$2^{2}\cdot 3$
13	$13$	1	$13$
14	$2\cdot 7$	2	$2\cdot 7$
15	$3\cdot 5$	2	$3\cdot 5$
16	$2\cdot 2\cdot 2\cdot 2$	4	$2^{4}$
17	$17$	1	$17$
18	$2\cdot 3\cdot 3$	3	$2\cdot 3^{2}$
19	$19$	1	$19$
20	$2\cdot 2\cdot 5$	3	$2^{2}\cdot 5$

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}<p_{k+1}$), 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 ${\textstyle 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 \mathbb {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

 Pikemalt artiklis 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 \mathbb {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 $\mathbb {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 \mathbb {N}$, nii et $a\cdot b=n$, kusjuures $1<a,b<n$. 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 \mathbb {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}}}<n$. 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.