II.4.  Alkuluvuista

Jokainen nollasta eroava kokonaisluku on aina jaollinen luvulla 1 ja itsellään sekä näiden vastaluvuilla. Välttämättä luvulla ei olekaan muita tekijöitä. Ykköstä suurempaa kokonaislukua , joka on jaollinen vain luvuilla 1, −1, ja , sanotaankin alkuluvuksi eli jaottomaksi luvuksi. Muut ykköstä isommat kokonaisluvut ovat yhdistettyjä lukuja (tai jaollisia lukuja). Ne ovat silloin muotoa , missä ja .

Alkulukuja ovat mm. 2, 3, 5, 7, 11, 13, 17 ja 19. Pienet alkuluvut voi löytää suhteellisen helposti ns. Eratostheneen seulalla. Esimerkkinä menetelmästä määrätään lottoruudukossa esiintyvät alkuluvut (ks. kuviota alla). Ensin hylätään luku 1. Luku 2 on ensimmäinen alkuluku, ja sen jälkeen viivataan yli kaikki sen monikerrat. Tämän jälkeen ensimmäinen luku, jota ei ole vielä viivattu yli, on seuraava alkuluku, siis luku 3. Taas viivataan yli kaikki tämän monikerrat. Näin jatketaan: Ensimmäinen vastaan tuleva luku, jota ei ole siihen mennessä viivattu yli, on suuruusjärjestyksessä seuraava alkuluku. Sen kaikki monikerrat viivataan sitten yli, jne. Oheisessa kuviossa ympyröidyt luvut ovat tämän menetelmän mukaan lottoruudukossa esiintyvät alkuluvut.

Eratostheneen seulalla voi käsinkin etsiä varsin suuria alkulukuja, aina viisi-kuusinumeroisiin asti. Tietokoneilla päästään tietenkin paljon kauemmaksi! Tällä menetelmällä saadaan siis kaikki tiettyyn lukuun mennessä esiintyvät alkuluvut. Aina ei kuitenkaan tarvita kaikkia perättäisiä alkulukuja, vaan syystä tai toisesta ollaan kiinnostuneita löytämään mahdollisimman suuria alkulukuja. Näihin palataan tämän pykälän lopussa ja RSA-menetelmän yhteydessä (tämän luvun 5. pykälässä).

Opiskelutehtävä 19. (Satasta pienemmät alkuluvut)

Määrää kaikki satasta pienemmät alkuluvut.

Vinkki tehtävään 19

Opiskelutehtävä 20. (Alkulukujen muoto)

Osoita, että kaikki lukua 3 suuremmat alkuluvut ovat muotoa jollekin .

Vinkki tehtävään 20

Alkuluvuilla on jaollisuuden kannalta eräitä tärkeitä erikoisominaisuuksia. Seuraava on perustavanlaatuinen.

Lause 2.4.1. (Eukleideen lemma)

Jos alkuluku jakaa kahden kokonaisluvun ja tulon, se jakaa ainakin toisen tulon tekijöistä, ts. jos , niin tai .

Todistus. Oletuksen mukaan jollekin . Jos luku on jaollinen luvulla , pitää väite paikkansa. Oletetaan sitten, että ei ole jaollinen luvulla , ja osoitetaan, että silloin luku on jaollinen luvulla .

Koska on alkuluku, sillä on positiivisina tekijöinään vain luvut 1 ja . Toisaalta ei ole nyt jaollinen luvulla , joten välttämättä . On siis olemassa esitys joillekin kokonaisluvuille ja . Kertomalla tämä esitys luvulla saadaan yhtälö

,

mistä näkyykin, että luku on jaollinen luvulla .

Esimerkki 2.4.2.

Osoitetaan, että yhtälöllä ei ole yhtään rationaalista ratkaisua. Koska kaikkia rationaalilukuja ei voi käydä läpi, lienee viisainta yrittää todistaa väitettä antiteesillä. Oletetaan siis, että joillekin kokonaisluvuille ja . Voimme olettaa lisäksi, että rationaaliluku on supistetussa muodossa eli että luvut ja ovat keskenään jaottomia, ts. .

