Kiinalainen jäännöslause ja polynomikongruenssit

Abstract

Tutkielma kuuluu matematiikassa lukuteorian osa-alueeseen. Lukuteoria tarkastelee erityisesti positiivisten kokonaislukujen ominaisuuksia, joista tärkein on jaollisuus. Sen lisäksi tarkastellaan myös alkulukuja. Jaollisuuden avulla voidaan edelleen määritellä kongruenssi, jonka ominaisuuksiin tämä tutkielma pitkälti painottuu. Kongruenssilla on matematiikassa useita hyödyllisiä sovelluksia esimerkiksi tietojen salausta käsittelevässä kryptografiassa, mutta myös arkitodellisuudessa. Tässä tutkielmassa perehdytään kongruenssin ja polynomikongruenssien teoreettiseen taustaan ja esitellään eräs menetelmä muotoa f(x) ≡ 0 modulo m olevien polynomikongruenssien ratkaisemiseen. Apuna käytetään kiinalaista jäännöslausetta sekä Henselin lemmaa. Tutkielma nojaa vahvasti kirjallisuuteen, jonka pohjalta lauseet on esitetty. Lukijalta odotetaan jonkin verran lukuteorian alkeiden tuntemusta, vaikkakin työn kannalta keskeisimpiä käsitteitä on esitelty tutkielman alussa myöhempiä lauseita ja todistuksia varten. Kiinalainen jäännöslause on kätevä työkalu arkistenkin matemaattisten ongelmien ratkaisemisessa. Tunnettu esimerkki lauseen soveltamisesta on vanha kiinalainen ongelma, jossa pyritään ratkaisemaan sotilaiden lukumäärä, kun tiedetään sen jakojäännökset eri luvuilla jaettaessa. Näistä tiedoista muodostetaan kongruenssiryhmä, joka voidaan ratkaista kiinalaisen jäännöslauseen avulla. Polynomikongruenssi f(x) ≡ 0 modulo m voidaan ratkaista suoraan kiinalaisen jäännöslauseen avulla, jos modulona oleva luku m on yhdistetty luku, joka voidaan jakaa pareittain suhteellisiin alkulukuihin. Jos taas luku m on muotoa p^2, missä p on alkuluku, niin ratkaisu löydetään Henselin lemman avulla etsimällä ensin ratkaisu modulo p. Nostoperiaatteen avulla saadaan ratkaisut modulo p^k, kun tiedetään ratkaisut modulo p^(k−1). Näitä eri tapauksia käsitellään tutkielman lopussa havainnollistavin esimerkein.