Primitiivijuurista T¨ass¨a lyhyess¨a koosteessa kerrotaan, ett¨a jokaiseen alkulukuun

Primitiivijuurista

T¨ass¨a lyhyess¨a koosteessa kerrotaan, ett¨a jokaiseen alkulukuun p > 2 liittyy ainakin yksi primitiivijuuri. Se on p:ll¨a jaoton luku a, jolle kongruenssi a^b ≡ 1 mod p ei p¨ade mil- l¨a¨an b < p−1. Asia ei ole aivan triviaali, mutta sen tunteminen n¨akyy olevan oletuk- sena joissakin matematiikkakilpailuteht¨aviss¨a. – Seikkaper¨aisemmin t¨ast¨a on esityksess¨a http://matematiikkakilpailut.fi/kirjallisuus/laajalukuteoriamoniste.pdf.

Kongruenssiyht¨ al¨ on juurien lukum¨ a¨ ar¨ a

Olkoon p alkuluku ja

f(x) =a_nxⁿ+a_n−1xⁿ⁻¹ +· · ·+a₀ (1) koknaislukukertoiminen n:nnen asteen polynomi sek¨a s.y.t.(a_n, p) = 1. Yht¨al¨o f(x) ≡ 0 mod p on n:nnen asteen kongruenssiyht¨al¨o. Osoitetaan induktiolla n:n suhteen, ett¨a t¨allaisella yht¨al¨oll¨a on enint¨a¨an n kesken¨a¨an modulo p ep¨akongruenttia ratkaisua. Jos n= 1, asia on selv¨a. Josax₁+b≡0 modpjaax₂+b≡0 modp, niina(x₁−x₂)≡0 mod p, ja koska s.y.t.(a, p) = 1, niin x₁ ≡ x₂ mod p. Oletetaan sitten, ett¨a v¨aite on tosi astetta k < n oleville kongruenssiyht¨al¨oille. Oletetaan, ett¨a f on niin kuin kaavassa (1) ja ett¨a on n + 1 kesken¨a¨an modulo p ep¨akongruenttia lukua x = x₁, x₂, . . . , x_n, x_n+1, jotka toteuttavat kongruenssiyht¨al¨on f(x)≡0 modp. Silloin

g(x) =f(x)−a_n(x−x₁)(x−x₂)· · ·(x−x_n)

on astetta n− 1 oleva polynomi, ja kongruenssiyht¨al¨oll¨a g(x) ≡ 0 mod p on n keske- n¨a¨an ep¨akongruenttia ratkaisua. Induktio-oletuksen mukaan t¨am¨a on mahdollista vain, jos g(x):n korkeimmanasteisen termin kerroin on jaollinen p:ll¨a. p¨a¨attely¨a jatkamalla tul- laan siihen, ett¨a polynoming(x) kaikki kertoimet ovatp:ll¨a jaollisia, joteng(x)≡0 mod p kaikilla x. Siis erityisesti g(x_n+1) ≡ 0 mod p. Mutta koska my¨os f(x_n+1) ≡ 0 mod p, on a_n(x_n+1−x₁)(x_n+1 −x₂)· · ·(x_n+1 −x_n) ≡ 0 mod p. T¨am¨a on mahdollista vain, jos jokin tulon tekij¨a on jaollinen p:ll¨a eli x_n+1 ≡ x_j mod p jollain j. T¨am¨a on ristiriidassa luvuista x_j tehdyn ep¨akongruenttisuusoletuksen kanssa, joten induktioaskel on otettu ja v¨aite todistettu.

Edellisest¨a tuloksesta seuraa, ett¨a kongruenssillaxⁿ−1≡0 modpon enint¨a¨annkesken¨a¨an ep¨akongruenttia ratkaisua.

Primitiivijuuren m¨ a¨ aritelm¨ a

Eulerin funktioφm¨a¨aritell¨a¨an niin, ett¨aφ(m) on niiden kokonaislukujena, 1≤a ≤n−1, lukum¨a¨ar¨a, joille s.y.t.(a, m) = 1. Eulerin lause sanoo, ett¨a a^φ(m) ≡1 mod m aina, kun s.y.t.(a, m) = 1.

Olkoon a > 1 ja s.y.t.(a, m) = 1. On olemassa lukuja γ, joille a^γ ≡ 1 mod m. Yksi t¨allainen onφ(m), mutta pienempikin luku voi tulla kyseeseen. Esimerkiksi 2³≡1 mod 7.

Pienin γ, jolle a^γ ≡ 1 mod m on a:n indeksi modulo m. Olkoon t¨am¨a pienin luku δ.

Sanotaan, ett¨a a kuuluu eksponenttiin δmod m.

2 Jos a kuuluu eksponenttiin δ modm ja jos 0≤p < q < δ, niin ei voi olla a^p ≡a^q modm.

