Äärelliset kunnat ja niiden sovelluksia

A¨arelliset kunnat ja niiden sovelluksia ¨

Salla Pehkonen

Matematiikan pro gradu -tutkielma

Jyv¨askyl¨an yliopisto

Matematiikan ja tilastotieteen laitos Kes¨a 2019

i

Tiivistelm¨a: Salla Pehkonen A¨¨arelliset kunnat ja niiden sovelluksia, matematiikan pro gradu -tutkielma, 47 s., Jyv¨askyl¨an yliopisto, Matematiikan ja tilastotieteen laitos, kes¨a 2019.

T¨ass¨a tutkielmassa k¨asitell¨a¨an ¨a¨arellisi¨a kuntia ja tarkastellaan joitakin niiden so- velluksia salakirjoituksiin liittyen. Aluksi m¨a¨aritell¨a¨an polynomit sek¨a polynomin juu- ri ja tutkitaan niiden erilaisia ominaisuuksia. Lis¨aksi todistetaan ensimm¨aisen luvun ehk¨a t¨arkein lause, polynomien jakoyht¨al¨o, jota k¨aytet¨a¨an my¨ohemmin muun muassa polynomien jaollisuuden tarkastelussa. Jaollisuuden yhteydess¨a k¨asitell¨a¨an polyno- mien suurinta yhteist¨a tekij¨a¨a, jaottomia polynomeja sek¨a juurien monikertaisuutta.

Seuraavaksi m¨a¨aritell¨a¨an, mit¨a ovat ¨a¨arelliset kunnat ja tarkastellaan niiden ole- massaoloa sek¨a sit¨a, miten ja mill¨a ehdoilla niit¨a voidaan muodostaa, esimerkiksi mil- lainen on oltava alkioiden lukum¨a¨ar¨a ¨a¨arellisessa kunnassa. M¨a¨aritell¨a¨an my¨os ¨a¨arel- lisiin kuntiin liittyvi¨a muita k¨asitteit¨a ja niiden ominaisuuksia. Lis¨aksi tarkastellaan erilaisia ¨a¨arellisiin kuntiin liittyvi¨a kuvauksia, kuten Eulerin φ-funktio, joka kertoo alkioiden lukum¨a¨ar¨an tietylle kertaluvulle. Er¨as t¨arkeimmist¨a toisen luvun tuloksista on, ett¨a jokaiselle luvulle q, joka on muotoa pⁿ, miss¨ap on alkuluku jan positiivinen kokonaisluku, voidaan muodostaa yksi ja vain yksi ¨a¨arellinen kunta.

Tutkielman kaksi viimeist¨a lukua liittyv¨at ¨a¨arellisten kuntien soveltamiseen. Kol- mannessa luvussa m¨a¨aritell¨a¨an salakirjoituksen periaatteet ja k¨asitteet sek¨a esitell¨a¨an joitakin tunnettuja salausmenetelmi¨a, kuten RSA. Tarkastellaan my¨os toistetun ne- li¨oinnin ideaa, joka siis nopeuttaa huomattavasti luvun bⁿ modm laskemista, kun lukun on todella suuri.

Viimeisess¨a luvussa keskityt¨a¨an yhteen t¨arkeimp¨a¨an ¨a¨arellisiin kuntiin liittyv¨a¨an ongelmaan, nimitt¨ain diskreettiin logaritmiin. Diskreetti logaritmi nousee ¨a¨arellisten kuntien yhteydess¨a oleelliseksi ongelmaksi, kun k¨asitell¨a¨an salausj¨arjestelmi¨a. Esimer- kiksi Diffien ja Hellmanin avaintenvaihdossa ja ElGamalin salausj¨arjestelm¨ass¨a hy¨o- dynnet¨a¨an t¨at¨a ongelmaa. Lis¨aksi tarkastellaan er¨ast¨a algoritmia, joka on kehitelty diskreettien logaritmien ratkaisemiseksi ¨a¨arellisiss¨a kunnissa. T¨at¨a algoritmia varten todistetaan my¨os t¨arke¨a kiinalainen j¨a¨ann¨oslause.

Sis¨ alt¨ o

Johdanto 1

Luku 1. Polynomit 3

1.1. M¨a¨aritelm¨a 3

1.2. Jaollisuus 7

Luku 2. A¨¨arelliset kunnat 13

2.1. M¨a¨aritelmi¨a 13

2.2. A¨¨arellisen kunnan alkiot 17

2.3. Frobeniuksen automorfismi 18

2.4. Eulerinφ-funktio 20

2.5. Olemassaolo ja yksik¨asitteisyys 25

Luku 3. Salakirjoitus 35

3.1. Toistettu neli¨ointi 35

3.2. Salausj¨arjestelm¨a 35

3.3. Julkinen avain 37

3.4. RSA 37

Luku 4. Diskreetti logaritmi 41

4.1. M¨a¨aritelm¨a 41

4.2. Diffien ja Hellmanin avaintenvaihto 42

4.3. ElGamalin salausj¨arjestelm¨a 43

4.4. Digitaalinen allekirjoitus 43

4.5. Diskreetin logaritmin etsiminen ¨a¨arellisiss¨a kunnissa 44

Kirjallisuutta 47

i

Johdanto

T¨am¨an kirjoitelman tarkoituksena on tutkia ¨a¨arellisi¨a kuntia ja erilaisia mene- telmi¨a, joissa niit¨a voi soveltaa. ¨A¨arelliset kunnat luovat matemaattisen pohjan sa- lakirjoituksiin ja siksi t¨aytyy ensin m¨a¨aritell¨a ja tarkastella niiden ominaisuuksia.

A¨¨arellisi¨a kuntia voidaan muodostaa tietynlaisten kokonaislukujen lis¨aksi my¨os po- lynomien avulla. Polynomeista muodostetut ¨a¨arelliset kunnat k¨aytt¨aytyv¨at samalla tavalla kuin kokonaisluvuista muodostetut, mink¨a takia polynomien ominaisuudet m¨a¨aritell¨a¨an tarkasti. T¨ass¨a tutkielmassa tarkastellaan k¨asitteit¨a algebran kautta.

Siisp¨a my¨os polynomit m¨a¨aritell¨a¨an algebran s¨a¨ant¨ojen mukaan, eik¨a niit¨a ajatella funktioina. Lukijan oletetaan siis tuntevan algebran ja kuntateorian perusk¨asitteet.

Salausj¨arjestelmiss¨a k¨aytet¨a¨an usein lukuteorian k¨asitteit¨a ja menetelmi¨a, mutta t¨ass¨a tutkielmassa pyrit¨a¨an tarkastelemaan j¨arjestelmi¨a algebran n¨ak¨okulmasta. Lu- vussa kolme keskityt¨a¨an enemm¨an salausj¨arjestelmien ja salakirjotuksen perusideaan ja k¨asitteisiin, joiden pohjalta voidaan rakentaa toimivia salausmenetelmi¨a. Luvussa esitell¨a¨an my¨os ehk¨a tunnetuin julkisen avaimen salausj¨arjestelm¨a RSA. Kun salaus- j¨arjestelmien idea on selv¨a, voidaan tarkastella erilaisia salausmenetelmi¨a, jotka kaikki perustuvat yhteen suureen matemaattiseen ongelmaan, joka on diskreetin logaritmin ongelma.

Ongelma piilee siin¨a, ett¨a esimerkiksi toistetun neli¨oinnin avulla pysyt¨a¨an melko helposti ja nopeasti ratkaisemaan potenssilaskuja suurillekin luvuille, mutta toiseen suuntaan on vaikeampi p¨a¨ast¨a. Siisp¨a hyvin k¨arjistestysti, jos viesti salataan eritt¨ain suuren potenssin avulla, niin salausta on l¨ahes mahdoton purkaa ilman avainta, sill¨a potenssin ratkaisu diskreetin logaritmin avulla ei onnistu. T¨at¨a ongelmaa hy¨odyn- t¨avi¨a menetelmi¨a ovat esimerkiksi Diffien ja Hellmanin avaintenvaihto, ElGamalin salausj¨arjestelm¨a ja digitaalinen allekirjoitus. Luvussa nelj¨a on yksi esimerkki, jos- sa on k¨aytetty apuna Maxima-tietokoneohjelmaa tulosten laskemiseen. Ohjelmassa k¨aytetyt laskumenetelm¨at ja komennot eiv¨at ole oleellisia esimerkin kannalta, mut- ta voidaan huomata, ett¨a jo noinkin pienill¨a luvuilla k¨asin laskeminen olisi todella haastavaa. Todellisuudessa salausj¨arjestelmiss¨a k¨aytet¨a¨an todella suuria lukuja, sill¨a kuntien alkioiden lukum¨a¨ar¨at ovat noin suuruusluokkaa 10⁵⁰⁰.

LUKU 1

Polynomit

1.1. M¨a¨aritelm¨a

T¨ass¨a kappaleessa k¨ayd¨a¨an l¨api polynomien m¨a¨aritelm¨a ja perusominaisuuksia, kuten esimerkiksi polynomien juuriin liittyv¨at ominaisuudet. Kappaleessa k¨asitell¨a¨an my¨os polynomien jakoyht¨al¨o, joka on ehk¨a t¨arkein tulos, joka liittyy polynomeihin, koska siita saadaan lukuisia seurauksia. L¨ahteen¨a t¨ass¨a kappaleessa on k¨aytetty teosta [2].

Olkoon F kunta. T¨all¨oin merkinn¨all¨a

f(t) = a_ntⁿ+· · ·+a₀

