Aritmetiikan peruslause

Alkuluvut

Alkuluvuksi sanotaan ykköstä suurempaa kokonaislukua, joka on jaollinen vain itsellään ja luvulla yksi. Esimerkiksi luku 11 = 1·11 on alkuluku mutta luku 9 = 1·3·3 ei ole alkuluku koska se on jaollinen myös luvulla 3.

Esimerkki 1

Tutki, onko luku alkuluku.

a) 128

b) 131

a) Huomataan, että luku 128 on parillinen luku ja täten jaollinen luvulla 2. Siispä luku 128 ei ole alkuluku.

b) Etsitään luvun 131 tekijöitä kokeilemalla jakolaskua 131/a kymmenellä ensimmäisellä ykköstä suuremmalla kokonaisluvulla a = 2,3,4,...,11. Huomataan että luku 131 ei ole jaollinen millään kokonaisluvulla 2–11.

Jos siis luku 131 on mahollista jakaa tekijöihin, niin 131 = pq, missä p, q ∈ ℕ ja luvut p, q ovat jotakin muuta kuin luvut 131 ja 1, niin p ≥ 12 ja q ≥ 12. Toisaalta, jos p ≥ 12 ja q ≥ 12, niin

pq ≥ 12·12 = 144 > 131.

Täten luku 131 on jaollinen vain itsellään ja luvulla 1. Näin ollen luku 131 on alkuluku.

Tehtävän 1b havainto voidaan yleistää lauseeksi

Todistus

Todistetaan väite kontrapositiolla.

Tehtään vastaoletus. Oletetaan että

Tällöin

Päädyttiin ristiriitaan oletuksen pq = n kanssa eli lause

on tosi.

Listan jäljelle jääneet luvut ovat alkulukuja. Sillä kuten aikaisemmin todettiin, niin kaikki välillä 2-n olevat alkuluvut ovat pienempiä tai yhtäsuuria kuin luvun n neliöjuuri ja jaollisia vain itsellään sekä luvulla 1.

Esimerkki 2

Etsitään Eratotheneksen seulalla kaikki alkuluvut väliltä 2-40.

(1) Kirjoitetaan kaikki luvut listaksi.

(2) Luku 2 on alkuluku. Poistetaan listalta kaikki lukua 2 suuremmat luvun 2 moninkerrat.

(3) Listan seuraava jäljellä oleva luku on kolme. Luku 3 on alkuluku. Poistetaan listalta kaikki lukua 3 suuremmat luvun 3 moninkerrat.

(4) Luku 4 on poistettu listalta eli listan seuraava jäljellä oleva luku on 5. Luku 5 on alkuluku. Poistetaan listalta kaikki lukua 5 suuremmat luvun 5 moninkerrat.

Listan seuraava jäljellä oleva luku on luku 7, joka on suurempi kuin luvun 40 neliöjuuri

Täten kaikki listan loput jäljellä olevat luvut ovat alkulukuja. Alkuluvut välillä 2-40: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.

Alkutekijä

Kokonaisluvun a alkutekijöitä ovat ne luvun a tekijät, jotka ovat alkulukuja.

Esimerkiksi luvun 16=2⁴ tekijät ovat 1,2,4,8 ja 16, joista ainoastaan luku 2 on alkulukuna luvun 16 alkutekijä.

Aritmetiikan peruslause

Jokainen lukua 1 suurempi kokonaisluku a voidaan ilmaista yksikäsitteisesti (poislukien tekijöiden järjestys) alkutekijöidensä tulona:

missä p₁,p₂,...,pₖ ovat luvun a alkutekijät ja n₁,n₂,...,nₖ ∈ ℕ.

Esitystä kutsutaan luvun a alkutekijähajotelmaksi. Esimerkiksi luvun 16 alkutekijähajotelma on 16=2⁴. Kun luku a on esitetty alkutekijähajotelmana, niin sanotaan että luku a on jaettu alkutekijöihin.

Aritmetiikan peruslauseen todistukseen tarvitaan Eukleideen lemmaa, joka esitetään seuraavaksi.

Eukleideen lemma

Jos kahden kokonaisluvun a ja b tulo on jaollinen alkuluvulla p, niin ainakin toinen luvuista a ja b on jaollinen luvulla p, toisin sanoen jos p|ab, niin p|a tai p|b.

Todistus

Oletuksen mukaan p|ab eli ab = np, jollakin n ∈ ℕ. Jos p|a, niin lause on tosi. Jos p∤a, niin on todistettava, että p|b.

Jos p∤a, niin syt(p, a) = 1. On siis olemassa sellaiset kokonaisluvut x,y, että

Siispä p|b.

Aritmetiikan peruslauseen todistus

Todistetaan lause kahdessa vaiheessa:

(1) Todistetaan, että jokainen kokonaisluku a > 1 voidaan esittää alkutekijöidensä tulona.

