Lukuteoria 1 2023

Ajankohtaista 30.1.2023

Kursimateriaalin uudessa versiossa on korjattu tehtävä 3.21. Aiemmassa versiossa tällä kohdalla oli sama tehtävä kuin 3.14.

Ensimmäisen viikon harjoitustehtäviin on julkaistu ratkaisuja alla.

Sisältö

Kurssilla käsitellään luonnollisten lukujen ja kokonaislukujen jaollisuuteen liittyviä teemoja. Aluksi tarkastelemme kokonaislukujen joukon $\mathbb Z$ ja luonnollisten lukujen joukon $\mathbb N$ ja niiden laskutoimitusten ja järjestyksen perusasioita, erityisesti induktioperiaatetta, joka liittyy luonnollisten lukujen määritelmään. Induktioperiaate on tärkeä työkalu, jota käytetään usein, kun osoitetaan, että jokin väite pätee kaikilla luonnollisilla luvuilla.

Alkuvalmistelujen jälkeen käsittelemme kokonaislukujen jaollisuutta: jos $a,b,c\in\mathbb Z$ ja pätee $ab=c$, niin $c$ on jaollinen luvuilla $a$ ja $b$ ja luvut $a$ ja $b$ ovat luvun $c$ tekijöitä. Todistamme induktion avulla jakoyhtälön: Jos $a,b\in\mathbb Z$, $b\ne 0$, niin on yksikäsitteiset kokonaisluvut $q,r\in\mathbb Z$, joille pätee $a=qb+r$ ja $0\le r<|b|$. Jakoyhtälön ensimmäisenä sovelluksena osoitamme, että kiinnitetyllä kantaluvulla $b\ge 2$ mikä tahansa kokonaisluku $x\in\mathbb Z$ voidaan esittää muodossa $$x=\pm(a_0+a_1b+a_2b^2+\cdots+a_Nb^N)=\pm\sum_{k=0}^Na_kb^k $$ sopivilla luonnollisilla luvuilla $0\le a_1,\dots,a_N< b$ ja päädymme tarkastelemaan kokonaislukuja $b$-järjestelmässä, erityisesti kantaluvuilla $b=10$ ja $b=2$ (binaariluvut).

Tarkastelemme kokonaislukujen suurinta yhteistä tekijää ja sen selvittämistä Eukleideen algoritmin avulla. Tässä jakoyhtälö tulee jälleen käyttöön.

Luonnollinen luku $p\ge 2$ on alkuluku, jos sen ainoat tekijät luonnollisten lukujen joukossa ovat $1$ ja $p$. Tutustumme alkulukujen etsimiseen Erastotheneen seulan avulla.

Kurssin lopussa tutustumme kongruenssiin. Kokonaisluvut $a$ ja $b$ ovat kongruentteja modulo $q$, jos niiden erotus on jaollinen luonnollisella luvulla $q\ge 2$. Tarkastelemme ensimmäisen asteen kongruenssiyhtälöitä $ax\equiv b\mod q$ ja todistamme kiinalaisen jäännöslauseen, joka käsittelee tällaisista yhtälöistä koostuvien yhtälöryhmien ratkaisua.

Esitiedot

Lukemista

• G. Jones ja M. Jones: Elementary number theory, Springer, 1998 (Saatavana kirjaston kautta e-kirjana)

Luennot

Harjoitukset

Kunkin viikon tehtävät julkaistaan tässä. Numerot viittaavat luentomateriaaliin sisältyviin harjoitustehtäviin.

Contact information

Jouni Parkkonen
Matematiikan ja tilastotieteen laitos
PL 35
40014 Jyväskylän yliopisto