Algarv

Algarv (inglise keeles prime number) on naturaalarv, mis on suurem kui 1 ja jagub ainult arvuga 1 ja iseendaga.

Seega erinevad algarvud teistest naturaalarvudest selle poolest, et neil on täpselt kaks erinevat naturaalarvulist jagajat.

Ühest suuremaid naturaalarve, mis jaguvad peale ühe ja iseenda veel mõne naturaalarvuga, nimetatakse kordarvudeks. Arv 1 ei ole algarv ega kordarv.

Algarvulisi muutujaid tähistatakse tavaliselt tähtedega $p$ ja $q$, vajaduse korral kasutatakse alaindekseid.

Kõigi algarvude hulk on naturaalarvude hulga alamhulk. Seda tähistatakse tavaliselt sümboliga $\mathbb{P}$.

Kasvavalt järjestatud algarvude jada

${\left(p_n\right)}_{n\in \mathbb{N}}=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\dots )$ Mall:OEIS.

Algarvude omadused

Algarve iseloomustab naturaalarvude seas see, et neil on täpselt kaks naturaalarvulist [[jagaja]t.

Kõik algarvud peale arvu 2 on paaritud, sest kõik suuremad paarisarvud jaguvad peale iseenda ja 1 ka (vähemalt) arvuga 2. Seetõttu on igal algarvul peale arvu 2 kuju $2k+1$, kus $k$ on naturaalarv.

Igal algarvul $p\ne 2$ on üks kujudest $4k+1$ ja $4k+3$, kus $k$ on naturaalarv. Esimese $1000$ algarvu $p\ne 2$ seas on $495$-l kuju $4n+1$ ja $505$-l kuju $4n+3$. Kui jada jätkata, siis läheneb kummagi kuju osatähtsus väärtusele $0,5$.

Igal algarvul $p\ne 3$ on üks kujudest $3k+1$ või $3k+2$, kus $k$ on naturaalarv.

Igal algarvul $p>3$ on üks kujudest $p=6k+1$ või $p=6k-1$, kus $k$ on naturaalarv.

Iga algarv $p>5$ lõpeb ühega numbritest 1, 3, 7 või 9. Dirichlet' teoreemist tuleneb, et iga numbriga neist lõpeb lõpmata palju algarve.

Algarve on lõpmata palju

Mall:Vaata 4. sajandil eKr tõestas Vana-Kreeka matemaatik Eukleides, et leidub lõpmata palju algarve. Ta kasutas vastuväitelist tõestust. Tänapäeva mõistestikku ülekantuna oletas ta, et algarve on lõplik hulk$p_1,...,p_n,$ ja konstrueerides seejärel naturaalarvu $a=p_1{p}_2...p_n+1$. Nii konstrueeritud naturaalarv ei saa olla algarv, sest ei leidu suuremaid algarve kui $p_n$, seetõttu peab ta olema kordarv ja tal leidub algarvulisi jagajaid. Kui mingi algarv $p_i$ jagab arvu $a$ ja võrduse paremal poolel olevat algarvude korrutist, siis peab ta jagama ka arvu 1, mis ei ole aga võimalik, sest $p_i>1$. Vastuolu tekkis oletusest, et algarve on lõplik hulk. Tänapäeval tuntakse seda väidet Eukleidese teoreemina, millel on terve rida tuntud tõestusi.

Algarvude jaotumine

Algarvude asukoht naturaalarvude jadas tundub olevat juhuslik. Kaks algarvu 2 ja 3 on järjestikused naturaalarvud. Leidub ka üksteisele väga lähedal asuvaid algarve. Algarve kujul $p$ ja $p+2$ nimetatakse algarvukaksikuteks. Näiteks 29 ja 31 ning 41 ja 43 Mall:OEIS.

On tõestatud, et iga naturaalarvu $n$ korral leidub arvude $n$ ja $2n$ vahel algarv.

Sümboliga $\pi \left(n\right)$ tähistatakse naturaalarvu $n$ mitteületavate algarvude arvu. Funktsiooni $\pi \left(n\right)$ nimetatakse algarvude jaotusfunktsiooniks. Väikeste argumentide korral saab funktsiooni $\pi \left(n\right)$ väärtusi leida peast: $\pi \left(1\right)=0,\pi \left(2\right)=1,\pi \left(3\right)=2,...,\pi \left(10\right)=4,...$. Suurte arvude jaoks on saadud ligikaudne hinnang:

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x)}{\frac{x}{\ln (x)}}=1$.