Yhtälön mukaan , joten tulo on jaollinen alkuluvulla 2. Eukleideen lemman mukaan silloin tai . Joka tapauksessa on siis jaollinen luvulla 2, ts. jollekin kokonaisluvulle . Siten eli .

Vastaavasti kuin edellä päätellään, että . Mutta nyt luku 2 olisi sekä luvun että luvun tekijä, mikä on ristiriita näiden keskinäisen jaottomuuden kanssa. Antiteesi on siis epätosi ja väite oikein.

Esimerkki 2.4.3.

Eukleideen lemmaa ei voi käyttää alkuluvun sijasta yhdistetyille luvuille. Esimerkiksi , mutta luku 6 ei jaa kumpaakaan tekijää.

Opiskelutehtävä 21. (Neliöjuurta pienempi alkutekijä)

Osoita, että jos luku ei ole alkuluku, niin sillä on tekijänä jokin alkuluku , jolle .

Vinkki tehtävään 21

Lause 2.4.4. (Aritmetiikan peruslause)

Ykköstä suurempi kokonaisluku on joko itse alkuluku tai se on alkulukujen tulo.

Todistus. Tehdään vastaoletus: On olemassa yhdistettyjä positiivisia kokonaislukuja, joita ei voi esittää alkulukujen tulona. Olkoon näistä pienin.

Yhdistettynä lukuna on muotoa , missä ja . Koska molemmat luvut ja ovat pienempiä kuin , ne ovat joko alkulukuja tai niiden tuloja. Mutta silloinhan myös luku on alkulukujen tulo, vastoin vastaoletusta. Väite on siis oikein.

Sellaista kokonaisluvun tekijää, joka on alkuluku, sanotaan myös sen alkutekijäksi. Aritmetiikan peruslauseen mukaan jokainen ykköstä suurempi kokonaisluku on itse asiassa esitettävissä muodossa

,

missä luvut ovat eri alkulukuja, ja potenssit vähintään ykkösiä. Tätä esitystä sanotaan luvun alkutekijäesitykseksi. Jos vielä alkutekijät ovat esityksessä pienuusjärjestyksessä, voidaan osoittaa, että esitys on silloin yksikäsitteinen.

Opiskelutehtävä 22. (Lukujen alkutekijät)

Jaa luvut 1999, 2000 ja 2001 alkutekijöihinsä.

Vinkki tehtävään 22

Jos luvuilla ja on alkutekijäesitykset

nähdään alkulukujen jaollisuusominaisuuksien perusteella, että luku on luvun tekijä eli täsmälleen silloin, kun luvun jokainen alkutekijä on luvun jokin alkutekijä ja sen potenssi ei ylitä vastaavaa potenssia .

Kahdelle kokonaisluvulle alkutekijäesityksistä voidaan helposti muodostaa niiden suurin yhteinen tekijä: poimitaan molemmissa esiintyvät alkuluvut, valitaan näille potenssiluvuksi esitysten potensseista pienempi ja muodostetaan näiden tulo. Menettelyn voi induktiivisesti yleistää useammallekin luvulle.

Esimerkki 2.4.5.

Luvuilla 540, 450 ja 882 on alkutekijäesitykset

,     ja  ,

joten . Alkutekijäesityksistä näkyy myös, että mikään näistä luvuista ei jaa toista.

Tehtävä. Selvitä, kuinka monta eri tekijää on luvuilla 108 ja 25200. (Vihje: Käytä lukujen alkutekijäesityksiä hyväksi.)

Lause 2.4.6.

Alkulukuja on äärettömän monta.

Todistus. Tehdään vastaoletus (millä muulla tavalla tätä voisi todistaakaan?): alkulukuja on vain äärellinen määrä, olkoot ne , , …, ja .

Tarkastellaan näiden tulosta seuraavaa kokonaislukua eli lukua

.