tarkoitetaan yleens¨a funktiota kunnastaF itselleen. Mutta kun tarkastellaan polyno- meja, ei tarvitse ajatella, ett¨af olisi funktio. Polynomeille t¨aytyy kuitenkin m¨a¨aritell¨a laskutoimitukset. Esimerkiksi, jos a0, . . . , an ∈F ja b0, . . . , bm ∈F, niin merkit¨a¨an

f(t) = a_ntⁿ+· · ·+a₀ g(t) = b_mt^m+· · ·+b₀. Nyt jos n > m, niin olkoon b_j = 0, kun j > m, jolloin

g(t) = 0tⁿ+· · ·+b_mt^m+· · ·+b₀. T¨all¨oin m¨a¨aritell¨a¨an summaksi

(1.1) (f +g)(t) = (a_n+b_n)tⁿ+· · ·+ (a₀+b₀).

Josc∈F, niin

(cf)(t) = ca_ntⁿ+· · ·+ca₀ M¨a¨aritell¨a¨an tulo

(f g)(t) = (a_nb_m)t^n+m+· · ·+a₀b₀. Nyt voidaan kuitenkin merkit¨a

(f g)(t) =c_n+mt^n+m+· · ·+c₀, miss¨a

ck =

k

X

i=0

aibk−i =a0bk+a1bk−1+· · ·+akb0. (1.2)

T¨am¨a merkint¨a kertoimelle ck saadaan, kun yhdistet¨a¨an termit a_itⁱbk−it^k−i =a_ibk−it^k.

Nyt ollaan m¨a¨aritelty yhteen- ja kertolasku polynomeille yht¨al¨oiden (1.1) ja (1.2) mukaan. Ei ole merkityst¨a, kuuluvatko kertoimet ai ja bj kuntaan F, kunhan ne noudattavat aritmetiikan s¨a¨ant¨oj¨a eli kuuluvat kommutatiiviseen renkaaseen. Viel¨a t¨aytyy kuitenkin m¨a¨aritell¨a, mit¨a muuttuja t merkitsee polynomissa.

3

4 1. POLYNOMIT

Olkoon R kommutatiivinen rengas. Olkoon Pol_R joukko ¨a¨arett¨omi¨a vektoreita (a₀, a₁, a₂, . . . , a_n, . . .),

miss¨a a_n ∈R siten, ett¨a vain ¨a¨arellinen m¨a¨ar¨a a_n6= 0. Siisp¨a vektori on (a₀, a₁, . . . , a_d,0,0,0, . . .),

miss¨a nollat jatkuvat ¨a¨arett¨omiin oikealle. Joukon Pol_R tekij¨oit¨a kutsutaan polyno- meiksi yli renkaanR. Tekij¨oit¨aa₀, a₁, . . . kutsutaan polynomin kertoimiksi. Josa_j = 0 kaikillaj, niin kutsutaan polynomia nollapolynomiksi (0,0,0, . . .).

M¨a¨aritell¨a¨an yhteenlasku kuten edell¨a yht¨al¨oss¨a (2.1), jolloin Pol_R on additiivinen ryhm¨a. Seuraavaksi m¨a¨aritell¨a¨an kertolasku vastaavasti, toisin sanoen jos

f = (a₀, a₁, . . .) ja g = (b₀, b₁, . . .),

ovat polynomeja, joiden kertoimet ovat kommutatiivisessa renkaassa R, niin niiden tulo m¨a¨aritell¨a¨an

f g= (c₀, c₁, . . .), miss¨a

c_k=

k

X

i=0

a_ibk−i = X

i+j=k

a_ib_j. Siisp¨a Pol_R on kommutatiivinen rengas.

Valitaan muuttujaksi t. T¨all¨oin

t= (0,1,0,0, . . .).

Muuttujalla t on siis kerroin 0 kohdassa 0, kerroin 1 kohdassa 1 ja loput kertoimista ovat nollia. T¨all¨oin muuttuja t korotettuna potenssiin n on

tⁿ = (0,0, . . . ,0,1,0,0, . . .),

miss¨a kerroin 1 on kohdassa n. Toisin sanoen tⁿ on vektori, jollan:s komponentti on 1 ja kaikki muut komponentit ovat nollia.

Polynomia voidaan my¨os kertoa renkaan R alkiolla, jolloin jos a ∈ R ja f = (a₀, a₁, . . .), niin

af = (aa₀, aa₁, , . . .).

M¨a¨aritelm¨a 1.1.1. Olkoon F kunta ja f polynomi f(t) =a_ntⁿ+· · ·+a₀,

miss¨a a_j ∈ F kaikilla j = 0,1, . . . , n. T¨all¨oin alkioita a_j kutsutaan polynomin f kertoimiksi. Lis¨aksi jos n on suurin kokonaisluku siten, ett¨a an 6= 0, niin sanotaan, ett¨a n on polynomin f aste ja merkit¨a¨an degf = n. M¨a¨aritell¨a¨an nollapolynomille g(t) = 0, ett¨a degg :=−∞. Sanotaan my¨os, ett¨aa_non polynominf p¨a¨akerroinja a₀ on polynomin f vakiotermi.

Lause1.1.2. Olkootf jag polynomeja, joiden kertoimet ovat kunnassaF. T¨all¨oin deg(f g) = degf+ degg.

1.1. M ¨A ¨ARITELM ¨A 5

Todistus. Olkoot

f(t) =antⁿ+· · ·+a0 ja g(t) = bmt^m+· · ·+b0,

miss¨a a_n 6= 0 ja b_m 6= 0. T¨all¨oin, kun kerrotaan polynomit f ja g, niin huomataan, ett¨a

f(t)g(t) =a_nb_mt^n+m+. . .

ja a_nb_m 6= 0, joten degf g =n+m = degf + degg.

Seuraavaksi m¨a¨aritell¨a¨an, mik¨a on polynomin juuri ja millaisia ominaisuuksia sill¨a on.

M¨a¨aritelm¨a1.1.3. OlkootF kunta,α ∈F jafpolynomi kunnassaF. Sanotaan, ett¨a α on polynomin f juuri, jos f(α) = 0

Lause 1.1.4. Olkoon f polynomi kunnassa F ja f(t) =antⁿ+· · ·+a0.

Oletetaan, ett¨a polynomin f aste on n ≥ 0, joten f 6= 0. T¨all¨oin polynomilla f on enint¨a¨an n juurta.

T¨am¨an lauseen todistukseen tarvitaan lemma.

Lemma 1.1.5. Olkoot f polynomi yli kunnan F ja α ∈ F. T¨all¨oin on olemassa alkiot c₀, . . . , c_n∈F siten, ett¨a

f(t) = c₀+c₁(t−α) +· · ·+c_n(t−α)ⁿ.

Todistus. Merkit¨a¨an polynominf lausekkeessa muuttujaat arvollat =α+ (t− α). Nyt jokaiselle k ∈Z, jolle 1≤k≤n, saadaan binomikertoimien avulla

t^k = (α+ (t−α))^k=α^k+ k

1

α^k−1(t−α) +· · ·+ k

k−1

α(t−α)^k−1+ (t−α)^k ja n¨ain ollen

a_kt^k=a_kα^k+a_k k

1

α^k−1(t−α) +· · ·+a_k k

k−1

α(t−α)^k−1+a_k(t−α)^k voidaan kirjoittaa termin (t−α) potensseina, jotka on kerrottu kunnan F alkioilla.

Kun otetaan summaPn

k=0a_kt^kniin saadaan polynominf lauseke haluttuun muotoon.

Lauseen 1.1.4 todistus. Lemmassa 1.1.5 saadaan, ett¨a f(α) = c₀. Siisp¨a jos f(α) = 0, niin c₀ = 0 ja voidaan merkit¨a

f(t) = (t−α)h(t), miss¨a

h(t) =d₁+d₂(t−α) +· · ·+d_n(t−α)ⁿ⁻¹,

joillekin d₁, d₂, . . . , d_n ∈F. Tehd¨a¨an antiteesi ja oletetaan, ett¨a polynomilla f onkin n+ 1 eri juurta kunnassa F ja merkit¨a¨an niit¨a α₁, . . . , α_n+1.

Olkoon α =α1. T¨all¨oin αi−α1 6= 0 kaikilla i = 2,3, . . . , n+ 1. Koska oletuksen mukaan

0 = f(α_i) = (α_i−α₁)h(α_i),

6 1. POLYNOMIT

niin on oltava h(α_i) = 0 kaikille i= 2,3, . . . , n+ 1. Tekem¨all¨a induktion huomataan,

ett¨a t¨am¨a on mahdotonta ja saadaan ristiriita.

Seuraava lause on yksi t¨arkeimmist¨a polynomeihin liittyvist¨a tuloksista. Sen avul- la saadaan todistettua monia muita tuloksia, kuten jo edell¨a todistettu polynomien juurien m¨a¨ar¨a.

Lause 1.1.6 (Polynomien jakoyht¨al¨o). Olkoot f ja g polynomeja yli kunnan F, toisin sanoen f, g ∈F[t] ja oletetaan, ett¨a degg ≥0. T¨all¨oin on olemassa polynomit q, r ∈F[t] siten, ett¨a

f(t) = q(t)g(t) +r(t), (1.3)

ja degr <degg. Polynomit q ja r ovat m¨a¨aritelty yksik¨asitteisesti.

Todistus. Olkoon m= degg ≥0. Merkit¨a¨an f(t) =a_ntⁿ+· · ·+a₀, g(t) = b_mt^m+· · ·+b₀, miss¨a b_m 6= 0.

Josn < m, niin valitaanq(t) = 0 ja r(t) =f(t).

