Algarv

Allikas: Vikipeedia
Jump to navigation Jump to search

Algarv (ingl prime number) on naturaalarv, mis on suurem kui 1 ja mis jagub ainult arvuga 1 või iseendaga. Seega eristuvad algarvud naturaalarvude hulgas seetõttu, et neil on täpselt kaks erinevat naturaalarvulist jagajat. Naturaalarve, mis peale ühe ja iseendaga jagumise jaguvad veel vähemalt mingi kolmanda naturaalarvuga, nimetatakse kordarvudeks. Arv 1 ei ole algarv ega kordarv.[1]

Algarvude hulk[muuda | muuda lähteteksti]

Algarve tähistatakse tavaliselt sümbolitega ja , vajadusel kasutatakse indekseid. Kõigist algarvudest koosnevat naturaalarvude hulga alamhulka tähistatakse tavaliselt sümboliga .

Vahetult on algarvude hulgaga seotud kasvavalt järjestatud algarvude jada . Seega

,

kusjuures

(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 ja konstrueerides seejärel naturaalarvu . Nii konstrueeritud naturaalarv ei saa olla algarv, sest ei leidu suuremaid algarve kui , seetõttu peab ta olema kordarv ja tal leidub algarvulisi jagajaid. Kui mingi algarv jagab arvu ja võrduse paremal poolel olevat algarvude korrutist, siis peab ta jagama ka arvu 1, mis ei ole aga võimalik, sest . 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 jaotumine[muuda | muuda lähteteksti]

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 ja nimetatakse algarvukaksikuteks. Näiteks 29 ja 31 või 41 ja 43 (jada A001097 OEIS'es).

On tõestatud, et iga naturaalarvu korral leidub arvude ja vahel algarv.[4]

Sümboliga tähistatakse naturaalarvu mitteületavate algarvude arvu. Funktsiooni nimetatakse algarvude jaotusfunktsiooniks.[1] Väikeste argumentide korral saab funktsiooni väärtusi leida peast: . Suurte arvude jaoks on saadud ligikaudne hinnang:

.[3]

Algarvude genereerimine[muuda | muuda lähteteksti]

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

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

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

või Wrighti valem[7]

,

kus tähistab suurimat täisarvu, mis on väiksem kui . Seni leitud valemeid ei loeta lihtsateks ja efektiivseteks.[8]

Viited[muuda | muuda lähteteksti]

  1. 1,0 1,1 Kivistik, L., Gabovitš, J. Arvuteooria. Tartu: TRÜ, 1974.
  2. Joyce, D. E. Euclid's Elements, Book IX, Proposition 20.
  3. 3,0 3,1 Hardy, G. H., Wright, E. M. An Introduction to the Theory of Numbers (5-th edition).Oxford: Clarendon Press, 1979.
  4. Landau, E. Handbuch der Lehre von der Verteilung der Primzahlen I. Leipzig: Verlag von B. G. Teubner, 1909.
  5. Horsley, S. KOΣ KINON EPATOΣ Θ ENOΥ Σ. or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S. Philosophical Transactions (1683-1775), vol. 62 (1772), lk 327-347.
  6. Mills, W. H. A Prime-Representing Function. Bulletin of the American Mathematical Society, vol. 53, nr 6 (1947), lk 604.
  7. Wright, E. M. A Prime-Representing Function. American Mathematical Monthly, vol. 58, nr 9 (1951), lk 616–618.
  8. Ribenboim, P. Are There Functions That Generate Prime Numbers? The College Mathematics Journal, vol. 28, nr 5 (1997), lk 352-359.

Välislingid[muuda | muuda lähteteksti]