MAA 11
Lukuteoriasta
Tällä kurssilla keskitymme kokonaislukujen jaollisuuteen ja kokonaislukuyhtälöiden ratkaisemiseen.
Jaollisuudessa keskeinen työväline on kongruenssi. Kaksi lukua ovat keskenään kongruentteja, jos ne ovat samalla tavalla jaollisia.
Esimerkiksi kun tarkastellaan jaollisuutta luvulla kolme, niin luvut 6 ja 9 ovat kongruentteja, koska kumpikin on jaollinen luvulla kolme. Samoin luvut 7 ja 10 ovat kongruentteja, koska kummallakin jakojäännökseksi jää yksi. Asia voidaan ilmaista myös seuraavasti: [[$ 6 \equiv 9 \pmod 3 $]] ja [[$ 7 \equiv 10 \pmod 3 $]].
Esim. selvitä jakojäännös, kun luku 978 + 5 jaetaan luvulla 8. Koska 9 ja 1 ovat kongruentteja, voidaan 9 korvata luvulla 1, eli [[$ 9^{78}+5 \equiv1^{78}+5 \equiv 1 + 5 \equiv 6 $]]. Jakojäännös on siis 6.
Kokonaislukuyhtälöillä ei aina ole ratkaisua. Esim. yhtälöllä 2x + 4y = 5 ei ole kokonaislukuratkaisua. Tämä johtuu siitä, että sekä 2 että 4 ovat parillisia lukuja, eikä niillä pystytä ilmaisemaan paritonta lukua 5.
Yhtälöllä 2x + 11y = 5 puolestaan on ratkaisu. Valitaan esim. y = -1 ja x = 8. Samoin yhtälöllä 2x + 11y = 391 on ratkaisu, niin myös yhtälöllä 2x+11y = 98123174. Itse asiassa yhtälön oikealla puolella voi olla mikä tahansa kokonaisluku ja yhtälö ratkeaa. Tämä johtuu siitä, että luvut 2 ja 11 ovat sopivasti erilaiset ja siksi niiden yhdistelmällä voidaan ilmaista mitä tahansa.
Lukujen erilaisuutta tutkitaan lukujen tekijöiden avulla. Kaikki luvut (paitsi alkuvut) voidaan esittää kahden tai useamman luvun tulona. Näitä tulon tekijöitä kutsutaan luvun tekijöiksi. Esimerkiksi luvun 12 tekijät ovat 1,2,3,4,6 ja 12. Tekijät 1 ja 12 eivät tosin ole kovin mielenkiintoisia, niitä kutsutaankin triviaalitekijöiksi.
Kahdella luvulla voi olla yhteisiä tekijöitä, kuten esimerkiksi luvuilla 12 ja 30. Lukuteorian kannalta mielenkiintoista on selvittää kahden luvun suurin yhteinen tekijä. Luvuille 12 ja 30 se on 6, merkitään syt(12,30) = 6. Vaikka symmetrian näkökulmasta onkin hienoa, että luvuilla on suuri yhteinen tekijä, niin se rajoittaa lukujen ilmaisuvoimaa. Luvuilla 12 ja 30 voidaan ilmaista vain luvun 6 monikertoja. Esimerkiksi yhtälöllä 12x + 30y = 601 ei ole ratkaisua, koska 601 ei ole luvun 6 monikerta. Ilmiötä voidaan vielä havainnollistaa seuraavalla esimerkillä.
[[$$ 30x + 12y = z \\ 6 \cdot 5x + 6 \cdot 2y = z \\ z = 6 \cdot (5x+2y) \\ z = 6n $$]]
Jos luvuilla ei ole muita yhteisiä tekijöitä kuin luku yksi, voidaan niiden avulla ilmaista mikä tahansa kokonaisluku. Esimerkikisi yhtälölle 2x + 11y = z löytyy aina ratkaisu, koska syt(2,11) = 1.
Jaollisuudessa keskeinen työväline on kongruenssi. Kaksi lukua ovat keskenään kongruentteja, jos ne ovat samalla tavalla jaollisia.
Esimerkiksi kun tarkastellaan jaollisuutta luvulla kolme, niin luvut 6 ja 9 ovat kongruentteja, koska kumpikin on jaollinen luvulla kolme. Samoin luvut 7 ja 10 ovat kongruentteja, koska kummallakin jakojäännökseksi jää yksi. Asia voidaan ilmaista myös seuraavasti: [[$ 6 \equiv 9 \pmod 3 $]] ja [[$ 7 \equiv 10 \pmod 3 $]].
Esim. selvitä jakojäännös, kun luku 978 + 5 jaetaan luvulla 8. Koska 9 ja 1 ovat kongruentteja, voidaan 9 korvata luvulla 1, eli [[$ 9^{78}+5 \equiv1^{78}+5 \equiv 1 + 5 \equiv 6 $]]. Jakojäännös on siis 6.
Kokonaislukuyhtälöillä ei aina ole ratkaisua. Esim. yhtälöllä 2x + 4y = 5 ei ole kokonaislukuratkaisua. Tämä johtuu siitä, että sekä 2 että 4 ovat parillisia lukuja, eikä niillä pystytä ilmaisemaan paritonta lukua 5.
Yhtälöllä 2x + 11y = 5 puolestaan on ratkaisu. Valitaan esim. y = -1 ja x = 8. Samoin yhtälöllä 2x + 11y = 391 on ratkaisu, niin myös yhtälöllä 2x+11y = 98123174. Itse asiassa yhtälön oikealla puolella voi olla mikä tahansa kokonaisluku ja yhtälö ratkeaa. Tämä johtuu siitä, että luvut 2 ja 11 ovat sopivasti erilaiset ja siksi niiden yhdistelmällä voidaan ilmaista mitä tahansa.
Lukujen erilaisuutta tutkitaan lukujen tekijöiden avulla. Kaikki luvut (paitsi alkuvut) voidaan esittää kahden tai useamman luvun tulona. Näitä tulon tekijöitä kutsutaan luvun tekijöiksi. Esimerkiksi luvun 12 tekijät ovat 1,2,3,4,6 ja 12. Tekijät 1 ja 12 eivät tosin ole kovin mielenkiintoisia, niitä kutsutaankin triviaalitekijöiksi.
Kahdella luvulla voi olla yhteisiä tekijöitä, kuten esimerkiksi luvuilla 12 ja 30. Lukuteorian kannalta mielenkiintoista on selvittää kahden luvun suurin yhteinen tekijä. Luvuille 12 ja 30 se on 6, merkitään syt(12,30) = 6. Vaikka symmetrian näkökulmasta onkin hienoa, että luvuilla on suuri yhteinen tekijä, niin se rajoittaa lukujen ilmaisuvoimaa. Luvuilla 12 ja 30 voidaan ilmaista vain luvun 6 monikertoja. Esimerkiksi yhtälöllä 12x + 30y = 601 ei ole ratkaisua, koska 601 ei ole luvun 6 monikerta. Ilmiötä voidaan vielä havainnollistaa seuraavalla esimerkillä.
[[$$ 30x + 12y = z \\ 6 \cdot 5x + 6 \cdot 2y = z \\ z = 6 \cdot (5x+2y) \\ z = 6n $$]]
Jos luvuilla ei ole muita yhteisiä tekijöitä kuin luku yksi, voidaan niiden avulla ilmaista mikä tahansa kokonaisluku. Esimerkikisi yhtälölle 2x + 11y = z löytyy aina ratkaisu, koska syt(2,11) = 1.