Josn ≥m, niin

f₁(t) =f(t)−a_nb⁻¹_m t^n−mg(t).

T¨all¨oin degf₁ <degg ja kun jatketaan vastaavasti, niin l¨oydet¨a¨an polynomit q₁ ja r siten, ett¨a

f₁(t) =q₁(t)g(t) +r(t), miss¨a degr <degg.

Nyt

f(t) = a_nb⁻¹_m t^n−mg(t) +f₁(t)

=a_nb⁻¹_m t^n−mg(t) +q₁(t)g(t) +r(t)

= (anb⁻¹_m t^n−m+q1)g(t) +r(t),

joten jos merkit¨a¨an q(t) = a_nb⁻¹_m t^n−m+q₁, niin yht¨al¨o (1.3) toteutuu.

Seuraus 1.1.7. Olkoot F kunta,f ∈F[t] nollasta eroava polynomi ja α∈F sen juuri, eli f(α) = 0. T¨all¨oin on olemassa polynomi q(t)∈F[t] siten, ett¨a

f(t) = (t−α)q(t).

Todistus. Voidaan kirjoittaa

f(t) = q(t)(t−α) +r(t),

miss¨a degr <deg(t−α). Mutta deg(t−α) = 1, joten r on vakio. Nyt saadaan 0 =f(α) = q(α)(α−α) +r(α) = r(α).

1.2. JAOLLISUUS 7

Seuraus 1.1.8. Olkoon F sellainen kunta, jossa kaikilla polynomeilla f ∈ F[t], jotka eiv¨at ole vakioita, on juuri kunnassaF. T¨all¨oin on olemassa alkiot α₁, . . . , α_n∈ F ja c∈F siten, ett¨a

f(t) = c(t−α₁)· · ·(t−α_n).

Todistus. Seurauksesta 1.1.7 huomataan, ett¨a degq = degf −1. Jos α = α₁, niin saadaan seurauksen 1.1.7 mukaan yht¨al¨o

f(t) =q(t)(t−α₁).

Nyt jos polynomiq ei ole vakio, niin oletuksen nojalla sille l¨oytyy juuriα₂ ja saadaan f(t) =q₂(t)(t−α₁)(t−α₂).

T¨at¨a jatketaan kunnes q_n on vakio.

Seurauksesta 1.1.8 saadaan m¨a¨aritelm¨a:

M¨a¨aritelm¨a 1.1.9. Kunta F, jossa jokaisella polynomilla, jonka aste on ≥1, on juuri kunnassa F, on algebrallisesti suljettu.

Nyt lause 1.1.4 voidaan todistaa my¨os polynomien jakoyht¨al¨on avulla.

Seuraus 1.1.10. Olkoon F kunta ja f polynomi, jonka aste on n ≥ 1. T¨all¨oin polynomilla f on enint¨a¨an n juurta.

Todistus. Olkootα₁, . . . , α_rpolynominf eri juuret kunnassaF. Nyt polynomien jakoyht¨al¨on nojalla tiedet¨a¨an, ett¨a polynomi voidaan jakaa tekij¨oihin seuraavasti:

f(t) = c(t−α₁)· · ·(t−α_r)g(t),

miss¨a r≤n.

1.2. Jaollisuus

T¨ass¨a kappaleessa esitet¨a¨an, miten polynomien jakoyht¨al¨on avulla voidaan m¨a¨ari- tell¨a polynomien jaollisuutta. Lis¨aksi tarkastellaan polynomien jaollisuuteen liittyvi¨a ominaisuuksia. L¨ahteen¨a on k¨aytetty teosta [2].

Lause1.2.1. OlkoonI renkaanF[t]ideaali. T¨all¨oin on olemassa polynomig, joka viritt¨a¨a ideaalin I. Jos I ei ole nollaideaali, niin g ∈ I ei ole nollapolynomi ja on pienint¨a astetta. Sanotaan, ett¨a polynomi g on ideaalin I viritt¨aj¨a.

Todistus. Oletetaan, ett¨a I ei ole nollaideaali. Olkoon g ∈I pienint¨a astetta ja g 6= 0. V¨aitet¨a¨an, ett¨ag viritt¨a¨a ideaalin I. Olkoonf ideaalin I jokin polynomi. Nyt polynomin jakoyht¨al¨on avulla saadaan

f =qg+r,

miss¨a degr <degg. T¨all¨oinr=f−qg, ja ideaalin m¨a¨aritelm¨an mukaan t¨ast¨a seuraa, ett¨a r ∈ I. Nyt koska degr < degg, niin t¨aytyy olla r = 0 (koska g on pienint¨a astetta). N¨ain ollen f =qg, eli toisin sanoen g viritt¨a¨a ideaalin I.

8 1. POLYNOMIT

Huomautus 1.2.2. Olkoon g₁ ideaalin I nollasta eroava viritt¨aj¨a ja olkoon g₂ my¨os ideaalin I viritt¨aj¨a. T¨all¨oin on olemassa polynomi q siten, ett¨a g₁ = qg₂. Nyt yht¨al¨ost¨a

degg₁ = degq+ degg₂ seuraa, ett¨a degg₂ ≤degg₁. Symmetrian nojalla t¨aytyy olla

degg₂ = degg₁, joten polynomi q on vakio. Voidaan siis kirjoittaa

g₁ =cg₂, miss¨a con vakio. Olkoon

g2(t) = antⁿ+· · ·+a0,

miss¨a a_n 6= 0. Valitaan b = a⁻¹_n . T¨all¨oin bg₂ on my¨os ideaalin I viritt¨aj¨a ja sen p¨a¨akerroin on 1. Siisp¨a jokaiselle nollasta eroavalle ideaalille l¨oytyy viritt¨aj¨a, jonka p¨a¨akerroin on 1. Lis¨aksi on selv¨a¨a, ett¨a t¨am¨a viritt¨aj¨a on yksik¨asitteinen.

M¨a¨aritelm¨a 1.2.3. Olkoot f ja g nollasta eroavia polynomeja. Sanotaan, et- t¨a polynomi g jakaa polynomin f, jos on olemassa polynomi q siten, ett¨a f = qg.

Merkit¨a¨an g |f.

M¨a¨aritelm¨a 1.2.4. Olkoot f1 ja f2 nollasta eroavia polynomeja. Polynomi g on polynomien f₁ ja f₂ suurin yhteinen tekij¨a, jos se jakaa polynomit f₁ ja f₂ ja lis¨aksi jos polynomih jakaa polynomit f₁ ja f₂, niinh jakaa polynomin g. Merkit¨a¨an syt(f₁, f₂) = g.

Lause 1.2.5. Olkoot f₁, f₂ ∈ F[t] nollasta eroavia polynomeja ja I ideaali, joka sis¨alt¨a¨a n¨am¨a polynomit. Jos polynomi g on ideaalin viritt¨aj¨a, niin g on polynomien f₁ ja f₂ suurin yhteinen tekij¨a.

Todistus. Koska f1 ∈I, niin on olemassa polynomi q1 siten, ett¨a f₁ =q₁g,

joten g jakaa polynomin f1. Vastaavasti g jakaa polynominf2.

Olkoon nyt h polynomi, joka jakaa molemmat polynomit f₁ ja f₂. T¨all¨oin f₁ =h₁h ja f₂ =h₂h,

joillekin polynomeille h1 ja h2. Koska g on ideaalin I viritt¨aj¨a, niin on olemassa polynomit g₁ ja g₂ siten, ett¨ag =g₁f₁+g₂f₂. Siisp¨a

g =g₁f₁+g₂f₂

=g₁h₁h+g₂h₂h

= (g₁h₁+g₂h₂)h,

eli polynomi h jakaa polynomin g.

Polynomien jakoyht¨al¨on avulla voidaan my¨os ratkaista kahden polynomin suurin yhteinen tekij¨a laskemalla polynomien jakoyht¨al¨o, jonka j¨alkeen saatu jakoj¨a¨ann¨osr1

jaetaan laskun jakajallag. T¨at¨a jatketaan, kunnes saadaan jakoj¨a¨ann¨okseksirn(x) = 0, jolloin haluttu suurin yhteinen tekj¨a on r_n−1(x).

1.2. JAOLLISUUS 9

Esimerkki 1.2.6. Olkoot f, g∈Q[x] polynomeja ja f(x) = 2x⁴+x³+ 2x+ 1 ja g(x) = 2x³+x²−x. T¨all¨oin saadaan

2x⁴+x³+ 4x+ 3 =x·(2x³+x²−x) + (x²+ 2x+ 1) 2x³+x²−x= (2x−3)·(x²+ 2x+ 1) + (3x+ 3)

x²+ 2x+ 1 = (x 3 +1

3)·(3x+ 3).

Nyt siis saadaan jakoj¨a¨ann¨okseksi nolla, joten polynomien f ja g suurin yhteinen tekij¨a on nollaa edelt¨av¨a jakoj¨a¨ann¨os, eli t¨ass¨a tapauksessa 3x+ 3.

Lause 1.2.7. Olkoont alkio miss¨a tahansa joukossa, jossa on olemassa suurimpia yhteisi¨a tekij¨oit¨a. T¨all¨oin jos m ja n ovat positiivisia kokonaislukuja, niin

syt(tⁿ−1, t^m−1) = t^syt(n,m)−1.

Todistus. Tehd¨a¨an toditus induktiolla. Jos max(n, m) = 1 tai jos n = m, niin tulos on triviaali. Oletetaan siis, ett¨am < nja huomataan, ett¨a (tⁿ−1)−t^n−m(t^m−1).

