Mis on algarv? Määratlus, omadused ja näited
Loe, mis on algarv: määratlus, omadused ja näited ning tähtsamad teoreemid (nt Goldbachi oletus, algarvude jaotus). Selged selgitused ja praktilised näited.
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.
Siin on veel üks viis, kuidas mõelda algarvudest. Arv 12 ei ole primaarne, sest sellest saab moodustada ristküliku, mille küljed on pikkusega 4 ja 3. Selle ristküliku pindala on 12, sest kõik 12 klotsi on kasutatud. Seda ei saa teha 11-ga. Ükskõik, kuidas ristkülikut ka ei kujundataks, jääb alati klotsid üle, välja arvatud ristkülik, mille küljed on pikkusega 11 ja 1. 11 peab seega olema algarv.
Kuidas leida väikeseid algarvusid
On olemas lihtne meetod algarvude loendi leidmiseks. Selle lõi Eratosthenes. Selle nimi on Eratosthenese sõel. See püüab üles numbrid, mis ei ole algarvud (nagu sõel) ja laseb algarvud läbi.
Meetod töötab numbrite loeteluga ja spetsiaalse numbriga b, mis muutub meetodi käigus. Meetodi läbimise ajal ringitad mõned numbrid nimekirjas sisse ja kriipsutad teised välja. Iga sissepiiratud arv on algarv ja iga läbi kriipsutatud arv on liitarv. Alguses on kõik arvud tavalised: neid ei ole sisse- ega välja kriipsutatud.
Meetod on alati sama:
- Kirjutage paberilehele kõik täisarvud alates 2-st kuni katsetatava arvuni. Ärge kirjutage üles arvu 1. Minge järgmise sammu juurde.
- Alusta, kui b on võrdne 2. Mine järgmise sammu juurde.
- Ümbritsege nimekirjas b. Minge järgmise sammu juurde.
- Alustades b-st, loe loetelus veel b ülespoole ja kriipsuta see number läbi. Korda veel b numbri üleslugemist ja numbrite ülestähendamist kuni nimekirja lõpuni. Minge järgmise sammu juurde.
- (Näiteks: Kui b on 2, siis ümmardate 2 ja kriipsutate läbi 4, 6, 8 jne. Kui b on 3, siis ümmardate 3 ja kriipsutate läbi 6, 9, 12 jne. 6 ja 12 on juba läbi kriipsutatud. Ristige need uuesti läbi).
- Suurendage b 1 võrra. Jätkake järgmise sammuga.
- Kui b on läbi kriipsutatud, minge tagasi eelmise sammu juurde. Kui b on nimekirjas olev number, mida ei ole läbi kriipsutatud, liigu 3. sammu juurde. Kui b ei ole nimekirjas, minge viimase sammu juurde.
- (See on viimane samm.) Te olete valmis. Kõik algarvud on sissejoonitud ja kõik liitarvud on läbi kriipsutatud.
Näiteks võiksite seda meetodit kasutada numbrite 2-10 nimekirja puhul. Lõpuks jäävad numbrid 2, 3, 5 ja 7 ringiga ümbritsetud. Need on algarvud. 4, 6, 8, 9 ja 10 kriipsutatakse läbi. Need on liitarvud.
See meetod või algoritm võtab väga suurte algarvude leidmiseks liiga kaua aega. Kuid see on vähem keeruline kui meetodid, mida kasutatakse väga suurte algarvude puhul, nagu Fermat' algarvukatsetus (test, millega saab kindlaks teha, kas arv on algarv või mitte) või Miller-Rabini algarvukatsetus.
Milleks kasutatakse algarvu
Primaarvud on matemaatikas ja arvutiteaduses väga olulised. Allpool on toodud mõned reaalmaailma kasutusalad. Väga pikad arvud on raskesti lahendatavad. Nende algtegureid on raske leida, mistõttu enamasti kasutatakse krüpteerimiseks ja salakoodide koostamiseks arvatavasti algtegureid sisaldavaid numbreid.
- Enamikul inimestel on pangakaart, millega nad saavad oma kontolt raha kätte, kasutades selleks pangaautomaati. See kaart on kaitstud salajase juurdepääsukoodiga. Kuna koodi tuleb hoida salajas, ei saa seda kaardi peal hoida selge tekstina. Koodi salajaseks salvestamiseks kasutatakse krüpteerimist. Krüpteerimisel kasutatakse korrutamisi, jagamisi ja suurte algarvude jääkide leidmist. Praktikas kasutatakse sageli algoritmi nimega RSA. See kasutab Hiina jäägi teoreemi.
- Kui kellelgi on oma e-kirjale digitaalallkiri, kasutatakse krüpteerimist. See tagab, et keegi ei saa võltsida nende saadetud e-kirja. Enne allkirjastamist luuakse sõnumi hash-väärtus. Seejärel kombineeritakse see digitaalallkirjaga, et saada allkirjastatud sõnum. Kasutatavad meetodid on enam-vähem samad, mis esimesel juhul eespool.
- Suurima seni teadaoleva prime'i leidmine on muutunud omamoodi spordialaks. Kui arv on suur, võib selle kontrollimine, kas see on priimus, olla keeruline. Suurimad praegu teadaolevad arvud on tavaliselt Mersenne'i arvud, sest kõige kiirem teadaolev arvude primaarsuse test on Lucas-Lehmeri test, mis põhineb Mersenne'i arvude erivormil. Mersenne'i pritsmeid otsiv rühm on siin[1].
Küsimused ja vastused
K: Mis on algarv?
V: Algarv on naturaalarv, mida ei saa jagada ühegi teise naturaalarvuga, välja arvatud 1 ja iseendaga.
K: Mis on väikseim liitarv?
V: Väikseim liitarv on 4, sest 2 x 2 = 4.
K: Millised on järgmised algarvud pärast 2?
V: Järgmised algarvud pärast 2 on 3, 5, 7, 11 ja 13.
K: Kas on olemas suurim algarv?
V: Ei, suurimat algarvu ei ole olemas. Algarvude hulk on lõpmatu.
K: Mida väidab aritmeetika põhitõde?
V: Aritmeetika põhiteoreem väidab, et iga positiivset täisarvu saab kirjutada priimarvude korrutisena üheselt mõistetavalt.
K: Mis on Goldbachi oletus?
V: Goldbachi oletus on lahendamata probleem matemaatikas, mis väidab, et iga täisarvu, mis on suurem kui kaks, saab väljendada kahe algarvu summana.
K: Kes pani kirja tõestuse, et pole olemas suurimat algarvu?
V: Eukleidese kirja pandud tõestus, et ei ole olemas suurimat algarvu.
Otsige