Kongruenssi
Limma, Jenni (2022-12-21)
J. Limma
21.12.2022
© 2022 Jenni Limma. Tämä Kohde on tekijänoikeuden ja/tai lähioikeuksien suojaama. Voit käyttää Kohdetta käyttöösi sovellettavan tekijänoikeutta ja lähioikeuksia koskevan lainsäädännön sallimilla tavoilla. Muunlaista käyttöä varten tarvitset oikeudenhaltijoiden luvan.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-202212213863
https://urn.fi/URN:NBN:fi:oulu-202212213863
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.
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.
Kokoelmat
- Avoin saatavuus [36528]