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} } = \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)  .

## Algarvude omadused
Algarve iseloomustab naturaalarvude seas see, et neil on täpselt kaks naturaalarvulist jagajat.

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 \neq 2 on üks kujudest 4k+1 ja 4k+3, kus k on naturaalarv. Esimese 1000 algarvu p \neq 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 \neq 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

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 .

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:

\lim_{x \to \infty}\frac{\pi(x)}{\frac{x}{\ln(x)}} = 1.

## Algarvude genereerimine
Ü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,\ldots

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,\ldots,n, kus n on mingi etteantud naturaalarv.

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

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

või Wrighti valem

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

kus \left\lfloor x \right\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 = \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 definitsioon 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 \varphi(p) = p-1. Ent \varphi(1) = 1 \ne 1-1 = 0. Kui 1 oleks algarv, tuleks see väide keerulisemalt sõnastada..

## Viited

## 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