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.^[1]

Algarve tähistatakse tavaliselt sümbolitega ${\displaystyle p}$ ja ${\displaystyle q}$, vajaduse korral kasutatakse alaindekseid.

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

Vahetult on algarvude hulgaga ${\displaystyle \mathbb {P} }$ seotud kasvavalt järjestatud algarvude jada ${\displaystyle \left(p_{n}\right)_{n\in \mathbb {N} }}$. Seega

${\displaystyle \mathbb {N} \varsupsetneq \mathbb {P} =\{p_{n}\mid n\in \mathbb {N} \}}$,

kusjuures

${\displaystyle \left(p_{n}\right)_{n\in \mathbb {N} }=\left(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,\dotsc \right)}$ (jada A000040 OEIS'es).

IV sajandil eKr järeldas Vana-Kreeka matemaatik Eukleides loogiliselt, et leidub lõpmata palju algarve. Tõestuse viis Eukleides läbi vastuväiteliselt, oletades, et algarve on lõplik hulk ${\displaystyle p_{1},...,p_{n}}$ ja konstrueerides seejärel naturaalarvu ${\displaystyle a=p_{1}p_{2}...p_{n}+1}$. Nii konstrueeritud naturaalarv ei saa olla algarv, sest ei leidu suuremaid algarve kui ${\displaystyle p_{n}}$, seetõttu peab ta olema kordarv ja tal leidub algarvulisi jagajaid. Kui mingi algarv ${\displaystyle p_{i}}$ jagab arvu ${\displaystyle a}$ ja võrduse paremal poolel olevat algarvude korrutist, siis peab ta jagama ka arvu 1, mis ei ole aga võimalik, sest ${\displaystyle p_{i}>1}$. Vastuolu tekkis oletusest, et algarve on lõplik hulk.^[2] Tänapäeval tuntakse seda väidet Eukleidese teoreemina, millel on terve rida tuntud tõestusi.^[3]

Algarvude asukoht naturaalarvude reas tundub olevat juhuslik. Kaks algarvu 2 ja 3 on järjestikused naturaalarvud. Leidub ka üksteisele väga lähedal asuvaid algarve. Algarve kujul ${\displaystyle p}$ ja ${\displaystyle p+2}$ nimetatakse algarvukaksikuteks. Näiteks 29 ja 31 või 41 ja 43 (jada A001097 OEIS'es).

On tõestatud, et iga naturaalarvu ${\displaystyle n}$ korral leidub arvude ${\displaystyle n}$ ja ${\displaystyle 2n}$ vahel algarv.^[4]

Sümboliga ${\displaystyle \pi \left(n\right)}$ tähistatakse naturaalarvu ${\displaystyle n}$ mitteületavate algarvude arvu. Funktsiooni ${\displaystyle \pi \left(n\right)}$ nimetatakse algarvude jaotusfunktsiooniks.^[1] Väikeste argumentide korral saab funktsiooni ${\displaystyle \pi \left(n\right)}$ väärtusi leida peast: ${\displaystyle \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:

${\displaystyle \lim _{x\to \infty }{\frac {\pi (x)}{\frac {x}{\ln(x)}}}=1}$.^[3]

Ü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

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

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

Algarvude saamiseks on püütud leida ka valemeid. Näiteks Millsi valem^[6]

${\displaystyle \left\lfloor {A^{3^{n}}}\right\rfloor }$

või Wrighti valem^[7]

${\displaystyle \left\lfloor 2^{2^{2^{\cdot ^{\cdot ^{\cdot ^{2^{\alpha }}}}}}}\right\rfloor }$,

kus ${\displaystyle \left\lfloor x\right\rfloor }$ tähistab suurimat täisarvu, mis on väiksem kui ${\displaystyle x}$. Seni leitud valemeid ei loeta lihtsateks ja efektiivseteks.^[8]

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.^[9] 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 ${\displaystyle x=6=2\cdot 3=1\cdot 2\cdot 3=1^{2}\cdot 2\cdot 3=\ldots =1^{657}\cdot 2\cdot 3=\ldots }$.

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 ${\displaystyle p}$ puhul ${\displaystyle \varphi (p)=p-1}$. Ent ${\displaystyle \varphi (1)=1\neq 1-1=0}$. Kui 1 oleks algarv, tuleks see väide keerulisemalt sõnastada..

Artikli kirjutamine on selles kohas pooleli jäänud. Jätkamine on kõigile lahkesti lubatud.

• 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

Vikisõnastiku artikkel: algarv

• Citizendiumi artikkel