Se ei ole jaollinen millään luetellulla alkuluvulla , sillä muutoin sellainen alkuluku jakaisi myös luvun 1. Se on siis joko itse alkuluku tai yhdistetty luku, jonka kaikki alkulukutekijät ovat suurempia kuin luetelluista suurin . Joka tapauksessa on siis olemassa alkulukua suurempi alkuluku, mikä on vastoin antiteesiä. Lauseen väite on siis oikein.

Jossain mielessä alkulukuja on kuitenkin vähemmän kuin yhdistettyjä lukuja. Ovathan esimerkiksi kaikki kakkosta suuremmat parilliset luvut yhdistettyjä lukuja. On myös olemassa mielivaltaisen pitkiä yhdistettyjen lukujen muodostamia jonoja. Annetulle luvulle nimittäin luvut , , …, ovat kaikki yhdistettyjä lukuja; ensimmäinen on jaollinen luvulla 2, toinen luvulla 3, …, ja viimeinen luvulla . Näitä peräkkäisiä lukuja on yhteensä kappaletta.

Jos on niiden alkulukujen määrä, jotka ovat korkeintaan luvun suuruisia, lähestyy ns. alkulukulauseen mukaan suurilla luvun arvoilla siihen mennessä vastaan tulleiden alkulukujen määrän ja lausekkeen suhde lukua 1 (tässä ln tarkoittaa luonnollista logaritmia). Esimerkiksi luvulle on alkulukujen määrä ja lauseke , joten niiden suhde on likimain 1,054. Alkulukulauseen todistivat J. Hadamard ja J. C. de la Vallée-Poussin vuonna 1896.

Oikein suurelle luvulle voi olla työlästä löytää sen alkutekijäesitystä. Ylivoimaista voi olla jo senkin selvittäminen, onko se yhdistetty luku tai alkuluku. Toisaalta eri tilanteita, esimerkiksi salakirjoitusta, varten halutaan löytää yhä suurempia ja suurempia alkulukuja. Sellaisia etsittiin joskus Fermat'n lukujen

ja nykyään etenkin Mersennen lukujen

( alkuluku)

joukosta (jälkimmäisistä yleisesti vain alkuluvut numeroidaan, eikä kaikkia kyseisen tyyppisiä lukuja). Pierre de Fermat (1601−1665) itse osoitti, että luvut

, , , ja

ovat alkulukuja ja väitti, että kaikki kyseisen muotoiset luvut olisivat alkulukuja. Mutta Leonhard Euler osoitti v. 1732, että luvulla on tekijäesitys

,

ja I. F. Zolotarov v. 1878, että on jaollinen luvulla . Nykyään tiedetään, että ei ole alkuluku, kun . Luku lienee kuitenkin toistaiseksi suurin, jolle tiedetään tekijöihinjako. Alkuluvuiksi Fermat'n luvuista on todettu vain nuo viisi ensimmäistä ja avoin probleema onkin, onko niiden joukossa yhtään muuta.

Mersennen alkuluvuista ensimmäiset ovat

, , ,
, , .

Vuoden 2006 loppuun mennessä oli löydetty kaikkiaan 44 Mersennen alkulukua. Näistä tiedettiin, että

.

Tämän lisäksi oli löydetty vielä isommat alkuluvut

, , , ja ,

mutta niistä ei vielä tiedetty, olivatko ne nimenomaan järjestyksessä seuraavat Mersennen alkuluvut. Viimeisimmän luvun desimaaliesityksessä on yli 9,8 miljoonaa numeroa.

Alkulukuihin liittyy edelleen monia avoimia kysymyksiä. Ei ole esimerkiksi pystytty selvittämään, onko Mersennen alkulukuja ylipäätään olemassa loputtomasti. Avoin kysymys on myös ns. Goldbachin väittämä, jonka mukaan jokainen kakkosta suurempi parillinen luku voidaan esittää kahden alkuluvun summana. Vastausta vaille on edelleen ns. alkulukukaksosia koskeva pulma: onko olemassa loputtomasti lukupareja ja , joista molemmat olisivat alkulukuja?

Alkulukuihin liittyvää tietoutta, varsinkin uusimmista alkuluvuista, löytyy monilta internetin sivuilta, mm. osoitteesta http://primes.utm.edu/.

[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]