Jos n¨ain olisi, olisia^p(a^q−p−1)≡0 modm, ja koska s.y.t.(a, m) = 1, olisia^q−p ≡1 modm, mik¨a olisi ristiriidassa δ:n minimiominaisuuden kanssa.

Jos a^γ ≡ a^γ mod m, niin γ ≡ γ mod δ. Olkoon nimitt¨ain γ = qδ+r ja γ = qδ +r, 0≤r, r < δ. Silloin a^γ =

a^δ_q

a^r ≡a^r modm ja vastaavasti a^γ ≡a^r modm. Edellisen kappaleen mukaan a^r ≡a^r mod mon mahdollinen vain, jos r =r eli γ −γ ≡0 modm.

– Jos γ ≡γ mod δ, niin γ =qδ+r ja γ =qδ+r, jolloin a^γ = a^δ_q

a^r ≡ a^r mod m ja samoin a^γ ≡a^rmod m, joten a^γ ≡a^γ modm.

Erityisesti a^γ ≡ 1 jos ja vain jos δ|γ. T¨aten jokaisella a se eksponentti, johon a kuuluu modm, on luvun φ(m) tekij¨a.

Luvut, jotka kuuluvat eksponenttiin φ(m) mod m ovat primitiivijuuria modulo m. Jos p on alkuluku, niinφ(p) =p−1.

Primitiivijuuret modulo alkuluku

Oletetaan, ett¨a x kuuluu eksponenttiin ab mod m. Silloin x^ab ≡1 mod m. Tarkastellaan lukua x^a. Oletetaan, ett¨a x^a kuuluu eksponenttiin δ modm. Silloin x^aδ ≡1 mod m. Yll¨a sanotuin nojalla (ab)|(aδ) joten b|δ. Mutta koska (x^a)^b ≡ 1 mod m, niin δ|b. Siis onkin δ=b. Oletuksesta, ett¨ax kuuluu eksponenttiin ab seuraa, ett¨ax^a kuuluu eksponenttiin b modulo m.

Olkoot a ja b kaksi lukua, joille s.y.t.(a, b) = 1. Kuulukoon x eksponenttiin a ja y eks- ponenttiin b modulo m. Tarkastellaan lukua xy. Oletetaan, ett¨a se kuuluu eksponenttiin δmod m. Silloin x^δy^δ ≡1 modm ja edelleenx^bδy^bδ ≡1 modm. Mutta t¨ast¨a seuraa, ett¨a x^bδ ≡1 modm ja edelleen, ett¨a a|bδ. Koska (a, b) = 1, on oltava a|δ. Samoin osoitetaan, ett¨ab|δ. Jos kaksi yheistekij¨at¨ont¨a lukua ovatδ:n tekij¨oit¨a, niiden tulokin on: ab|δ. Mutta toisaalta (xy)^ab = (x^a)^b(y^b)^a ≡ 1 mod m, joten δ|(ab). Siis ab = δ. Tulo xy kuuluu siis eksponenttiin ab.

Olkoon nyt p > 2 alkuluku. Luvut 1, 2, . . ., p−1 kuuluvat jokainen johonkin ekspo- nenttiin modp. Olkoot δ₁, δ₂, . . ., δ_r t¨allaiset eksponentit. Jokainen δ_j on luvun p−1 tekij¨a. Olkoon sittenτ n¨aiden lukujen pienin yhteinen monikerta. Luvullaτ on kanoninen alkulukuhajotelma τ = q₁^α1q^α₂²· · ·q_k^αk. Olkoon 1 ≤ s ≤ k. Jokin luvuista δ_j on jaollinen luvulla q_s^αs; olkoon se luku δ. Siis δ = aq_s^αs. Jos x on luku, joka kuuluu eksponenttiin δ, niin aikaisemmin sanotun perusteella x^a kuuluu eksponenttiin q_s^αs. Merkit¨a¨an lukua x^a x_s:ll¨a. Sama p¨atee kaikille s = 1, . . . , k. Voidaan muodostaa luku g=x₁x₂· · ·x_s. Koska eri luvuillax_s ei ole yhteisi¨a tekij¨oit¨a,g kuuluu eksponenttiin q₁^α1· · ·q^α_k^k =τ. Jokainen δ_j onτ:n tekij¨a. Jokaiselle luvuistax= 1, 2, . . . , p−1 p¨ateex^δj ≡1 modp jollainδ_j. Mutta silloin jokaiselle t¨allaisellex p¨atee x^τ ≡1 mod p.

Astetta τ olevalla kongruenssilla on enint¨a¨an τ eri ratkaisua. Siis p−1≤τ. Mutta koska jokainenδ_j onp−1:n tekij¨a, on my¨os lukujen δ_i pienin yhteinen monikerta eliτ on p−1:n tekij¨a. Siis τ ≤p−1, ja g on primitiivinen juuri modp.