Aritmetiikan peruslause: alkulukujen yksikäsitteinen tekijäjako ja käyttö

Aritmetiikan peruslause: selkeä opas alkulukujen yksikäsitteiseen tekijäjakoon ja sen käyttöön, mm. kryptografiassa — teoriasta käytäntöön.

Tekijä: Leandro Alegsa

18-12-2025 11:45

Aritmetiikan peruslause (jota kutsutaan myös ainutlaatuisen tekijäjaon lauseeksi) on lukuteorian tärkeä lause. Lauseen mukaan jokainen positiivinen kokonaisluku, joka on suurempi kuin 1, voidaan kirjoittaa alkulukujen tulona (tai luku on itse alkuluku). Lause sanoo myös, että tällainen kirjoitus on yksikäsitteinen: jos kaksi ihmistä löytää kaksi kirjoitusta samasta luvusta alkulukujen tulona, ne eroavat vain alkulukujen järjestyksessä.

Esimerkkejä:

6936 = 2³ · 3 · 17²

1200 = 2⁴ · 3 · 5²

Alkulukujen löytymistä kokonaisluvun tekijöiksi kutsutaan kertolaskuksi (eli alkulukuhajotelman muodostamiseksi). Tämä periaate on keskeinen monessa matemaattisessa käsitteessä ja sillä on käytännön merkitystä laskennassa ja kryptografiassa.

Mitä tarkoittaa "yksikäsitteinen"?

Yksikäsitteisyys tarkoittaa, että jos n = p1·p2·...·pr = q1·q2·...·qs, missä kaikki p_i ja q_j ovat alkulukuja, niin r = s ja jossain järjestyksessä p_i = q_i kaikille i. Toisin sanoen primes ovat kokonaislukujen "atomit": ne muodostavat kaikki muut luvut ja jokaisella luvulla on vain yksi alkulukujen kertolaskuesitys (pois lukien esityksen järjestyksen permutaatio). Huomaa, että luku 1 ei ole alkuluku eikä komposiittiluku, ja se suljetaan erikseen pois esityksistä.

Todistuksen idea lyhyesti

Peruslauseen todistus koostuu kahdesta osasta: olemassaolosta ja yksikäsitteisyydestä.

Esiintymisen (olemassaolon) todistus: Käytännössä todistus voidaan tehdä induktiolla tai jakamalla luku toistuvasti pienimmällä alkutekijällään. Koska jokainen ei-alkuluku voidaan hajottaa kahden pienemmän tekijän tuloksi, jatkamalla tätä prosessia päädymme lopulta pelkkiin alkulukuihin.
Yksikäsitteisyyden todistus: Keskeinen työkalu on Euclidin lemma: jos p on alkuluku ja p jakaa a·b, niin p jakaa a tai p jakaa b. Jos olisi kaksi erilaista alkulukujen hajotelmaa samalle luvulle, Euclidin lemmaa toistamalla päädytään ristiriitaan, koska jokainen alkuluku jommassakummassa hajotelmista pitäisi jakaa jonkin toisen hajotelman alkuluvuista.

Seuraukset ja käytännön sovelluksia

Alkulukuhajotelmat antavat kätevän tavan laskea suurempia aritmeettisia suureita. Esimerkiksi suurimman yhteisen tekijän ja pienimmän yhteisen monikerran laskeminen perustuu alkulukujen eksponentteihin: jos n = ∏ p_i^a_i ja m = ∏ p_i^b_i, niin gcd(n,m) = ∏ p_i^min(a_i,b_i) ja lcm(n,m) = ∏ p_i^max(a_i,b_i).
Vaikka peruslause takaa, että hajotelma on yksikäsitteinen, ei se kerro, kuinka helppoa hajottaminen on laskennallisesti. Pienten lukujen hajottaminen on helppoa esimerkiksi alkulukujen koepalautuksella, mutta suurten luvujen faktorisointi voi olla laskennallisesti vaikeaa. Tätä vaikeutta hyödynnetään monissa salaustekniikoissa ja erityisesti julkisen avaimen järjestelmissä kuten RSA:ssa — siksi peruslause on merkittävä myös kryptografiassa.
Algoritmeja faktorisointiin ovat mm. trial division (jakokokeet alkulukuihin asti n:n neliöjuureen), Pollardin rho -algoritmi, elliptiset käyrät (ECM) ja yleinen luvuten kenttä -siivilä (GNFS) hyvin suurten lukujen tapauksessa.

