Tehtävän 31 ratkaisu

Kääntyviä alkioita voi etsiä joko kokeilemalla tai hyödyntämällä lauseen 3.4.1 antamaa tietoa, jonka mukaan renkaan alkiolla a on käänteisalkio täsmälleen silloin, kun luvut a ja n ovat keskenään jaottomat eli . Hyödynnetään tätä. Koska , kun , niin renkaan kääntyvät alkiot ovat 1, 5, 7 ja 11.

Käänteisalkioitten määrääminen:

Ratkaisutapa 1. Modulin 12 ollessa pieni voidaan alkioiden 1, 5, 7 ja 11 käänteisalkiot etsiä yksinkertaisesti kokeilemalla. Kullekin alkiolle täytyy löytää joku renkaan alkio siten, että alkion ja sen käänteisalkion tulo renkaassa on 1.

Kääntyvän alkion käänteisalkio on myös kääntyvä. Siis kääntyville alkioille pätee, että niiden käänteisalkiot kuuluvat joukkoon . Huomaa, että käänteisalkion ei tarvitse olla eri alkion. Alkio 1 onkin aina oma käänteisalkionsa, sillä . Etsitään loput käänteisalkiot:

Luvun 5 käänteisalkio: Alkio 1 ei voi olla alkion 5 käänteisalkio. Kokeilemalla seuraavalla mahdollisella renkaan alkiolla 5 huomataan, että . Siten myös alkio 5 on itse oma käänteisalkionsa, .

Samaan tapaan jatkamalla havaitaan, että myös alkiot 7 ja 11 ovat omia käänteisalkioitaan, sillä ja . Näin ollen ja .

Huomautus. Renkaassa käytetään sanan luku sijasta sanaa alkio.

Ratkaisutapa 2. Jos kokeileminen ei syystä tai toisesta onnistu, voidaan kääntyvän alkion a käänteisalkio lauseen 3.4.1 avulla etsiä luvun suurimman yhteisen tekijän monikertasummaesityksen avulla. Tehdään näin alkioille 5 ja 7.

Luvulle 5 on syt(12, 5) = 1. Eukleideen algoritmin mukaan on

Paluualgoritmia käyttämällä saadaan suurin yhteinen tekijä 1 esitettyä lukujen 12 ja 5 monikertasummana:

Näin ollen alkion käänteisalkio ko. renkaassa on .

Luvulle 7 on syt(12, 7) = 1 ja

joten paluualgoritmia käyttämällä saadaan syt esitettyä lukujen 12 ja 7 monikertasummana:

Nyt −5 on alkion 7 käänteisalkio. Koska , voidaan valita käänteisalkiota vastaavasta ekvivalenssiluokasta jokin toinen edustaja. Koska −5 + 12 = 7, valitaan edustajaksi luku 7 ja näin siis luku 7 on itsensä käänteisalkio.

Huomautus. Joskus tämä paluualgoritmista saatava kerroin voi olla negatiivinen, kuten edellä alkion 7 käänteisalkiota etsittäessä käy. Tämä ei kuitenkaan haittaa, sillä kyseiset ratkaisut kuuluvat kuitenkin samaan jäännösluokkaan ja näin käänteisalkioksi voidaan valita mikä tahansa edustaja kyseisestä jäännösluokasta.

Tässä tehtävässä siis kukin kääntyvä alkio on oma käänteisalkionsa. Näin ei tietenkään aina käy.

Kääntyvät alkiot ja niiden käänteisalkiot kuvana, missä nuoli osoittaa käänteisalkion:

Lisätietoja. Käänteisalkioita tarvitsee itse asiassa etsiä vain renkaan puolikkaasta, sillä toinen puoli menee symmetrisesti käyttämällä merkin vaihtoa apuna. Esimerkiksi modulo 12 on ja , joten ja .

[Opiskelutehtävä 31] [Vinkki tehtävään 31]

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