Algarvude genereerimine

Eratosthenese sõel leiab naturaalarvude hulgast kõigepealt paarisarvud (punane), seejärel arvu 3 kordsed (roheline), arvu 5 kordsed (sinine) ja arvu 7 kordsed (kollane). Hallidele ruutudele jäänud arvud on väiksemad kui 11²=121 ja on seega algarvud.

Üks vanimaid algoritme algarvude tabeli koostamiseks on Vana-Kreeka matemaatiku Eratosthenese poolt III sajandil eKr loodud lihtne meetod, mida tuntakse Eratosthenese sõelana: kõik algarvud, välja arvatud arv 2, kuuluvad paaritute arvude hulka ja sisalduvad reas

$3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,\dots$

Iga kordarv on mingi algarvu kordne, seega tuleb arvureas maha tõmmata kõik algarvu 3 kordsed alates arvust $3^2$. Järgmine algarv on 5, nüüd saab maha tõmmata arvu 5 kordsed alates arvust $5^2$. Analoogiliselt toimitakse edasi. Kui algarvust $p$ väiksemate algarvude kordsed on maha tõmmatud, siis kõik allesjäänud arvud, mis on väiksemad kui $p^2$, on algarvud. Nii saab leida kõik algarvud vahemikus $1,\dots ,n$, kus $n$ on mingi etteantud naturaalarv.

Algarvude saamiseks on püütud leida ka valemeid. Näiteks Millsi valem

$\lfloor A^{3^n}\rfloor$

või Wrighti valem

$\lfloor 2^{2^{2^{{\cdot }^{{\cdot }^{{\cdot }^{2^{\alpha }}}}}}}\rfloor$,

kus $\lfloor x\rfloor$ tähistab suurimat täisarvu, mis on väiksem kui $x$. Seni leitud valemeid ei loeta lihtsateks ja efektiivseteks.

Miks 1 ei ole algarv

Algarvu definitsioon lähtub otstarbekusest.

Algarvu mõiste on matemaatika ajaloos muutunud. Näiteks arvas Godfrey Harold Hardy veel 1908. aastal arvu 1 algarvude hulka, kuid hiljemalt 1929. aastal enam mitte. Alates 20. sajandist arvu 1 tavaliselt algarvuks ei loeta.

Argument selle kasuks, et 1 peaks olema algarv:

• Definitsiooni „Algarvud jaguvad ainult iseendaga ja arvuga 1" järgi on igal algarvul ülimalt kaks jagajat. Arvu 1 puhul on jagajaid üks, teiste algarvude puhul kaks.

Selle kasuks, et 1 ei peaks olema algarv, räägivad järgmised argumendid:

• Igal algarvul on täpselt kaks jagajat (arv 1 ja see arv ise), mis tähendab, et need jagajad on eri arvud.
• Algteguriteks lahutamine on ühene. Kui 1 oleks algarv, siis saaks näiteks kordarvu 6 lahutada algteguriteks paljudel viisidel, näiteks $x=6=2\cdot 3=1\cdot 2\cdot 3=1^2\cdot 2\cdot 3=\dots =1^{657}\cdot 2\cdot 3=\dots$.

Sel juhul tuleks algteguriteks lahutamise ühesus sõnastada keerulisemalt.

• Kahe algarvu korrutis on alati kordarv. Arvu 1 le korrutis algarvuga on algarv. Kui 1 oleks algarv, peaks kordarvu swfinitsioon olema keerulisem.
• Eratosthenese sõel tuleks teisiti sõnastada, sest muidu jääks sõelale ainult arv 1.
• Euleri φ-funktsiooni väärtus on kõikide algarvude $p$ puhul $\phi (p)=p-1$. Ent $\phi (1)=1\ne 1-1=0$. Kui 1 oleks algarv, tuleks see väide keerulisemalt sõnastada..

Kirjandus

• Chris K. Caldwell, Angela Reddick, Yeng Xiong. The History of the Primality of One: A Selection of Sources – Journal of Integer Sequences, 2012, lk 1–40. Veebis

Välislingid

• Citizendiumi artikkel