Yleistäminen

Peruslause on erityinen tapaus laajemmasta käsitteestä, jossa tutkitaan, onko renkaassa tai vyössä yksikäsitteinen tekijäjako. Luvilla tämä vastaa käsitettä "unique factorization domain" (UFD): kokonaislukien rengas Z on esimerkki UFD:stä. On olemassa renkaita, joissa alkulukujen kaltainen käsite ei johda yksikäsitteiseen tekijäjakoon — tällaiset esimerkit kuuluvat algebraan ja kertovat, että peruslause ei automaattisesti päde kaikkiin rakenteisiin ilman lisäehtoja.

Yhteenvetona: Lause antaa selkeän ja voimakkaan kuvan kokonaislukujen rakenteesta: alkuluvut muodostavat rakennuspalikat, ja jokainen luku (yli 1) on yksikäsitteisesti rakennettavissa niistä. Tämä käsitys on sekä teoreettisesti tärkeä että käytännössä hyödyllinen.

Todiste

Ensimmäinen henkilö, joka todisti lauseen, oli Eukleides. Ensimmäinen yksityiskohtainen ja oikea todistus oli Carl Friedrich Gaußin Disquisitiones Arithmeticae -teoksessa.

Jotkut saattavat ajatella, että lause on totta kaikkialla. Lause ei kuitenkaan päde yleisemmissä lukujärjestelmissä, kuten algebrallisissa kokonaisluvuissa. Ernst Kummer mainitsi tämän ensimmäisen kerran vuonna 1843 teoksessaan Fermat'n viimeinen lause. Lisätietoa tästä: lue algebrallinen lukuteoria.

Todistus koostuu kahdesta osasta: ensinnäkin osoitamme, että jokainen luku voidaan kirjoittaa alkulukujen tulona; toiseksi osoitamme, että jos kirjoitamme luvun toisen kerran alkulukujen tulona, kahden alkulukujen luettelon on oltava sama.

Todistuksen ensimmäinen osa

Osoitamme, että jos jokaista lukua, joka on suurempi kuin 1, ei voida kirjoittaa alkulukujen tulona, päädymme jonkinlaiseen mahdottomuuteen. Tämän jälkeen päätämme, että on oltava totta, että jokainen luku voidaan kirjoittaa alkulukujen tulona.

Katsotaan nyt, mitä tapahtuu, kun joku sanoo tietävänsä positiivisen kokonaisluvun, joka on suurempi kuin 1 ja jota ei voi kirjoittaa alkulukujen tulona. Tällöin pyydämme häntä mainitsemaan kaikki luvut, jotka ovat suurempia kuin 1 ja joita ei voida kirjoittaa alkulukujen tulona. Yhden näistä luvuista on oltava pienin: sanotaan sitä n. Tämä luku n ei tietenkään voi olla 1. Se ei myöskään voi olla alkuluku, koska alkuluku on yhden alkuluvun "tuote": itse alkuluku. Sen on siis oltava lukujen tulo. Näin ollen -

n = ab

jossa sekä a että b ovat positiivisia kokonaislukuja, jotka ovat tietenkin pienempiä kuin n. Mutta: n oli pienin luku, jota ei voi kirjoittaa alkulukujen tulona. Joten a ja b on voitava kirjoittaa alkulukujen tulona, koska ne ovat molemmat pienempiä kuin n. Mutta silloin tulo

n = ab

voidaan kirjoittaa myös alkulukujen tulona. Tämä on mahdottomuus, koska sanoimme, että n:ää ei voi kirjoittaa alkulukujen tulona.

Olemme nyt osoittaneet mahdottomuuden, joka on olemassa, jos lauseen ensimmäinen osa ei olisi totta. Näin olemme nyt todistaneet lauseen ensimmäisen osan.

Todistuksen toinen osa

Nyt meidän on todistettava, että on vain yksi tapa kirjoittaa positiivinen luku, joka on suurempi kuin 1, alkulukujen tulona.

Tätä varten käytämme seuraavaa lemmaa: jos alkuluku p jakaa tulon ab, se joko jakaa a:n tai b:n (Eukleideen lemma). Todistamme nyt ensin tämän lemman. Oletetaan, että p ei jaa a:ta. Silloin p ja a ovat yhteiskertoimisia, ja meillä on Bezoutin identiteetti, joka sanoo, että on oltava kokonaisluvut x ja y, jotka ovat sellaisia, että

px + ay = 1.

Kun kaikki kerrotaan b:llä, saadaan