Todistetaan väite tekemällä ristiriitatodistus: tehdään vastaoletus ja päädytään ristiriitaan eli todistetaan alkuperäisen lauseen negaatio epätodeksi.

Tehdään vastaoletus: a on pienin ykköstä suurempi kokonaisluku, jolla ei ole alkulukuhajotelmaa.

Täten a ei voi olla alkuluku eli a = p·q, joillakin kokonaisluvuilla p, q > 1.

Koska p, q > 1, niin p, q < a.

Koska oletuksen mukaan a on pienin ykköstä suurempi luku, jolla ei ole alkutekijähajotelmaa ja p, q < a, niin luvuilla p ja q on alkutekijähajotelmat.

Täten luvulla a on lukujen p ja q tulona alkutekijähajotelma. Pädyttiin ristiriitaan oletuksen kanssa. Toditetusti jokaisella kokonaisluvulla a > 1 on olemassa alkutekijähajotelma.

(2) Todistetaan, että kokonaisluvun a > 1 alkutekijähajotelma on yksikäsitteinen.

Todistetaan väite ristiriitatodistuksella.

Tehdään vastaoletus: luvulla a on vähintään kaksi eri alkutekijähajotelmaa:

Täten on ainakin yksi sellainen alkuluku pᵢ, joka ei sisälly jälkimmäiseen alkutekijähajotelmaan.

Koska q₁ on alkuluku, niin se ei ole jaollinen luvulla pᵢ ≠ q₁. Eukleideen lemman perusteella

Myöskään luku q₂ ei ole alkulukuna jaollinen luvulla pᵢ ≠ q₂. Yhä Eukleideen lemmaan nojaten saadaan

Jatkamalla päättelyä lukuun qₖ asti päädytään tulokseen pᵢ|1, mikä on ristiriita sen kanssa että pᵢ > 1. Todistetusti luvun a > 1 alkutekijähajotelma on yksikäsitteinen.

Esimerkki 3

Muodosta luvun 31920 alkutekijähajotelma.

Ratkaisu

Huomataan että luku 31920 on parillinen. Jaetaan alkuluvulla 2, niin monta kertaa kuin mahdollista.

Seuraavaksi suurin alkuluku on 3. Luku 1995 on jaollinen luvulla 3.

Seuraavaksi suurin alkuluku on 5. Luku 665 on jaollinen luvulla 5.

Seuraavaksi suurin alkuluku on 7. Luku 133 on jaollinen luvulla 7.

Luku 19 on alkuluku eli kaikki tekijät ovat nyt alkutekijöitä. Kirjoitetaan lopuksi tulo käyttämällä potenssimerkintää. Luvun 31920 alkutekijähajotelma:

pienemmällä alkuluvulla. Hyödynnetään esimerkin 2 tulosta, josta saadaan alkuluvut väliltä 2-14: 2, 3, 5, 7, 11, 13. Huomataan, että luku 211 ei ole jaollinen millään alkuluvulla väliltä 2-14 eli luku 211 on alkuluku.

Esimerkki 5

Määritä lukujen 1176 ja 2772

a) suurin yhteinen tekijä

b) pienin yhteinen moninkerta

Ratkaisu

Määritetään lukujen 1176 ja 2772 alkutekijähajotelmat ja muodostetaan lukujen suurin yhteinen tekijä sekä pienin yhteinen moninkerta alkutekijöistä.

a) syt(1176, 2772) = 2² · 3 · 7 = 84

b) pym(1176, 2772) = 2³ · 3² · 7² · 11 = 38808

Jaollisuuslauseita

(1) Oletetaan, että a ja b ovat erisuuria alkulukuja ja c ∈ ℤ. Jos a|c ja b|c, niin ab|c.

(2) Olkoon a ja b positiivisia kokonaislukuja ja syt(a, b) = 1. Jos a|c ja b|c, niin ab|c.

Todistus

(1) Tarkastellaan luvun c alkutekijähajotelmaa

Koska a|c ja b|c, niin Eukleideen lemmasta sekä alkutekijähajotelman yksikäsitteisyydestä seuraa, että a = rᵢ ja b = rⱼ joillakin indekseillä i, j = 1,...,k. Koska kyseessä on erisuuret alkuluvut a ja b, niin i ≠ j. Täten rᵢrⱼ = ab|c.

(2) Tarkastellaan lukujen a ja b alkutekijähajotelmia.

Koska syt(a, b) = 1, niin pᵢ ≠ qⱼ kaikilla indekseillä i = 1,...,k ja j = 1,...,h.

Kuten kohdassa 1, seuraa Eukleideen lemmasta sekä alkutekijähajotelman yksikäsitteisyydestä, että kaikkien alkulukujen indeksien

täytyy esiintyä luvun c alkutekijähajotelmassa

Täten ab|c.

Harjoituksia