III.4.  Käänteisalkioista

Yhteenlaskulla muodostettu yhtälö voidaan aina ratkaista; ratkaisu on . Mutta muotoa olevalle yhtälölle ratkaiseminen ei ole yhtä selvää.

Tarkastellaanpa vaikka aluksi yhtälöä . Voisiko siitä ratkaista muuttujan ? Koska moduli 17 on nyt varsin pieni, on tietenkin helppo kokeilla kaikki luvut 0, 1, 2, …, 16 ja siten löytää kaikki ratkaisut. Mutta tämä menettely ei toimi, jos moduli on hyvin suuri.

Yleisemmin toimivan ratkaisumenetelmän johtamiseksi laskemmekin seuraavasti. Ensinnäkin Eukleideen algoritmin mukaisesti on

ja ,

josta voimme ratkaista luvun 1 muodossa

.

Siitä näkyy edelleen, että

.

Käytetään tätä tietoa sitten yhtälön ratkaisemiseen: Kerrotaan se ensin luvulla 7, jolloin saadaan yhtälö

.

Koskapa päti , onkin saatu, että

eli .

Tämä on siis ainoa ratkaisuehdokas (renkaassa ). Koska toisaalta

,

se myös kelpaa ratkaisuksi.

Yllä saatiin välituloksena, että , joka siis ilmoittaa, että alkio 7 on alkion 5 'käänteisalkio' renkaassa . Tämän löytämisessä taas oli olennaista, että .

Sanommekin yleisesti, että renkaassa alkio on alkion käänteisalkio, jos , merkitään . Alkiota sanotaan silloin myös kääntyväksi alkioksi. Symmetriasyistä myös alkio on kääntyvä ja sen käänteisalkio on eli . Erityisesti siten .

Seuraava lause ilmoittaa, millaisille alkioille käänteisalkioita löytyy.

Lause 3.4.1.

Renkaan () alkiolla on käänteisalkio täsmälleen silloin, kun luvut ja ovat keskenään jaottomat, ts. .

Todistus. Oletetaan ensin, että . Pitää löytää siis . Oletuksen perusteella joillekin kokonaisluvuille ja , joten

.

Tämän mukaan alkio kelpaakin alkion käänteisalkioksi.

Oletetaan sitten kääntäen, että jollekin alkiolle . Silloin eli jollekin kokonaisluvulle . Jos nyt , jakaa se luvut ja , ja siten myös summan . Niinpä välttämättä , mikä olikin osoitettava.

Esimerkki 3.4.2.

Renkaan kääntyvät alkiot ovat ne, jotka ovat suhteellisesti jaottomia luvun 10 kanssa, eli siis alkiot 1, 3, 7 ja 9. Lisäksi , ja , joten näiden käänteisalkiot ovat seuraavat: , , ja .

Ilman muuta pätee aina, että alkio 1, samoin kuin myös −1, on itsensä käänteisalkio, mutta edellisen esimerkin mukaan muullakin alkiolla voi olla tämä ominaisuus.

Esimerkki 3.4.3.

Kuvataan seuraavissa kuvioissa renkaiden , , ja kääntyvät alkiot. Kuvioissa nuolet osoittavat alkion käänteisalkion; ruksi alkion päällä taas merkitsee sitä, että kyseisellä alkiolla ei ole käänteisalkiota.

Tehtävä. Määrää renkaiden , ja kääntyvät alkiot ja niiden käänteisalkiot.

Jäännösluokkarenkaissa käänteisalkioita voidaan käyttää yhtälöiden ratkaisemisessa samaan tapaan kuin luvuilla käänteislukuja.

Lause 3.4.4.

Jos alkio on renkaan kääntyvä alkio, yhtälöllä on jokaisella renkaan alkiolla yksikäsitteinen ratkaisu .

Todistus. Jos , saadaan väitetty ratkaisu kertomalla tämä yhtälö alkiolla ja huomioimalla, että .

Toisaalta, jos , on , ts. yhtälö toteutuu.

Opiskelutehtävä 31. (Käänteisalkiot jäännösluokkarenkaassa)