pbx + aby = b,

Muista, että ab voidaan jakaa p:llä. Nyt vasemmalla puolella on kaksi termiä, jotka ovat jaollisia p:llä. Joten myös oikealla puolella oleva termi on jaollinen p:llä. Olemme nyt todistaneet, että jos p ei jaa a:ta, sen on jaettava b. Tämä todistaa lemman.

Nyt todistamme, että voimme kirjoittaa kokonaisluvun, joka on suurempi kuin 1, vain yhdellä tavalla alkulukujen tulona. Otetaan kaksi alkulukujen A ja B tuotetta, joilla on sama tulos. Tiedämme siis tuotteiden tuloksen, että A = B. Otetaan mikä tahansa alkuluku p ensimmäisestä tuotteesta A. Se jakaa A:n, joten se jakaa myös B:n. Käyttämällä useaan kertaan äsken todistamaamme lemmaa voimme nähdä, että p:n on silloin jaettava vähintään yksi B:n tekijä b. Mutta kaikki tekijät ovat itse alkulukuja, joten myös b on alkuluku. Mutta tiedämme, että p on myös alkuluku, joten p:n on oltava yhtä suuri kuin b. Jaamme siis nyt A:n p:llä ja jaamme myös B:n p:llä. Ja saamme tuloksen A* = B*. Jälleen voimme ottaa alkutuotteen A* alkuluvun p ja todeta, että se on yhtä suuri kuin jokin luku tuotteessa B*. Jatkamalla tällä tavalla näemme lopuksi, että kahden tuotteen alkutekijöiden on oltava täsmälleen samat. Tämä todistaa, että voimme kirjoittaa positiivisen kokonaisluvun alkulukujen tuotteena vain yhdellä ainoalla tavalla.

Aiheeseen liittyvät sivut

Algebran perusteoria

Kokonaislukujen jaettavuuteen perustuvat joukot
Yleiskatsaus	Kokonaislukujen kertolasku Jakaja Yhtenäinen jakaja Divisori-funktio Ensisijainen tekijä Aritmetiikan perusoppi
Faktorisointimuodot	Prime Komposiitti Semiprime Pronic Sphenic Neliötön Tehokas Täydellinen teho Akilles Sileä Säännöllinen Rough Epätavallinen
Rajoitetut jakajasummat	Täydellinen Lähes täydellinen Quasiperfect Kerro täydellinen Hemiperfect Hyperperfekti Superperfect Yhtenäinen täydellinen Puoliksi täydellinen Käytännön Erdős-Nicolas
Kun jakajia on paljon	Runsas Primitiivinen runsas Erittäin runsas Superrunsas Kolossaalisen runsas Erittäin komposiitti Superior erittäin komposiitti Outo
Aliquot-sekvenssiin liittyvä	Koskemattomat Ystävällinen (kolminkertainen) Seurallinen Kihlattu
Base-riippuvainen	Equidigital Ekstravagantti Taloudellinen Harshad Polydivisible Smith
Muut sarjat	Aritmeettinen Puutteellinen Ystävällinen Yksinäinen Sublime Harmoninen jakaja Descartes Uudelleentarkasteltava Superperfect

Kysymyksiä ja vastauksia

K: Mikä on aritmetiikan perusteoria?

V: Aritmetiikan perusteoria on lukuteorian lause, jonka mukaan jokainen positiivinen kokonaisluku, joka on suurempi kuin 1, voidaan kirjoittaa alkulukujen tulona, ja on vain yksi tapa kirjoittaa luku.

K: Miten tätä teoreemaa voidaan käyttää?

V: Tätä teoreemaa voidaan käyttää salakirjoituksessa.

K: Mitä tapahtuu, jos kaksi ihmistä löytää kaksi eri tapaa kirjoittaa sama luku?

V: Jos kaksi ihmistä löytää kaksi eri tapaa kirjoittaa sama luku, ainoa asia, joka voi olla erilainen, on järjestys, jossa alkuluvut kirjoitetaan.

K: Mitä on kertolasku?

V: Faktorisointi tarkoittaa kaikkien tietyn luvun muodostavien alkulukujen löytämistä.

K: Onko 6936 esimerkki alkuluvusta?

V: Ei, 6936 ei ole alkuluku; se voidaan kirjoittaa muodossa 23 - 3 - 172.
Ei, 6936 ei ole alkuluku; se voidaan kirjoittaa muodossa 23 - 3 - 172.

Etsiä