Nyt

syt(tⁿ−1, t^m−1) = syt(t^m−1, t^n−m−1),

koska josd on polynomien (tⁿ−1) ja (t^m−1) suurin yhteinen tekij¨a, niin se on my¨os polynomien (t^m −1) ja (tⁿ−1)−s(t^m−1) suurin yhteinen tekij¨a jollekin s ∈ Z ja k¨a¨ant¨aen, jos d on polynomien (t^m−1) ja (tⁿ−1)−s(t^m−1) suurin yhteinen tekij¨a, niin se on my¨os polynomien (tⁿ−1) ja (t^m−1) suurin yhteinen tekij¨a. Nyt induktion nojalla saadaan

syt(t^m−1, t^n−m−1) =t^syt(m,n−m)−1 = t^syt(n,m)−1.

Seuraus 1.2.8. Samoilla oletuksilla kuin edellisess¨a lauseessa,

syt(x^qn−x, x^qd −x) = x^syt(qn,qd)−x.

Todistus. Sivuutetaan.

M¨a¨aritelm¨a 1.2.9. Polynomi p∈F[t] onjaoton(yli kunnan F), jos sen aste on

≥1 ja jos voidaan jakaa tekij¨oihin

p=f g,

miss¨a f, g∈F[t] ja joko degf = 0 tai degg = 0. Toisin sanoen jokof tai g on vakio, joten polynomin p ainoat jakajat ovatp itse ja luku 1.

Lause1.2.10. Jokainen kunnassaF[t]oleva polynomi, jonka aste on≥1, voidaan esitt¨a¨a yksik¨asitteisesti nollasta eroavien jaottomien polynomien p₁· · ·p_m tulona.

Todistus. Todistetaan ensin tulon olemassaolo.

Olkoon f ∈F[t] ja deg f ≥ 1. Jos polynomi f on jaoton, niin todistus on selv¨a.

Muulloin voidaan merkit¨a

f =gh,

miss¨a degg <degf ja degh <degf. Nyt polynomitg jah voidaan esitt¨a¨a joidenkin polynomien tulona ja t¨at¨a voidaan jatkaa niin kauan, kunnes polynomit ovat jaotto- mia. Siisp¨a my¨os polynomi f voidaan esitt¨a¨a jaottomien polynomien tulona.

10 1. POLYNOMIT

Lauseen 1.2.10 yksik¨asitteisyyden todistamiseen tarvitaan lemma:

Lemma 1.2.11. Olkoon p ∈ F[t] jaoton polynomi. Olkoot f, g ∈ F[t] nollasta eroavia polynomeja ja oletetaan, ett¨apjakaa tulonf g. T¨all¨oinpjakaa joko polynomin f tai polynomin g.

Todistus. Oletetaan, ett¨apei jaa polynomiaf. T¨all¨oin polynomienpjaf suurin yhteinen tekij¨a on 1 ja on olemassa polynomit h₁, h₂ ∈F[t] siten, ett¨a

1 = h₁p+h₂f.

Kerrotaan yht¨al¨o polynomilla g ja saadaan

g =gh₁p+h₂f g.

Nyt oletuksen nojalla f g=h₃p, joten

g = (gh₁+h₂h₃)p,

joten p jakaa polynoming.

Lauseen 1.2.10 yksik¨asitteisyys. Oletetaan nyt, ett¨a polynomif voidaan il- maista kahdella tavalla jaottomien polynomien avulla, eli f = p₁· · ·p_m = q₁· · ·q_r. T¨all¨oin p₁ | q₁· · ·q_r, joten lemman 1.2.11 mukaan p₁ jakaa jonkin polynomeista q_i. Oletetaan, ett¨a p1 jakaa polynominq1. Nyt koska q1 on jaoton ja p1 ei ole vakiopoly- nomi, niin on olemassa vakio c1, jolle q1 =c1p1. Siisp¨a

p₁p₂· · ·p_m =c₁p₁q₂· · ·q_r, jolloin

p₂p₃· · ·p_m =c₁q₂q₃· · ·q_r.

Jatkamalla induktiivisesti huomataan, ett¨a m = r ja l¨oydet¨a¨an vakiot ci siten, ett¨a

q_i =c_ip_i kaikillei= 1,2, . . . , m.

M¨a¨aritelm¨a 1.2.12. Olkoot p₁, . . . , p_r jaottomia polynomeja, joiden p¨a¨akertoi- met ovat 1. Polynomi f voidaan esitt¨a¨a polynomien tulona:

f =p^m₁¹· · ·p^m_r^r,

miss¨am1, . . . , mrovat yksik¨asitteisi¨a positiivisia kokonaislukuja polynomienp1, . . . , pr

mukaan. T¨allaista tekij¨oihin jakoa kutsutaan polynomin f normalisoivaksi tekij¨oihin jaoksi.

Lis¨aksi yli algebrallisen kunnan voidaan merkit¨a f(t) = (t−α₁)^m1· · ·(t−α_r)^mr.

M¨a¨aritelm¨a 1.2.13. Jos polynomi p on jaoton jaf =p^mg, miss¨a p ei jaa poly- nomia g ja m ≥ 0 on kokonaisluku, niin sanotaan, ett¨a polynomi p on m-kertainen polynomissa f. M¨a¨aritell¨a¨an t¨am¨a moninkerta polynomin f j¨arjestysluvuksi polyno- min p suhteen.

Vastaavasti polynomin juurille:

M¨a¨aritelm¨a 1.2.14. Josα on polynomin f juuri ja f(t) = (t−α)^mg(t),

miss¨a g(t) 6= 0, niin (t−α) ei jaa polynomia g(t). T¨all¨oin polynomi (t−α) on m- kertainenpolynomissaf eli voidaan sanoa, ett¨aαon polynominf m-kertainen juuri.

1.2. JAOLLISUUS 11

Nyt siis jos m >1, niin sanotaan, ett¨a juuri on moninmertainen. Juuren monin- kertaisuus voidaan testata helposti derivaatan avulla, joten t¨aytyy ensin m¨a¨aritell¨a polynomeille derivaatta.

M¨a¨aritelm¨a 1.2.15. Olkoon f(t) = antⁿ+· · ·+a0 polynomi. M¨a¨aritell¨a¨an sen derivaatta

Df(t) = f⁰(t) =na_ntⁿ⁻¹+ (n−1)an−1tⁿ⁻²+· · ·+a₁ =

n

X

k=1

ka_kt^k−1.

T¨all¨oin seuraavan lauseen avulla voidaan saada selville, onko polynomin juuri moninkertainen.

Lause 1.2.16. OlkootF kunta ja f polynomi yli kunnan F siten, ett¨a sen aste on

≥ 1 ja α on polynomin juuri kunnassa F. T¨all¨oin juuri α on moninkertainen jos ja vain jos f⁰(α) = 0.

Todistus. Oletetaan, ett¨a

f(t) = (t−α)^mg(t), miss¨a m >1. Derivoimalla polynomif saadaan

f⁰(t) = m(t−α)^m−1g(t) + (t−α)^mg⁰(t).

Kun sijoitetaan α, niin huomataan, ett¨af⁰(α) = 0, kun m−1≥1.

Toisaalta oletetaan, ett¨a

f(t) = (t−α)^mg(t),

miss¨a g(t)6= 0, jotenα on polynomin f m-kertainen juuri. Jos m= 1, niin f⁰(t) =g(t) + (t−α)g⁰(t),

jolloin f⁰(α) =g(α)6= 0.

LUKU 2

A¨ ¨ arelliset kunnat

2.1. M¨a¨aritelmi¨a

T¨ass¨a kappaleessa tarkastellaan, mit¨a ovat ¨a¨arelliset kunnat ja m¨a¨aritellaan kun- tateorian t¨arkeimpi¨a k¨asitteit¨a. L¨ahteen¨a on k¨aytetty teosta [2] jos ei toisin mainita.

Tarkastellaan j¨a¨ann¨osluokkarenkaita Zn ja erityisesti sit¨a, ovatko ne kuntia. Mer- kit¨a¨an kokonaisluvun a ∈Zn viritt¨am¨a¨a ekvivalenssiluokkaa a. Joukko Zn on kunta, jos jokaiselle alkiolle l¨oytyy kertolaskussa k¨a¨anteisalkio, toisin sanoen jos kaikillea 6= 0 on olemassa alkio b siten, ett¨a

a·b= 1.

(2.1)

T¨am¨a ei kuitenkaan aina pid¨a paikkansa, sill¨a esimerkiksi j¨a¨ann¨osluokkarenkaassa Z⁴ ekvivalenssiluokalle 2 ei l¨oydy k¨a¨anteisalkiota ja lis¨aksi 2·2 = 0 eli joukossa on nollanjakajia, jolloin se ei voi olla kunta. [4]

Lause 2.1.1. J¨a¨ann¨osluokkarengas Z^p on kunta, jos luku p on alkuluku. [4]

Todistus. Olkoon a joukon Z^p alkio ja a 6= 0. Nyt t¨aytyy siis osoittaa, ett¨a on olemassa alkio b siten, ett¨a yht¨al¨o (2.1) p¨atee. Nyt koska a 6= 0, niin p - a. T¨all¨oin siis on olemassa alkiot b, t ∈ Zp siten, ett¨a ab+tp = 1. T¨all¨oin ab ≡ 1 (mod p), eli

yht¨al¨o (2.1) p¨atee.

