JultikaUniversity of Oulu repository

Tiivistelmä

LUK-tutkielmassa käsitellään kongruenssia. Kongruenssin avulla tutkitaan jakojäännöksiä. Näitä jakojäännöksiä voidaan laskea myös lineaarisen kongruenssin avulla. Lineaarisessa kongruenssissa on yksi kongruenssi, jossa on yksi muuttuja x. Lineaarisen kongruenssin voi ratkaista joko kokeilemalla, Diofantoksen yhtälön avulla tai etsimällä ratkaisut Eukleideen algoritmia käyttäen.

Diofantoksen yhtälöksi sanotaan yhtälöä, jossa on kaksi muuttujaa, mutta vain yksi yhtälö. Diofantoksen yhtälössä etsitään siis kokonaislukuratkaisua. Kun kongruensseja on monta eli kyseessä on kongruenssiyhtälöryhmä, jossa on vain yksi muuttuja x ja kongruensseilla on eri modulot, voidaan ratkaisun löytämiseen käyttää Kiinalaista jäännöslausetta. Kiinalaisessa jäännöslauseessa on kuitenkin tärkeää, että kongruenssiyhtälöryhmän kongruenssien modulot ovat pareittain keskenään jaottomia. Kongruenssiyhtälöryhmälle löytyy tällöin yksikäsitteinen ratkaisu modulo M, joka on kongruenssien modulojen tulo.

Kongruensseissa voidaan hyödyntää myös alkulukuja. Kun kongruenssissa on mukana kertomia, Wilsonin lause on tällöin hyödyllinen, sillä sen avulla saadaan myös isoille kertomille helposti ratkaisu. Wilsonin lause kertoo, että jos p on alkuluku, niin luvun (p-1)! on kongruentti -1 kanssa modulo p. Kongruensseissa, joissa on eksponentteja ja varsinkin isoja eksponentteja, voidaan hyödyntää Fermat’n pientä lausetta. Fermat’n pienen lauseen mukaan alkuluvuilla p ja kokonaisluvuilla a, jotka ovat keskenään jaottomia, on voimassa kongruenssi, että luku ap-1 on kongruentti 1 kanssa modulo p.