Algarv on teatud liiki loomulik arv. Täpsemalt: algarv on naturaalarv suurem kui 1, millel ei ole positiivseid jagajaid peale 1 ja iseenda. Arv, mis on võrdne kahe väiksema naturaalarvu korrutisega (välja arvatud 1 × ise), on liitarv ehk komposiitne arv. Näiteks väikseim liitarv on 4, sest 2 × 2 = 4. Arv 1 ei ole ei algarv ega liitarv; see on erandiks määratluses. Väikseim algarv on 2; järgnevad algarvud on 3, 5, 7, 11, 13 jne. Suurimat algarvu ei ole olemas — algarvud lõppevad lõpmatuseni.

Olulised omadused

  • Erandlikkus: 1 ei ole algarv.
  • Kahe olemasolu: 2 on ainus paarisarv, mis on algarv; kõik teised paarisarvud on liitarvud.
  • Faktoreerimine: iga naturaalarv > 1 on kas algarv või saab selle esitada algarvude korrutisena. See on fundamentaalne tulemus, mida nimetatakse algarvude teoreemiks (Fundamental Theorem of Arithmetic) — algarvude faktoriseerimine on ainulaadne kuni korrutuse järjekorra muutmise.
  • Lõpmatus: on olemas lõpmatu arv algarve; selle esimese elegantsi tõestuse andis Euclid juba antiikajal.

Kuidas kontrollida, kas arv on algarv?

Praktilisi meetodeid on mitu:

  • Proovijagamine (trial division): jagada arvu kõigi naturaalarvudega alates 2 kuni ruutjuureni (sqrt(n)). Kui ükski jagaja ei sobi, on arv algarv. See töötab hästi väikeste arvude puhul.
  • Seevad ja tabelid: Erinevad algoritmid nagu Eratosthene siif (Sieve of Eratosthenes) genereerivad kõik algarvud kuni antud piirini efektiivselt.
  • Prodbabilistlikud testid: suuremate arvude puhul kasutatakse kiiremaid probabilistlikke teste (nt Miller–Rabin), mis annavad suure tõenäosusega õige vastuse. Neid kasutatakse sageli esimese läviväravana enne deterministlikke kontrolle.
  • Deterministlikud testid: on olemas ka deterministlikud polünoomsed testid (nt AKS), mida kasutatakse teoreetiliselt ja mõnikord praktikas väga suurte arvude puhul.

Jaotus ja mustrid

Algarvude esinemine tundub alguses juhuslik, kuid neil on sügavaid aritmeetilisi mustreid. Näiteks algarvude tiheduse kasvab aeglaselt: primaarne tulemus on algarvude arv funktsioon π(x), mis hinnatakse suures piiris ligikaudu x / ln(x) (see on algarvude teooreem, inglise keeles Prime Number Theorem). Erinevad uurimused tegelevad täpsemate hinnangute, algarvude arvu ja jaotuse kõrvalekalletega.

Tuntud probleemid ja rakendused

  • Goldbachi oletus: üks kuulsamaid lahendamata probleeme: iga paarisarv ≥ 4 kas saab esitada kahe algarvu summana — see on veel tõestamata. Loe ka: Goldbachi oletus.
  • Kaksikalgardud: küsimus, kas leidub lõpmata palju paaris algarve (nt 11 ja 13), on endiselt avatud (kaksikalgarvude hulk).
  • Kryptograafia: algarve omadusi kasutatakse kaasaegses krüptograafias (nt RSA), kus suurte arvude faktoreerimise keerukus tagab turvalisuse.

Lihtsad näited

  • Algarvud kuni 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
  • Näide faktoreerimisest: 84 = 2 × 2 × 3 × 7 ehk 84 = 2^2 × 3 × 7 (siin on faktorid algarvud).
  • Euclidi lihtne tõestus algarvude lõpmatusest: kui eeldada, et algarvud on lõplik kogum p1, p2, ..., pn, siis konstrueeri N = p1·p2·...·pn + 1. N ei jagu ühegi pi järgi, seega N on algarv või omab algarvu, mis ei kuulu algupärasesse nimekirja — vastuolu.

Algarvud on matemaatika üks põhilisi ja huvitavamaid objekte: nende lihtne definitsioon peidab endas palju sügavaid küsimusi ja praktilisi rakendusi. Kui soovite, võin lisada rohkem näiteid, selgitada mõnda primality-testi samm-sammult või näidata, kuidas Eratosthene siifi praktikas kasutada.