Alkuluvut – määritelmä, ominaisuudet ja esimerkit
Tutustu alkulukuihin: selkeä määritelmä, tärkeimmät ominaisuudet ja havainnollistavat esimerkit. Opas alkeista edistyneempiin käsitteisiin ja klassisiin ongelmiin.
Primaluku on luonnollinen luku, joka on suurempi kuin 1 ja jonka ainoat positiiviset tekijät ovat 1 ja luku itse. Toisin sanoen luku p > 1 on alkuluku, jos sitä ei voi kirjoittaa kahden suuremman luonnollisen luvun m ja n tulona. Jos luku voidaan esittää siten, sitä kutsutaan yhdistelmäluvuksi eli komposiittiluvuksi. Pienin yhdistelty luku on 4, koska 2 × 2 = 4. Luku 1 ei ole yhdistelty eikä alkuluku, vaan sillä on oma erityisasemansa. Pienin alkuluku on 2, ja sitä seuraavat alkuluvut ovat 3, 5, 7, 11 ja 13. Suurinta alkulukua ei ole: alkulukuja on äärettömän monta. Primalukujen joukkoa merkitään joskus muodossa 
.
Määritelmä ja keskeisiä ominaisuuksia
- Alkuluku on kokonaisluku p > 1, jolla ei ole muita positiivisia tekijöitä kuin 1 ja p itse.
- 2 on ainoa parillinen alkuluku; kaikki muut alkuluvut ovat parittomia.
- Alkulukuja on äärettömästi — tästä antoi ensimmäisen tunnetun todistuksen antiikin matemaatikko Eukleideus.
- Kun luku kasvaa, sen alkulukuisuuden varmistaminen voi olla laskennallisesti vaikeampaa; samaan aikaan alkulukujen esiintymisen tarkka ennustaminen on yksi matematiikan kiinnostavista osa-alueista.
Alkulukujen esimerkkejä
Ensimmäisiä alkulukuja ovat
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Pienimmät yhdistelmäluvut ovat 4, 6, 8, 9, 10, ...
Peruslause aritmetiikassa
Aritmetiikan perusteoriassa todetaan, että jokainen positiivinen kokonaisluku > 1 voidaan esittää alkulukujen tulona tavalla, joka on yksikäsitteinen järjestyksestä riippumatta. Tämä on niin sanottu peruslause aritmetiikassa (Fundamental Theorem of Arithmetic). Käytännössä tämä tarkoittaa, että jokaisella kokonaisluvulla on yksikäsitteinen alkutekijäjako.
Tämä periaate on keskeinen monilla aloilla, mm. lukuteoriassa, koodauksessa ja salauksessa (esim. RSA), koska suurten lukujen tekijöihin jakaminen on usein paljon vaikeampaa kuin alkuluvun testaaminen.
Alkulukujen etsiminen ja testaaminen
Alkulukujen löytämiseen ja testaamiseen on kehitetty monia menetelmiä:
- Jaollisuustestit ja koejaotus (trial division) pienillä tekijöillä — yksinkertainen mutta hidas suurilla luvuilla.
- Seulamenetelmät, kuten Eratostheneen seula, jotka löytävät kaikki alkuluvut tiettyyn rajaan asti tehokkaasti.
- Probabilistiset primalisuustestit, kuten Miller–Rabin, jotka kertovat todennäköisesti, onko luku alkuluku (nopeat ja käytännössä luotettavat parametrien valinnalla).
- Deterministiset algoritmit, kuten AKS-primalisuustesti, jotka pystyvät kertomaan varmasti, onko luku alkuluku, ilman todennäköisyyskomponenttia (vaikka käytännössä usein hitaampia kuin heuristiset testit suurilla luvuilla).
Jakautuminen ja tilastolliset tulokset
Alkulukujen jakautumista suurten lukujen joukossa kuvaa muun muassa alkulukujen jakautumislause (Prime Number Theorem), jonka mukaan alkulukujen tiheys lähellä suurta lukua n on suunnilleen 1 / log n. Tämä antaa käsityksen siitä, kuinka harvinaisia alkuluvut ovat kasvaessa.
Suuria avoimia ongelmia ja tutkimus
- Goldbachin arvelu — esittää, että jokaista parillista lukua suurempaa kuin 2 voidaan esittää kahden alkuluvun summana; tämä on vielä ratkaisematon.
- Kaksosalkuluvut (twin primes) — arvaus on, että äärettömän monta paria p ja p+2 on alkulukuja, mutta tämäkin on ratkaisematta.
- Alkulukujen esiintymiseen liittyy monia muita syviä kysymyksiä, ja uusinta tutkimusta tehdään sekä teoreettisesti että laskennallisesti.
Suurimmat löydetyt alkuluvut
Suuret alkuluvut löydetään usein Mersennen-lukujen muotoisina (2^p − 1, kun p on alkuluku) ja monet maailman suurimmat tunnetut alkuluvut löytyvät GIMPS-projektin (Great Internet Mersenne Prime Search) kaltaisissa hajautetuissa laskentaprojekteissa. Monet tutkijat ja harrastajat osallistuvat tähän työhön etsiäkseen yhä suurempia alkulukuja.
Käytännön huomioita ja esimerkkejä tehtäviä varten
Perustehtäviä:
- Tarkista, onko luku 97 alkuluku käyttämällä koejaotusta tekijöillä 2, 3, 5, 7 (riittää, kun tarkistat kaikki tekijät ≤ √97).
- Kirjoita luku 360 alkutekijämuodossa: 360 = 2^3 × 3^2 × 5.
Alkuluvut ovat yksi lukuteorian keskeisistä aiheista ja niihin liittyy sekä yksinkertaisia perusominaisuuksia että hyvin syvällisiä ja vaikeita ongelmia. Lisätietoa ja syventäviä teemoja voi löytää muun muassa alkulukuteoriasta ja aritmetiikan perusteoriasta (Aritmetiikan perusteoriassa).
Huom. Se, että jokin luku ei ole ilmeisesti jaollinen pienillä tekijöillä, ei aina todista lopullisesti sen alkulukuisuutta ilman luotettavaa primalisuustestiä tai täydellistä tekijöintiä.
Tässä on toinen tapa ajatella alkulukuja. Luku 12 ei ole alkuluku, koska siitä voidaan muodostaa suorakulmio, jonka sivujen pituudet ovat 4 ja 3. Tämän suorakulmion pinta-ala on 12, koska kaikki 12 palikkaa on käytetty. Tätä ei voida tehdä 11:llä. Miten tahansa suorakulmio järjestetäänkin, jäljelle jää aina palikoita, lukuun ottamatta suorakulmiota, jonka sivujen pituudet ovat 11 ja 1. 11:n on siis oltava alkuluku.
Miten löytää pieniä alkulukuja
Primalukujen luettelon löytämiseen on yksinkertainen menetelmä. Eratosthenes loi sen. Sen nimi on Eratostenesin seula. Se ottaa kiinni luvut, jotka eivät ole alkulukuja (kuten seula), ja päästää alkuluvut läpi.
Menetelmä toimii numeroluettelon ja erityisen b-nimisen luvun kanssa, joka muuttuu menetelmän aikana. Menetelmää läpikäydessä ympyröidään joitakin numeroita luettelossa ja yliviivataan toisia. Jokainen ympyröity luku on alkuluku ja jokainen yliviivattu luku on yhdistetty. Alussa kaikki luvut ovat tavallisia: niitä ei ole ympyröity eikä yliviivattu.
Menetelmä on aina sama:
- Kirjoita paperille kaikki kokonaisluvut 2:sta testattavaan lukuun asti. Älä kirjoita numeroa 1. Siirry seuraavaan vaiheeseen.
- Aloita, kun b on 2. Siirry seuraavaan vaiheeseen.
- Ympyröi b luettelossa. Siirry seuraavaan vaiheeseen.
- Aloita b:stä, laske luettelossa vielä b ylöspäin ja pyyhi tämä luku yli. Toistakaa vielä b numeron laskemista ylöspäin ja numeroiden yliviivaamista, kunnes lista on lopussa. Siirry seuraavaan vaiheeseen.
- (Esimerkiksi: Kun b on 2, ympyröi 2 ja yliviivaa 4, 6, 8 ja niin edelleen. Kun b on 3, ympyröit 3 ja yliviivaat 6, 9, 12 jne. 6 ja 12 on jo yliviivattu. Rastita ne uudelleen.)
- Suurenna b:tä 1:llä. Siirry seuraavaan vaiheeseen.
- Jos b on yliviivattu, palaa edelliseen vaiheeseen. Jos b on luettelon numero, jota ei ole yliviivattu, siirry kolmanteen vaiheeseen. Jos b ei ole luettelossa, siirry viimeiseen vaiheeseen.
- (Tämä on viimeinen vaihe.) Olet valmis. Kaikki alkuluvut on ympyröity ja kaikki yhdistetyt luvut on yliviivattu.
Menetelmää voidaan soveltaa esimerkiksi luetteloon, joka sisältää numerot 2-10. Lopulta numerot 2, 3, 5 ja 7 päätyvät ympyröityinä. Nämä ovat alkulukuja. Numerot 4, 6, 8, 9 ja 10 yliviivataan. Nämä ovat yhdistettyjä lukuja.
Tämä menetelmä tai algoritmi kestää liian kauan löytää hyvin suuria alkulukuja. Se on kuitenkin yksinkertaisempi kuin hyvin suurten alkulukujen määrittämiseen käytetyt menetelmät, kuten Fermat'n alkulukutesti (testi, jolla selvitetään, onko luku alkuluku vai ei) ja Miller-Rabinin alkulukutesti.
Mihin alkulukuja käytetään
Primaluvut ovat erittäin tärkeitä matematiikassa ja tietotekniikassa. Hyvin pitkiä lukuja on vaikea ratkaista. Niiden alkutekijöitä on vaikea löytää, joten useimmiten salakirjoitukseen ja salaisiin koodeihin käytetään lukuja, jotka todennäköisesti ovat alkulukuja. Esim:
- Useimmilla ihmisillä on pankkikortti, jolla he voivat nostaa rahaa tililtään pankkiautomaatilla. Kortti on suojattu salaisella salasanalla. Koska koodi on pidettävä salassa, sitä ei voi tallentaa kortille selväkielisenä. Koodin tallentamiseen salassa käytetään salausta. Tässä salauksessa käytetään kertolaskuja, jakolaskuja ja suurten alkulukujen jäännöslukujen löytämistä. Käytännössä käytetään usein algoritmia nimeltä RSA. Se käyttää kiinalaista jäännösteoriaa.
- Jos jollakulla on digitaalinen allekirjoitus sähköpostissaan, käytetään salausta. Näin varmistetaan, ettei kukaan voi väärentää sähköpostia. Ennen allekirjoittamista viestistä luodaan hash-arvo. Tämä yhdistetään sitten digitaaliseen allekirjoitukseen, jolloin saadaan allekirjoitettu viesti. Käytetyt menetelmät ovat suurin piirtein samat kuin ensimmäisessä edellä mainitussa tapauksessa.
- Suurimman tunnetun alkuluvun löytämisestä on vuosien varrella tullut eräänlainen urheilulaji. Jos luku on suuri, voi olla vaikeaa testata, onko se alkuluku. Suurimmat tällä hetkellä tunnetut alkuluvut ovat yleensä Mersennen alkulukuja, koska nopein tunnettu alkulukutesti on Lucas-Lehmerin testi, joka perustuu Mersennen lukujen erityismuotoon.
Aiheeseen liittyvät sivut
- Coprime
- Luettelo alkuluvuista
- Palindrominen prime
- Primaaritekijöiden kertolasku
- Wilson prime
Kysymyksiä ja vastauksia
Kysymys: Mikä on alkuluku?
A: Primaluku on luonnollinen luku, jota ei voi jakaa millään muulla luonnollisella luvulla kuin 1:llä ja itsellään.
K: Mikä on pienin yhdistetty luku?
A: Pienin yhdistetty luku on 4, koska 2 x 2 = 4.
K: Mitkä ovat seuraavat alkuluvut 2:n jälkeen?
V: Seuraavat alkuluvut 2:n jälkeen ovat 3, 5, 7, 11 ja 13.
K: Onko olemassa suurin alkuluku?
V: Ei, suurinta alkulukua ei ole olemassa. Primalukujen joukko on ääretön.
K: Mitä sanotaan aritmetiikan perusteoriassa?
V: Aritmetiikan perusteoremin mukaan jokainen positiivinen kokonaisluku voidaan kirjoittaa alkulukujen tulona yksikäsitteisellä tavalla.
K: Mikä on Goldbachin arvelu?
V: Goldbachin arvelu on matematiikan ratkaisematon ongelma, jonka mukaan jokainen parillinen kokonaisluku, joka on suurempi kuin kaksi, voidaan ilmaista kahden alkuluvun summana.
K: Kuka kirjasi todisteen siitä, että suurinta alkulukua ei ole olemassa?
V: Eukleides kirjasi todisteen siitä, että suurinta alkulukua ei ole olemassa.
Etsiä