My¨os polynomeista voidaan muodostaa j¨a¨ann¨osluokkarenkaita yli kunnanZp. Mer- kit¨a¨anZp[x]; se siis sis¨alt¨a¨a kaikki muuttujanxpotenssien summat ja polynomin ker- toimet kuuluvat kuntaan Zp, toisin sanoen kertoimet ovat j¨a¨ann¨osluokkia modulo p.

Lis¨aksi j¨a¨ann¨osluokkarenkaita muodostavien polynomien tulee olla jaottomia kunnas- sa Zp. Polynomeilla yli kunnan Zp voidaan laskea samalla tavalla kuin ”tavallisilla”

polynomeilla, mutta t¨aytyy muistaa, ett¨a aritmetiikka tapahtuu kunnassan Zp. [1]

Esimerkki2.1.2. OlkootF13[x] kunta jaa(x) = x⁸+x⁶+10x⁴+10x³+8x²+2x+8 sek¨a b(x) = 3x⁶+ 5x⁴ + 9x²+ 4x+ 8 polynomeja kunnassa F13[x]. Katsotaan onko olemassa polynomien jakoyht¨al¨on mukaiset polynomit q(x) ja r(x) siten, ett¨a

a(x) = q(x)b(x) +r(x), deg(r)<deg(b).

Nyt meid¨an t¨aytyy siis jakaa polynomia(x) polynomilla b(x). J¨atet¨a¨an jakolaskusta muuttujat x kokonaan pois ja lasketaan pelk¨ast¨a¨an kertoimilla.

13

14 2. ¨A ¨ARELLISET KUNNAT

N¨ain ollen saadaanq(x) = 9x²+ 7 ja r(x) = 11x⁴ + 3x²+ 4. [4]

M¨a¨aritelm¨a 2.1.3. Olkoon F kunnan E alikunta. T¨all¨oin kuntaa E kutsutaan kunnan F kuntalaajennukseksi.

M¨a¨aritelm¨a2.1.4. OlkoonEkunnanF kuntalaajennus. T¨all¨oin kunnanEalkio α on algebrallinen yli kunnan F, jos on olemassa nollasta eroava polynomi f ∈ F[t]

siten, ett¨a f(α) = 0. Toisin sanoen α toteuttaa yht¨al¨on anαⁿ+· · ·+a0 = 0, miss¨a a_j ∈F kaikilla j = 1,2, . . . n.

Jos jokainen alkioα∈E on algebrallinen yli kunnanF, niin sanotaan, ett¨a kunta E algebrallinen yli kunnan F.

Kuntalaajennus voidaan n¨ahd¨a my¨os vektoriavaruutena, jolloin kuntalaajennusE on vektoriavaruus yli kunnan F. KuntalaajennusE on¨a¨arellinen kuntalaajennus, jos E on vektoriavaruus, jolla on ¨a¨arellinen dimensio, yli kunnan F.

JosE on kunnan F kuntalaajennus, niin sen aste on [E :F] := dim_FE.

Lause2.1.5. JosEon kunnanF ¨a¨arellinen kuntalaajennus, niin jokainen kunnan E alkio on algebrallinen yli kunnan F ts. E on algebrallinen yli kunnan F.

Todistus. Alkionα ∈E potenssit, eli 1, α, α², . . . , αⁿ, eiv¨at voi olla lineaarisesti riippuvaisia yli kunnanF, josn > dimE. N¨ain ollen on olemassa alkiota₀, . . . , a_n∈F, joista kaikki eiv¨at ole nollia, siten, ett¨aa_nαⁿ+· · ·+a₀ = 0. T¨all¨oinαon algebrallinen

yli kunnan F.

M¨a¨aritelm¨a 2.1.6. Olkoot F kunta ja f ∈ F polynomi, jonka aste on n ≥ 1.

Kunnan F ¨a¨arellinen kuntalaajennus E on polynomin f juurikunta, jos f voidaan jakaa 1. asteen polynomeiksi kunnassaE siten, ett¨a

f(t) = c(t−α₁)· · ·(t−α_n),

miss¨a c ∈ F on p¨a¨akerroin ja E = F(α₁, . . . , α_n). Toisin sanoen juurikunta muo- dostuu kaikista polynomin f juurista siten, ett¨a polynomif on jakautunut 1. asteen polynomeihin.

Kuten edellisess¨a m¨a¨aritelm¨ast¨a huomataan, niin kuntalaajennuksista k¨aytet¨a¨an usein merkint¨a¨a F(α₁, . . . , α_n), jolla tarkoitetaan pienint¨a mahdollista kuntaa, joka

2.1. M ¨A ¨ARITELMI ¨A 15

sis¨alt¨a¨a kunnan F sek¨a alkiotα₁, . . . , α_n. Lis¨aksi seuraavissa lauseissa k¨aytet¨a¨an iso- morfismille merkint¨a¨a σ. Jos f(t) = a_ntⁿ+· · ·+a₀ on polynomi, niin m¨a¨aritell¨a¨an σf polynomeille

σf(t) =σ(a_n)tⁿ+· · ·+σ(a₀).

Lause 2.1.7. Olkoon F kunta ja p ∈ F[x] jaoton polynomi, jonka aste on ≥ 1.

T¨all¨oin on olemassa kunnan F kuntalaajennus E ja polynomilla p on juuri kunnassa E.

Todistus. Josf(t)∈F[t] jap-f, niin syt(f, p) = 1, joten on olemassa polynomit g(t), h(t)∈F[t] siten, ett¨a

gf +hp= 1.

T¨am¨a tarkoittaa sit¨a, ett¨a gf ≡ 1 mod p, josta seuraa, ett¨a f mod p on k¨a¨antyv¨a kunnassa F[t]/p. N¨ain ollen kaikki nollastaeroavat joukon F[t]/p alkiot ovat k¨a¨an- tyvi¨a, eli F[t]/p on kunta. Homomorfismi kuvaa kunnasta F jokaiselle polynomille j¨a¨ann¨osluokan modulo p(t) kuntaan F[t]/p. Koska kunnalla F[t]/p ei ole muita ide- aaleja kuin nollaideaali ja kunta itse, ja koska 16≡0 mod p(t), niin voidaan p¨a¨atell¨a, ett¨a homomorfismi

σ:F →F[t]/(p(t))

on injektio. N¨ain ollen F[t]/(p(t)) on ¨a¨arellinen kuntalaajennus kunnasta σ(F). Nyt jos tarkastellaan kuntaaF kuvajoukon σ(F) avulla, niin huomataan, ett¨aF[t]/(p(t)) on kunnan F kuntalaajennus, ja ett¨a polynomillap on juuri α t¨ass¨a laajennuksessa,

joka on sama kuin j¨a¨ann¨osluokka t modp(t).

Lause 2.1.8. Olkoot F kunta ja f ∈F polynomi, jonka aste on ≥ 1. T¨all¨oin on olemassa juurikunta polynomille f.

Todistus. Olkoonp polynominf jaoton tekij¨a. T¨all¨oin lauseen 2.1.7 mukaan on olemassa kuntalaajennus E₁ = F(α₁), jossa on polynomin p juuriα₁ ja t¨all¨oin my¨os polynomin f juuri. Jos polynomi f voidaan jakaa tekij¨oihin seuraavasti:

f(t) = (t−α₁)g(t)

kunnassaE₁[t], niin degg = degf−1. N¨ain ollen induktiolla saadaan, et¨a on olemassa kunta E =E₁(α₂, . . . , α_n) siten, ett¨a

g(t) = c(t−α₂)· · ·(t−α_n),

miss¨a c∈F.

Lause 2.1.9. Olkoot F kunta ja f ∈ F polynomi, jonka aste on ≥ 1. Olkoot E ja J kunnan F kuntalaajennuksia, jotka ovat polynomin f juurikuntia. T¨all¨oin on olemassa isomorfismi

σ:E →J yli kunnan F.

Todistus. Voidaan olettaa, ett¨a polynominf p¨a¨akerroin on 1 ilman, ett¨a lauseen yleistett¨avyys katoaa. Todistetaan seuraava tarkempi v¨aite induktiolla.

16 2. ¨A ¨ARELLISET KUNNAT

Olkoonσ :F →σF isomorfismi. Olkootf(t)∈F[t]polynomi, jonka p¨a¨akerroin on 1 jaK =F(α₁, . . . , α_n)polynominf juurikunta. Polynomif voidaan jakaa tekij¨oihin seuraavasti:

f(t) =

n

Y

i=1

(t−α_i).

Olkoon L polynominσf juurikunta, miss¨aL= (σF)(β₁, . . . , β_n)ja σf(t) =

n

Y

i=1

(t−βi).

T¨all¨oin on olemassa isomorfismi τ : K → L, joka laajentaa kuvauksen σ siten, ett¨a juuriaβ₁, . . . , β_nmuuttamalla, jos tarpeellista, saadaan τ α_i =β_i kaikillei= 1, . . . , n.

Olkoonp(t) polynomin f jaoton tekij¨a. T¨all¨oin, josα₁ on polynominp juuri jaβ₁ on polynomin σp juuri, niin on olemassa isomorfismi

τ₁ :F(α₁)→(σF)(β₁),

joka laajentaa kuvauksenσja kuvaa alkionα₁ alkioksiβ₁. Nyt tekij¨oihin jako voidaan tehd¨a

f(t) = (t−α1)g(t) yli kunnan F(α1) σf(t) = (t−β₁)τ₁g(t) yli kunnanσF(β₁),

koska τ₁α₁ =β₁. K¨aytt¨am¨all¨a induktiota polynomeihin g ja τ g saadaan isomorfismi

τ.