Määrää kaikki ne renkaan alkiot, joilla on käänteisalkio, ja ilmoita kunkin käänteisalkio.

Vinkki tehtävään 31

Opiskelutehtävä 32. (Yhtälön ratkaiseminen jäännösluokkarenkaassa)

Ratkaise yhtälö renkaassa .

Vinkki tehtävään 32

Opiskelutehtävä 33. (Tulon nollasääntö jäännösluokkarenkaassa)

Keksi esimerkki renkaasta ja sen alkioista ja siten, että , mutta ja .

Vinkki tehtävään 33

Jos renkaan moduli on alkuluku, on siinä renkaassa paljon kääntyviä alkioita.

Seuraus 3.4.5.

Kun on alkuluku, on jokaisella renkaan nollasta eroavalla alkiolla käänteisalkio.

Todistus.

Väite seuraa siitä, että alkuluvulla on positiivisina tekijöinään vain ykkönen ja se itse, joten jokaiselle renkaan alkiolle , jolle , on . Lauseen 3.4.1 mukaan sellaisella alkiolla taas on käänteisalkio.

Lause 3.4.6. (Fermat'n pikkulause)

Kun on alkuluku, pätee kaikille kokonaisluvuille .

Todistus. Luvulle 0 väite pätee. Riittää sen jälkeen osoittaa, että , kun . Kaikilla näillä on edellisen seurauslauseen 3.4.5 mukaan käänteisalkio renkaassa .

Olkoon siis . Tarkastellaan lukuja

, , , …,

ja näiden tuloa

.

Kyseiset luvut ovat, paitsi tietysti kokonaislukuina, myös renkaan alkioina eri alkioita, sillä jos on , on eli . Siten ne ovat samat kuin alkiot 1, 2, …, , mahdollisesti vain eri järjestyksessä. Niinpä renkaassa pätee, että

.

Yhdistämällä yllä olevat tulon arvot saadaan yhtälö

.

Koska jokainen alkioista 1, 2, …, on kääntyvä, yllä oleva yhtälö voidaan supistaa muotoon . Olemme siis osoittaneet sen, mitä pitikin.

Esimerkissä 3.2.5 on todennettu Fermat'n pikkulause renkaassa .

Tehtävä. Todenna kokeilemalla, että Fermat'n pikkulause pätee renkaassa .

Fermat'n pikkulause on tärkeä perustulos lukuteoriassa. Sitä voidaan käyttää mm. sen testaamiseen, voiko joku luku olla alkuluku. Jos nimittäin , ei voi olla alkuluku. Fermat'n pikkulause on myös perusta seuraavassa pykälässä (RSA-menetelmä) käsiteltävälle salausmenetelmälle.

Pierre de Fermat (1601−1665) oli ranskalainen lakimies, joka harrasti matematiikkaa. Häntä pidetään eräänä todennäköisyyslaskennan pioneerina, mutta tunnetumpi hän on lukuisista lukuteorian tuloksistaan. Fermat'n suuren lauseen (tai viimeisen lauseen) nimellä kulkee eräs hänen väittämistään, jonka mukaan yhtälöllä ei ole nollasta eroavia kokonaislukuratkaisuja, kun . Fermat ilmoitti aikanaan muistiinpanojensa reunahuomautuksena todistaneensa väittämän, mutta reunatila ei vain riittänyt sen esittämiseen. On syytä epäillä tätä, koska monet jälkipolvetkaan eivät lukuisista yrityksistä huolimatta ole pystyneet todistamaan tai kumoamaan väitettä. Väittämän todistusyrityksiä on vuosisatojen kuluessa ollut lukuisia ja ne ovat johtaneet monien matematiikan alueiden kehitykseen, muidenkin kuin lukuteorian. Todistuksen väittämälle esitti lopultakin englantilainen Andrew Wiles vuonna 1993 ja korjattuna vuonna 1994. Tästä uudentyyppisestä ja Wilesin yli seitsemän vuotta kehittämästä todistuksesta eivät tähänastiset tarkistajat ole löytäneet virhettä ja todistus onkin yleisesti hyväksytty oikeaksi.

[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]