[Etusivu] [Sisältö] [Luku I II III IV V VI] [Hakemisto]
[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]

III.1. Jäännösluokat

Ajatellaanpa kysymyksiä "mitä kello on sadan tunnin kuluttua?" tai "mikä viikonpäivä on tuhannen yön jälkeen?" Miten saamme vastauksen näihin?

Edellisessä tapauksessa laskemme kuinka monta vuorokautta eli 24 tunnin jaksoa sataan tuntiin mahtuu ja katsomme, mitä jää yli. Koska , kello siirtyy neljä tuntia eteenpäin.

Jälkimmäiseen kysymykseen vastaamme samaan tapaan. Koska viikossa on seitsemän päivää ja , on tuhannen yön jälkeen edetty kuusi viikonpäivää eteenpäin eli silloin on laskentahetkeä edeltävä viikonpäivä.

Kummassakaan tapauksessa emme loppupäätelmässä tarvitse tietoa, montako vuorokautta tai viikkoa kyseiseen ajanjaksoon on mahtunut, vaan vastauksen antamiseen riittää tietää, mitä jäi yli.

Tarkastellaankin seuraavassa lähemmin kiinteälle jakajalle jakoyhtälössä esiintyviä jakojäännöksiä. Kun , jakoyhtälön mukaan on

joillekin ja , missä . Tällaisessa tilanteessa luvut ja eroavat toisistaan luvun monikerralla, ts. erotus on jaollinen luvulla .

Yleisesti sanotaan, että kokonaisluvulle kokonaisluvut ja ovat (keskenään) kongruentteja modulo , jos moduli jakaa niiden erotuksen ; merkitään silloin, että . Siis

Tälle kongruenssikäsitteelle on varsin helppo todeta seuraavat ominaisuudet:

(a) ,

(b) jos , niin ,

Relaatioita, jotka toteuttavat nämä kolme ehtoa (nimiltään refleksiivisyys, symmetrisyys ja transitiivisuus), sanotaan yleisemmin ekvivalenssirelaatioiksi. Tällaisille relaatioille on ominaista, että ne määräävät osituksen siihen joukkoon, jossa ne on määritelty. Tämä taas tarkoittaa sitä, että keskenään ekvivalentit alkiot muodostavat erillisiä osajoukkoja, joiden yhdiste on koko määrittelyjoukko.

Esimerkki 3.1.1.

Kongruenssit ja pätevät, sillä ja . Sen sijaan , sillä .

Opiskelutehtävä 23. (Kongruentit luvut)

Määrää kaikki ne kokonaisluvut väliltä , jotka toteuttavat ehdon .

Vinkki tehtävään 23

Opiskelutehtävä 24. (Lukujen kongruenttisuus)

Päättele seuraavista, päteekö se vai eikö se päde?

(a) ,

(b) ,

(d) ,

(e) .

Vinkki tehtävään 24

Opiskelutehtävä 25. (Kongruenssiyhtälöiden ratkaiseminen)

Etsi kaikki kokonaisluvut , jotka toteuttavat annetun ehdon:

(a) ,

(b) .

Vinkki tehtävään 25

Kun kokonaisluvulle on jakoyhtälön mukaisesti , luku jakaa erotuksen , ts. on kongruentti (modulo ) luvun kanssa. Jokainen kokonaisluku on siten kongruentti (modulo ) jonkin luvun , , kanssa.

Keskenään kongruenteista luvuista saadaan aikaan seuraavat joukot, ns. jäännösluokat (modulo ):

…

Muita jäännösluokkia ei olekaan, sillä

, , jne.

Huomaa, että erikoisesti täsmälleen silloin, kun on jaollinen luvulla .

Merkitään näiden joukkojen muodostamaa joukkoa symbolilla , siis

Nämä osajoukot muodostavat siis erään kokonaislukujen osituksen, eli sen jaon erillisiin osajoukkoihin. Joukkoa tullaan sanomaan jäännösluokkarenkaaksi (ks. lauseen 3.2.3 jälkeinen selitys).