T¨am¨a lause todistaa periaatteessa sen, ett¨a kaksi ¨a¨arellist¨a kuntaa, joilla on sama m¨a¨ar¨a alkioita ovat isomorfiset, mutta palataan t¨ah¨an v¨aitteeseen viel¨a my¨ohemmin.

M¨a¨aritelm¨a 2.1.10. Olkoon G joukko kunnan K automorfismeja. Olkoon K^G joukko alkioita x ∈ K siten, ett¨a σx = x kaikille σ ∈ G. T¨all¨oin joukossa K^G on nolla-alkio ja ykk¨osalkio, sek¨a kaikille x, y ∈K^G p¨atee

σ(x+y) =σx+σy =x+y σ(xy) =σ(x)σ(y) =xy,

jolloin x +y ja xy ovat joukossa K^G. Lis¨aksi σ(x⁻¹) = σ(x)⁻¹ = x⁻¹, eli my¨os x⁻¹ ∈K^G. Siisp¨a joukko K^G on kunta ja sit¨a kutsutaan kiinnitetyksi kunnaksi.

M¨a¨aritelm¨a 2.1.11. Alkukuntaon kunnan pienin mahdollinen alikunta.

Jos F on ¨a¨arellinen kunta, jossa on q alkiota ja e on kunnan F ykk¨osalkio, niin on olemassa yksik¨asitteinen rengashomomorfismi

Z→F siten, ett¨a

n 7→ne=e+e+· · ·+e.

T¨am¨an homomorfismin ydin, eli alkiotn ∈Z, joillene= 0, on kokonaislukujen joukon Z ideaali. Ydin ei ole 0, sill¨a kuvajoukko on ¨a¨arellinen. Olkoon p pienin positiivinen kokonaisluku ideaalissa, jolloin p viritt¨a¨a ideaalin. T¨all¨oin on olemassa isomorfismi

Z^p →F^p

2.2. ¨A ¨ARELLISEN KUNNAN ALKIOT 17

j¨a¨ann¨osluokaltaZ^p sen kuvajoukkoon kunnassaF. Merkit¨a¨an kuvajoukkoa F^p. Koska Fp on kunnan F alikunta, jolloin se ei sis¨all¨a nollanjakajia, niin luvun p on oltava alkuluku. T¨at¨a lukua p kutsutaan kunnan F karakteristikaksi.

2.2. ¨A¨arellisen kunnan alkiot

T¨ass¨a kappaleessa k¨ay ilmi, mit¨a ominaisuuksia on ¨a¨arellisell¨a kunnalla, jossa on q alkiota ja millainen t¨am¨a luku q on. Jatkossa ¨a¨arellist¨a kuntaa, jonka kertaluku on q voidaan my¨os merkit¨a GF(q). L¨ahteen¨a t¨ass¨a luvussa on k¨aytetty teosta [2] jos ei toisin mainita.

Lause 2.2.1. A¨¨arellisen kunnan F alkioiden m¨a¨ar¨a q on jokin alkuluvun p po- tenssi.

Todistuksessa [2] ja [4]:

Todistus. Tarkastellaan kuntaa F vektoriavaruutena yli alkukunnan Fp. Nyt koska vektoriavaruudessa F on ¨a¨arellinen m¨a¨ar¨a alkioita, niin sen dimensio yli alku- kunnan Fp on ¨a¨arellinen. Olkoon t¨am¨a dimensio n. Jos {w₁, w₂, . . . , w_n} on kanta, niin jokainen vektoriavaruuden F alkio voidaan esitt¨a¨a muodossa

x=a₁w₁+· · ·+a_nw_n,

miss¨a aj ∈ F^p kaikilla j = 1, . . . , n. Koska jokainen kerrroin aj voidaan valita mieli- valtaisestip:ll¨a eri tavalla, niin t¨ast¨a seuraa, ett¨a vektoriavaruudessa, eli kunnassa F

onpⁿ alkiota. Siisp¨a q=pⁿ.

Jatkossa oletetaan, ett¨a luku q on lauseen 2.2.1 mukaisesti q=pⁿ jollekin alkulu- vullep ja positiiviselle kokonaisluvulle n.

Lause 2.2.2. A¨¨arellinen kunta F, jossa on q = pⁿ alkiota, on polynomin t^q −t juurikunta yli kunnan Zp.

Todistus. Nollasta eroavien alkioiden multiplikatiivisessa ryhm¨ass¨a F^∗ onq−1 alkiota, joille kaikille p¨atee

x^q−1−1 = 0 josx∈F^∗. N¨ain ollen kaikille kunnan F alkioille p¨atee

x^q−x= 0.

Tarkastellaan polynomia

f(t) =t^q−t

yli ¨a¨arellisen kunnanF^p. Polynomilla onqkappaletta eri juuria kunnassaF, nimitt¨ain kaikki kunnanF alkiot. N¨ain ollen jos K on jokin toinen kunta, joka sis¨alt¨a¨a kunnan F, niin polynomillat^q−tei voi olla muita juuria kunnassaKkuin kunnanF alkiot.

M¨a¨aritelm¨a2.2.3. KunnanF algebrallinen sulkeumaon kuntaA, joka on pienin algebrallisesti suljettu kunnan F kuntalaajennus.

Lause 2.2.4. Olkoon q = pⁿ ja A algebrallisesti suljettu kunta. T¨all¨oin joukko alkioita x∈A, joille x^q =x, on ¨a¨arellinen kunta, jossa on q alkiota.

18 2. ¨A ¨ARELLISET KUNNAT

Todistus. Binomikertoimien avulla saadaan (x+y)^p =

p

X

i=0

p i

xⁱy^p−i, miss¨a lausekkeesta

p i

= p!

i!(p−i)!

n¨ahd¨a¨an, ett¨a kaikki muut kertoimet, paitsi ensimm¨ainen ja viimeinen, ovat jaollisia luvulla p, toisin sanoen ne ovat nollia. T¨all¨oin saadaan yht¨al¨o

(x+y)^p =x^p+y^p kaikillex, y ∈A.

Induktiolla voidaan todistaa, ett¨a

(x+y)^pm =x^pm+y^pm kaikille positiivisille kokonaisluvuille m.

Olkoon nyt J joukko alkioita x ∈ A, joille x^pn =x. T¨all¨oin on helppo huomata, ett¨a J on kunta. Lis¨aksi n¨ahd¨a¨an, ett¨a joukko on yhteenlaskun suhteen suljettu ja koska yht¨al¨o

(xy)^pn =x^pny^pn

p¨atee kaikille kommutatiivisille renkaille, niin joukko on my¨os kertolaskun suhteen suljettu.

Olkoon nyt f(t) = t^q −t. T¨all¨oin polynomin f kaikki juuret ovat kunnassa J ja kunta J on pienin mahdollinen kunta, joka on jaollinen kunnalla Z^p ja kaikilla polynomin f juurilla. Siisp¨a J on polynomin f juurikunta.

Nyt lauseen 1.2.16 nojalla tarkastellaan polynomin derivaattaa. Saadaan f⁰(t) =qt^q−1−1 =−1,

koskaq = 0 kunnassaZp. Siisp¨a polynomilla ei ole moninkertaisia juuria, joten voidaan p¨a¨atell¨a, ett¨a sill¨a on tasanq juurta. T¨all¨oin kunnassaJ on t¨asmalleen q alkiota.

2.3. Frobeniuksen automorfismi

T¨ass¨a kappaleessa tarkastellaan automorfismeja, ja tarkemmin Frobeniuksen au- tomorfismia, ¨a¨arellisiss¨a kunnissa. L¨ahteen¨a on k¨aytetty teosta [2].

Lause 2.3.1. Olkoon F ¨a¨arellinen kunta, jossa on q alkiota. T¨all¨oin kuvaus ϕ:x7→x^p

on automorfismi kunnasta F.

Todistus. Tiedet¨a¨an, ett¨a kuvaus

x7→x^p

on rengashomomorfismi kunnastaF itselleen. Sen ydin on 0, ja koskaF on ¨a¨arellinen, niin kuvauksen on oltava bijektio. Toisin sanoen se on automorfismi.

2.3. FROBENIUKSEN AUTOMORFISMI 19

Automorfismia ϕ kutsutaan kunnan F Frobeniuksen automorfismiksi. Se luo ¨a¨a- rellisen, syklisen ryhm¨an, koska kunnassa F on ¨a¨arellinen m¨a¨ar¨a (q = pⁿ) alkioita.

Siisp¨a jokaiselle m∈Z

ϕ^mx=x^pm

kaikillex∈F. Eli kuvauksen ϕjakso jakaa luvun n, koska ϕⁿx=x^pn =x^q =x.

Nyt siis voidaan huomata, ett¨a

ϕⁿ=id.

Lause 2.3.2. Olkoon F ¨a¨arellinen kunta, jossa onq =pⁿ alkiota. T¨all¨oin kuvauk- sen ϕ jakso on t¨asm¨alleen luvun n mittainen.

Todistus. Oletetaan, ett¨a jakso on luvun m < n mittainen. T¨all¨oin jokaiselle alkiolle x∈F p¨atee

x^pm−x= 0.

Mutta edell¨a on todistettu, ett¨a polynomilla t^pm−t

on enint¨a¨anp^m juurta. Siisp¨a ei voi ollam < n.

Lause 2.3.3. Kunta Fp^m on kunnan Fpⁿ alikunta jos ja vain jos luku m jakaa luvun n.

Todistus. ”⇒” Olkoon kuntaF kunnanFq alikunta, miss¨aq =pⁿ. T¨all¨oin kun- ta F sis¨alt¨a¨a alkukunnan Fp, joten siin¨a on p^m alkiota jollekin m ∈Z. Tarkastellaan kuntaa Fq vektoriavaruutena, jonka dimensio on d, yli kunnan F. Nyt kunnan Fq

