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.
Edellämainitusta lauseesta huolimatta alkulukujen etsiminen luku kerrallaan käy helposti työlääksi, kun halutaan etsiä suurempia alkulukuja. Alkulukuja voidaan etsiä helpommin niin kutsutulla Eratostheneen seulalla. Eratostheneen seula on kreikkalaisen filosofin Eratostheneksen kehittämä yksinkertainen algoritmi, jolla voidaan etsiä alkulukuja äärellisestä lukujoikosta.
Eratotheneksen seulan vaiheet
Halutaan määrittää alkuluvut väliltä 2,...,n.
(1) Listataan luvut väliltä 2,...,n.
(2) Listan ensimmäinen luku 2 on alkuluku. Poistetaan listalta kaikki lukua 2 suuremmat luvun 2 moninkerrat.
(3) Siirrytään listan seuraavaan jäljellä olevaan lukuun k. Luku k on alkuluku.
(4) Poistetaan listalta kaikki lukua k suuremmat luvun k moninkerrat.
(5) Toistetaan kohtia 3 ja 4 niin kauan, kun luku k on pienempi tai yhtäsuuri kuin luvun n neliöjuuri.
Eratosthene 276 eaa. - 194 eaa.
Kuva: Public Domain
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ä.
Seuraavaksi tutustumme Aritmetiikan peruslauseeseen, joka on yksi lukuteorian keskeisimpiä tuloksia. Lauseen perustan esitti ensimmäisenä kreikkalainen matemaatikko Eukleides teoksessaan Elementa (suom. Alkeet). Sittemmin eri tahot ovat ottaneet lauseeseen kantaa ja lopulta saksalainen matemaatikko Carl Friedrich Gauss esitti Aritmetiikan peruslauseen ensimmäisen täydellisen ja virheettömän todistuksen.
Oksyrhynkhoksesta löydetty papyruskatkelma Alkeista noin vuodelta 100.
Kuva: Public Domain
Carl Friedrich Gauss 1777 - 1855
Christian Albrecht Jensenin öljyvärimaalaus Gaussista
Kuva: Public Domain
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:
Esimerkki 4
Onko luku 211 alkuluku?
Ratkaisu
Kuten Eratostheneen seulan esittelyn yhteydessä osoitettiin: tutkittaessa onko positiivinen kokonaisluku n alkuluku vai ei, riittää tutkia onko luku n jaollinen jollakin positiivisella kokonaisluvulla, joka on pienempi tai yhtäsuuri kuin luvun n neliöjuuri. Koska Aritmetiikan peruslauseen nojalla jokainen positiivinen kokonaisluku voidaan jakaa alkutekijöihin, niin riittää tutkia onko luku n jaollinen jollakin alkuluvulla, joka on pienempi tai yhtäsuuri kuin luvun n neliöjuuri. Luvun 211 tapauksessa riittää siis tarkastella onko luku 211 jaollinen jollakin lukua
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.
Suurimman yhteisen tekijän muodostaminen alkutekijöistä
Tarkastellaan lukujen a, b ∈ ℕ alkutekijähajotelmia. Määritetään kaikki ne alkuluvut, jotka esiintyvät molempien lukujen a ja b alkutekijähajotelmissa. Jokaisen yhteisen alkutekijän eksponentiksi määräytyy esiintyvistä eksponenteista pienempi. Lukujen a ja b suurin yhteinen tekijä on näin valittujen alkulukujen potenssien tulo.
Pienimmän yhteisen moninkerran muodostaminen alkutekijöistä
Tarkastellaan yhä lukujen a, b ∈ ℕ alkutekijähajotelmia. Määritetään kaikki alkuluvut jotka esiintyvät alkulukuhajotelmissa. Jokaisen alkuluvun eksponentiksi määräytyy esiintyvistä eksponenteista suurempi. Lukujen a ja b pienin yhteinen moninkerta on näin valittujen alkulukujen potenssien tulo. Edellisessä kappaleessa esitetty pienimmän yhteisen moninkerran kaava perustuu tälle päättelylle.
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
Etsi Eratotheneksen seulalla kaikki alkuluvut väliltä 41-100.
Vihje
Esimerkki 2
2. Mitkä luvuista 330, 331, 332, 333, 334, 335, 336, 337, 338, 339 ovat alkulukuja?
Vihje
Esimerkki 4
3. a) Jaa luvut 29250 ja 139425 alkutekijöihin
b) Määritä lukujen 29250 ja 139425 suurin yhteinen tekijä ja pienin yhteinen moninkerta alkutekijähajotelmien avulla.
Vihje
Esimerkit 3 ja 5
4. Todista, että jos n∈ℤ ei ole jaollinen luvulla 3, niin yhtälö n² = 3m + 1 on tosi millä tahansa m∈ℤ.
Vihje
Summan ja erotuksen tulo -muistikaava.
5. Etsi lukujen 1221, 2849, 3367 ja 4995 suurin yhteinen tekijä.
YO 1883
Vihje
Etsi suurin yhteinen tekijä hyödyntämällä lukujen 1221, 2849, 3367 ja 4995 alkutekijähajotelmia.
6. Osoita, että kokonaisluku a on jaollinen luvuilla 16 ja 20 jos ja vain jos se on jaollinen luvulla 80.
Vihje
Todista väite molempiin suuntiin hyödyntämällä lukujen 16, 20 ja 80 alkutekijähajotelmia.
7. Todista, että ykköstä suurempi kokonailuku a on jonkin kokonaisluvun neliö, jos ja vain jos luvun a alkutekijähajotelman jokaisen alkutekijän eksponentti on parillinen.
Vihje
Todista väite molempiin suuntiin hyödyntämällä alkutekijähajotelmia.
8. Olkoon n parillinen kokonaisluku. Osoita, että luku n(n+1)(n+2) on jaollinen luvulla 24.
Vihje
Todista että luku n(n+1)(n+2) on jaollinen luvun 24 tekijöiden tulolla.
9. Todista, että luku, jonka m+n viimeistä numeroa, muodostavat 2ᵐ·5ⁿ :llä jaollisen luvun, itsekin on jaollinen sillä tulolla.
YO 1885A
Vihje
Jos luvun viimeinen numero on b ja sitä ennen tulevat numerot muodostavat luvun a, niin kokonaisuudessaan luku on a·10+b. Jos luvun 2 viimeistä numeroa muodostavat luvun b ja sitä ennen tulevat numerot muodostavat luvun a, niin kokonaisuudessaan luku on a·10²+b. Jatka päättelyä.
10. Etsi kaksi kokonaista lukua, joiden suurin yhteinen tekijä on 140 ja pienin yhteinen jaettava 9800. Määrää kaikki tehtävän ratkaisut.
YO Syksy 1910
Vihje
Kappaleen kohdat: "suurimman yhteisen tekijän muodostaminen alkutekijöistä" ja "pienimmän yhteisen moninkerran muodostaminen alkutekijöistä".