Primitiiviset juuret ja niiden sovellukset

Abstract

Tässä työssä tutkitaan primitiivisiä juuria ja niiden erilaisia sovelluksia. Sovelluksissa käydään läpi rationaalilukujen desimaaliesityksen ominaisuuksia, näennäissatunnauslukugeneraattorin teoriaa ja indeksiaritmetiikkaa.

Aluksi työssä käydään läpi olennaisia määritelmiä, esimerkkejä ja lauseita, joiden jälkeen määritellään primitiivinen juuri. Primitiivinen juuri on yksiköiden ryhmän Un virittävä alkio. Tällöin yksiköiden ryhmä on syklinen. Hyödyllisen apulauseen avulla voidaan testata, onko jokin alkio primitiivinen juuri. Seuraavaksi tutkitaan syklisiä yksiköiden ryhmiä ja todistetaan, että alkuluvuille p löytyy aina primitiivinen juuri yksiköiden ryhmästä Up. Lisäksi huomataan syklisten ryhmien välisiä yhteyksiä ja määritetään primitiivisten juurien määrä Eulerin funktion avulla.

Primitiivisten juurten sovelluksissa tutkitaan rationaalilukujen desimaaliesityksien jaksollisuutta. Ensin selvitetään, milloin rationaaliluku on päättyvä. Huomataan, että jos luvun 1/n desimaaliesitys on päättymätön, niin se on jaksollinen ja sen jakson pituus on korkeintaan n − 1. Lisäksi, jos 10 on primitiivinen juuri modulo n, niin desimaaliesityksen pituus on kertaluku ϕ(n).

Tämän jälkeen tarkastellaan näennäissatunnaislukuja tuottavaa menetelmää ja primitiivisten juurten käyttöä näennäissatunnaisgeneraattorissa. Hyödyllisen lauseen avulla voidaan löytää primitiivisen juuren potensseista vielä suurempia primitiivisiä juuria, jolloin näennäissatunnaislukujen löytäminen vaikeutuu. Lopuksi hyödynnetään vielä primitiivisiä juuria määrittelemään indeksi, jota voidaan hyödyntää kongruenssiyhtälöiden ratkaisemisessa sekä määrittäessä onko kongruenssiyhtälöllä ratkaisua ja kuinka monta niitä on.