alkiot voidaan esitt¨a¨a kanta-alkioiden lineaarikombinaatioina, miss¨a kertoimet kuu- luvat kuntaan F ja huomataan, ett¨a alkukunnassa F^p on (p^m)^d = p^md alkiota. N¨ain ollen n=md eli luku m jakaa luvun n.

”⇐” Oletetaan, ett¨a luku m jakaa luvun n, eli n =md. Olkoon F kuvauksen ϕ^m kiinnitetty kunta. T¨all¨oin F on joukko alkioitax∈Fq siten, ett¨a

x^pm =x.

Lauseen 2.2.2 nojalla t¨am¨a on tarkalleen kunta Fp^m. Mutta ϕ^md =ϕⁿ,

joten Fp^m on kuvauksen ϕⁿ kiinnitetty kunta. Koska my¨os Fpⁿ on kuvauksen ϕⁿ kiinnitetty kunta, niin

F^pm ⊂F^pn.

Jos n =md, niin kuvauksen ϕ^m kertaluku on d. N¨ain ollen ϕ^m muodostaa sykli- sen ryhm¨an kunnan Fq automorfismeista., joiden kiinnitetty kunta on Fp^m. T¨am¨an syklisen ryhm¨an kertaluku on aste [F^pn :F^pm]

Lause 2.3.4. Kunnan F^q ainoat automorfismit ovat Frobeniuksen automorfismin potensseja 1, ϕ, ϕ², . . . , ϕⁿ⁻¹.

20 2. ¨A ¨ARELLISET KUNNAT

Todistus. Olkoon F^q = F^p(α) jollekin alkiolle α. Nyt, koska q = pⁿ, niin α on n-asteisen polynomin juuri. T¨all¨oin on enint¨a¨an n kunnan Fq automorfismia yli alkukunnanFp. N¨ain ollen, koska automorfismeja 1, ϕ, ϕ², . . . , ϕⁿ⁻¹ on jonkappaletta,

niin niit¨a ei voi olla muita.

2.4. Eulerin φ-funktio

T¨ass¨a kappaleessa esitet¨a¨an eritt¨ain t¨arke¨a ¨a¨arellisiin kuntiin liittyv¨a k¨asite, ni- mitt¨ain Eulerin φ-funktio ja tarkastellaan sen ominaisuuksia. Kappaleessa l¨ahteen¨a on k¨aytetty teosta [4].

Lause 2.4.1. Olkoon F ¨a¨arellinen kunta, jossa on q alkiota ja α∈F alkio, jonka kertaluku on t. T¨all¨oin luku t jakaa luvun q−1.

Todistus. Olkoon F^∗ joukko nollasta eroavia kunnan F alkioita. T¨all¨oin F^∗ on multiplikatiivinen ryhm¨a, jossa on q−1 alkiota ja {1, α, α², . . . , α^t−1} on aliryhm¨a, jossa on t alkiota. Lagrangen lauseen mukaan aliryhm¨an alkioiden m¨a¨ar¨a jakaa aina ryhm¨an alkioiden m¨a¨ar¨an, siisp¨at jakaa luvun q−1.

Merkit¨a¨an alkion α kertalukua merkinn¨all¨a ord(α).

Lemma 2.4.2. Jos ord(α) =t, niin ord(αⁱ) = _syt(i,t)^t . Todistus. Tiedet¨a¨an, ett¨a kaikille β 6= 0 p¨atee

β^s = 1 jos ja vain jos ord(β)|s.

(2.2)

Olkoon d = syt(i, t). T¨all¨oin α^i(dt) = α^t(id) = (α^t)^di = 1. Nyt yht¨al¨on (2.2) nojalla ord(αⁱ)| _d^t. Merkit¨a¨ans= ord(αⁱ). T¨all¨oin α^is= 1, joten yht¨al¨on (2.2) nojalla t|is.

Nyt koska d = syt(i, t), niin on olemassa kokonaisluvut a ja b, joille ai+bt= d.

Kun t¨am¨a yht¨al¨o kerrotaan luvullas, niin saadaan ais+bts=ds.

Mutta koska t | is, niin siit¨a seuraa, ett¨a t | ds, toisin sanoen _d^t | s, toisin sanoen

t

d |ord(αⁱ). Nyt siis on osoitettu, ett¨a ord(αⁱ)| _d^t ja _d^t |ord(αⁱ), joten ord(αⁱ) = _d^t. Kuvataan symbolillaφ(t) kokonaislukuja joukossa{0,1, . . . , t−1}, jotka ovat kes- ken¨a¨an jaottomia luvun t kanssa. T¨at¨a kutsutaan Eulerin φ-funktioksi. Huomataan, ett¨a φ(t) on aina v¨ahint¨a¨an 1, koska syt(1, t) = 1 kaikille t ≥ 1. Funktion φ(t) tark- kaa arvoa on vaikea sanoa, mutta jost on alkuluku, niin φ(t) =t−1, koska joukossa {0,1, . . . , t−1} kaikki paitsi 0 ovat kesken¨a¨an jaottomia luvun t kanssa.

Lause 2.4.3. Olkoot t kokonaisluku ja F kunta. Kunnassa F on alkioita, joiden kertaluku on t joko ei yht¨a¨an tai φ(t) kappaletta.

Todistus. Jos kunnassa ei ole kertalukua t olevia alkioita, ei ole mit¨a¨an, mit¨a todistaa. Jos ord(α) = t, niin kaikki alkiot, joiden kertaluku on t, ovat joukossa {1, α, . . . , α^t−1}. Nyt lemman 2.4.2 nojalla alkio αⁱ on kertalukua t jos ja vain jos syt(i, t) = 1. N¨aiden lukujen i m¨a¨ar¨a on t¨asm¨alleen φ(t).

Yhdist¨am¨all¨a lauseet 2.4.1 ja 2.4.3, huomataan, ett¨a jos F on ¨a¨arellinen kunta, jossa on q alkiota ja t on positiivinen kokonaisluku, niin jos t ei jaa lukuaq−1, niin kunnassa ei ole yht¨a¨an alkiota, jonka kertaluku on t. Lis¨aksi jos t jakaa luvun q−1,

2.4. EULERIN φ-FUNKTIO 21

niin alkioita, joiden kertaluku on t on joko nolla tai φ(t) m¨a¨ar¨a. Itseasiassa voidaan todistaa, ett¨a jos luku t jakaa luvun q−1, niin kunnassa on t¨asm¨alleen φ(t) alkiota, joiden kertaluku on t. Sit¨a ennen tarkastellaan tilannetta kuitenkin esimerkin avulla ja todistetaan yksi lause.

Esimerkki 2.4.4. Olkoon q = 16. T¨all¨oin q −1 = 15 ja lauseen 2.4.1 nojalla kokonaisluku t voi ollat = 1,3,5,15. Nyt jokaiselle luvulle t alkioiden m¨a¨ar¨a, joiden kertaluku on t, on lauseen 2.4.3 mukaan joko nolla tai φ(t). Nyt funktion φ(t) arvot on helppo laskea, joten saadaan

t φ(t) 1 1 3 2 5 4 15 8

Huomataan, ett¨a sarakkeen φ(t) lukujen summa on 15, mik¨a on nollasta eroavien alkioiden m¨a¨ar¨a kunnassa F.

Lause 2.4.5. Jos n on positiivinen kokonaisluku, niin X

d|n

φ(d) =n, (2.3)

miss¨a merkint¨a d|n tarkoittaa kaikkia luvun n positiivisia jakajia.

Todistus. Olkoot S_n = {_n¹,_n², . . . ,ⁿ_n} ja T_n joukon S_n osajoukko, jossa on ”sie- vennetyt” murtoluvut, eli ne murtoluvut, joiden osoittaja ja luku n ovat kesken¨a¨an jaottomia. T¨all¨oin selv¨asti|Sn|=n ja|Tn|=φ(n) kaikillen = 1,2,3, . . .. Esimerkiksi

S6 ={1 6,2

6,3 6,4

6,5 6,6

6}, T₆ ={1

6,5 6}.

Nyt sievennet¨a¨an jokainen joukon S_n murtoluku mahdollisimman siev¨a¨an muotoon.

T¨all¨oin jokaisella murtoluvulla on yksik¨asitteiset osoittaja ja nimitt¨aj¨a. Murtoluvun nimitt¨aj¨adon luvunnjakaja ja osoittajaeon kokonaisluku 1≤e≤d, joka on jaoton nimitt¨aj¨an d kanssa. K¨a¨ant¨aen, jos d on jokin luvun n positiivinen jakaja ja jos 1≤ e≤d, jolle syt(e, d) = 1, niin murtoluku ^e_d on jonkin joukossa Sn olevan murtoluvun sievenn¨os. T¨all¨oin joukko S_n hajoaa pistevieraiden joukkojen T_d yhdisteeksi kaikilla d, jotka jakavat luvun n. Siisp¨a

S_n=[

d|n

T_d, jolloin

|S_n|=X

d|n

|T_d|.

Nyt siis|S_n|=n ja |T_d|=φ(d), joten v¨aite on todistettu.

Lause 2.4.6. Olkoot F ¨a¨arellinen kunta, jossa on q alkiota ja t positiivinen koko- naisluku. Jost- (q−1), niin kunnassaF ei ole olemassa alkiota, jonka aste on t. Jos t | (q−1), niin kunnassa F on t¨asm¨alleen φ(t) kappaletta alkioita, joiden kertaluku on t.

22 2. ¨A ¨ARELLISET KUNNAT

Todistus. Ensimm¨ainen v¨aite seuraa suoraan lauseesta 2.4.1. Nyt merkit¨a¨an, ett¨a ψ(t) kertoo kertalukua t olevien alkioiden m¨a¨ar¨an kaikille positiivisille luvun q−1 jakajille t. T¨all¨oin, koska kaikkien alkioiden kertaluku jakaa luvun q−1, niin

X

t|q−1

ψ(t) = q−1.

(2.4)

Nyt yhdist¨am¨all¨a yht¨al¨ot (2.3) ja (2.4) huomataan, ett¨a X

t|q−1

(φ(t)−ψ(t)) = 0.

Siisp¨a φ(t) = ψ(t) kaikille t|q−1.

M¨a¨aritelm¨a 2.4.7. Multiplikatiivisen ryhm¨an F^∗ alkiota, jonka kertaluku on q−1 (toisin sanoen alkiota, joka viritt¨a¨a syklisen ryhm¨an F^∗ = F −0), kutsutaan kunnan F primitiiviseksi alkioksi.

Esimerkki 2.4.8. Olkoonp(x) = x³+x+ 1 Z2-kertoiminen polynomi, ts. p(x)∈ F2[x]. Huomataan ensin, ett¨a polynomi p on jaoton, koska p(0) = p(1) = 1, joten polymomilla p ei ole nollakohtia kunnassaF2; ja kolmannen asteen polynomi, jolla ei ole nollakohtia kunnassa, on jaoton yli t¨am¨an kunnan.

Koska polynomip(x) on kolmannen asteen polynomi, niin sen ekvivalenssiluokkien (mod p) edustajiksi voidaan ottaa kahdeksan polynomia, jotka ovat muotoa a₂x²+ a₁x+a₀, miss¨aa_i ∈F2. N¨am¨a polynomit voidaan my¨os ajatella vektoreiden [a₂, a₁, a₀]

”viritt¨aj¨afunktioiksi”.

Nyt kun kerrotaan n¨aist¨a kahdeksasta alkiosta kaksi kesken¨a¨an, saadaan (a₂x²+a₁x+a₀)(b₂x²+b₁x+b₀)

=a₂b₂x⁴+ (a₂b₁+a₁b₂)x³ + (a₂b₀+a₁b₁ +a₀b₂)x² + (a₁b₀+a₀b₁)x+a₀b₀.

Mutta t¨am¨a polynomi on nelj¨annen asteen polynomi, joten se ei ole kunnan F2[x]

alkio. Siisp¨a nelj¨annen ja kolmannen asteen termit t¨aytyy supistaa pois. Huomataan, ett¨a

x³ ≡x+ 1 mod (x³+x+ 1), x⁴ ≡x²+x mod (x³+x+ 1) ja n¨ain ollen

a₂b₂x⁴ ≡a₂b₂x²+a₂b₂x mod (p(x)) ja

(a2b1 +a1b2)x³ ≡(a2b1+a1b2)x+ (a2b1+a1b2) mod (p(x)).

Nyt tarkastellaan tilannetta vektoreina, jolloin kertomalla vektorit [a₂, a₁.a₀] ja [b₂, b₁, b₀] saadaan vektori [c₂, c₁, c₀], miss¨a

c₂ =a₂b₂ +a₂b₀+a₀b₂

c₁ =a₂b₂ +a₂b₁+a₁b₂ +a₁b₀+a₀b₁ c₀ =a₂b₁ +a₁b₂+a₀b₀.

2.4. EULERIN φ-FUNKTIO 23

T¨am¨a ei ole kovin yksinkertainen s¨a¨ant¨o, mutta se muodostaa kolmiulotteisen vekto- riavaruuden yli kunnanF2. Onneksi on my¨os helpompi tapa tarkastella t¨at¨a kahdeksan alkion kuntaa, jota merkit¨a¨an v¨aliaikaisesti GF(8).

Aloitetaan laskemalla muutama ensimm¨ainen muuttujanxpotenssi modulop(x) = x³+x+ 1:

x⁰ ≡1 x¹ ≡x x² ≡x² x³ ≡x+ 1 x⁴ ≡x²+x

x⁵ ≡x³+x² ≡x²+x+ 1 x⁶ ≡x³+x²+x≡x²+ 1 x⁷ ≡x³+x≡1,

miss¨a kaikki ovat mod (x³+x+ 1). T¨ast¨a seuraa, ett¨a muuttujan x mod (p(x)) po- tenssien muodostama jono on jaksollinen ja sen jakso on 7. Nyt m¨a¨aritell¨a¨an kunnas- saGF(8) muuttujanxekvivalenssiluokka alkionαavulla. Kolmiulotteisena vektorina α = [0,1,0]. Kun k¨aytet¨a¨an apuna taulukkoa, jossa lueteltiin muuttujan x potenssit modulo (x³+x+ 1), niin saadaan vastaava taulukko alkiolle α.

α⁰ = 1 α¹ =α α² =α² α³ =α+ 1 α⁴ =α² +α α⁵ =α² +α+ 1 α⁶ =α² + 1 α⁷ = 1.

Nyt ensimm¨aiset seitsem¨an potenssia ovat eri alkioita kunnassa GF(8). Koska kun- nassaGF(8) on ainoastaan seitsem¨an nollasta eroavaa alkiota, niin se tarkoittaa, ett¨a jokainen nollasta eroava alkio kunnassaGF(8) on alkionα potenssi, toisin sanoen al- kioαon kunnanGF(8) primitiivinen alkio. Voidaan siis k¨aytt¨a¨a alkiotaαlogaritmin kantalukuna, jos sovitaan, ett¨a

log_α(β) = k tarkoittaa, ett¨a α^k =β.

Saadaan siis taulukko kunnan GF(8) logartimeille ja potensseille:

24 2. ¨A ¨ARELLISET KUNNAT

β log_αβ k α^k

000 ? ? ?

001 0 0 001

010 1 1 010

011 3 2 100

100 2 3 011

101 6 4 110

110 4 5 111

111 5 6 101

Jos siis halutaan laskea esimerkiksi a·b = [110]·[111], niin taulukosta n¨ahd¨a¨an, ett¨a log_α(a) = 4 ja log_α(b) = 5, eli a·b = α⁴⁺⁵ =α⁹ =α² = [100]. (Huomaa, ett¨a alkion α potenssi t¨aytyy supistaa mod 7.)

Pienist¨a ¨a¨arellisist¨a kunnista primitiivisen alkion voi l¨oyt¨a¨a melko helposti kokei- lemalla, mutta isompiin kuntiin olisi hyv¨a saada jokin j¨arjestelm¨allinen menetelm¨a.

T¨allaisen menetelm¨an on kehitt¨anyt Gauss ja sit¨a kutsutaan Gaussin algoritmiksi.

Se esitt¨a¨a jonon kunnan alkioita α₁, α₂, . . . , α_k, miss¨a ord(α₁) < ord(α₂) < · · · <

ord(α_k) =q−1. Itse asiassa p¨atee ord(α_i)|ord(α_i+1), kaikille i= 1,2, . . . , k−1.

Gaussin algoritmi:

G1. Olkoot i = 1 ja α₁ mielivaltainen nollasta eroava alkio kunnassa F. Olkoon ord(α₁) =t₁.

G2. Jost_i =q−1, niin lopetetaan, sill¨aα_i on haluttu primitiivinen alkio.

G3. Muulloin valitaan nollasta eroava alkioβ ∈F, joka ei ole alkionα_i potenssi.

Olkoon ord(β) =s. Jos s=q−1, niin valitaan α_i+1 =β ja lopetetaan.

G4. Muulloin etsit¨a¨and |t_i ja e|s, joille syt(d, e) = 1 ja pyj(t_i, s) =e·d. Olkoot α_i+1 =α_i^tid ·β^se jat_i+1 =e·d. Sitten jatketaan kohdasta G2 saatujen α_i+1 ja t_i+1 kanssa.

Huomautuksia algoritmista:

• Kohdassa G3 huomataan, ett¨a alkion β kertaluku s ei jaa lukua t_i, koska yht¨al¨onx^ti = 1 kaikki ratkaisut ovat alkionα_ipotensseja. N¨ain ollen pyj(t_i, s) on luvunt_i moninkerta ja > t_i.

• Kohdassa G4 periaatteessa v¨aitet¨a¨an, ett¨a jos otetaan kaksi kokonaislukua m ja n, niin on mahdollista l¨oyt¨a¨a d | m ja e | n, joille syt(d, e) = 1 ja de= pyj(m, n).

• Kohdassa G4 alkionα

ti d

i kertaluku ondja alkionβ^se kertaluku one(ks. lemma 2.4.2). T¨ast¨a seuraa, ett¨a n¨aiden alkioiden tulon kertaluku ond·e= pyj(t_i, s), mik¨a selvi¨a¨a seuraavan lemman avulla.

Lemma 2.4.9. Olkoot ord(α) = m, ord(β) = n, miss¨a syt(m, n) = 1. T¨all¨oin ord(αβ) = mn.

Todistus. Oletetaan, ett¨a t= ord(αβ). T¨all¨oin

1 = (αβ)^t= (αβ)^tn =α^tnβ^tn =α^tn,

koska ord(β) =n. Nyt siis α^tn = 1, eli m|tn. Mutta koska syt(m, n) = 1, niin m |t.

Vastaavasti saadaan, ett¨an |t. Lis¨aksi koska syt(m, n) = 1, niin mn|t toisin sanoen