Primitivni korijen

Primitivni korijen jedan je od temeljnih pojmova elementarne teorije brojeva, odnosno njene grane, modularne aritmetike.

Kažemo da je broj [math]\displaystyle{ g }[/math] primitivni korijen modulo [math]\displaystyle{ n }[/math] ako je svaki broj relativno prost s [math]\displaystyle{ n }[/math] kongruentan s potencijom broja [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ n }[/math]. Drugim riječima, [math]\displaystyle{ g }[/math] je primitivni korijen modulo [math]\displaystyle{ n }[/math] ako za svaki cijeli broj relativno prost s [math]\displaystyle{ n }[/math] postoji neki cijeli broj [math]\displaystyle{ k }[/math] za koji je [math]\displaystyle{ g^k \equiv a \pmod n }[/math].

Broj [math]\displaystyle{ k }[/math] zovemo indeks ili diskretni logaritam od [math]\displaystyle{ a }[/math] po bazi [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ n }[/math]. Uočimo da je [math]\displaystyle{ g }[/math] primitivni korijen modulo [math]\displaystyle{ n }[/math] ako i samo ako je [math]\displaystyle{ g }[/math] generator multiplikativne grupe cijelih brojeva modulo [math]\displaystyle{ n }[/math].

Dodajmo da se, ako su [math]\displaystyle{ a }[/math] i [math]\displaystyle{ n }[/math] relativno prosti prirodni brojevi, najmanji prirodni broj [math]\displaystyle{ d }[/math] sa svojstvom da je [math]\displaystyle{ a^d \equiv 1 \pmod n }[/math] zove red od [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math]. Još kažemo da [math]\displaystyle{ a }[/math] pripada eksponentu [math]\displaystyle{ d }[/math] modulo [math]\displaystyle{ n }[/math].

Alternativna definicija primitivnog korijena kaže da ako je red broja [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math] jednak [math]\displaystyle{ \varphi{(n)} }[/math] tada je [math]\displaystyle{ a }[/math] primitivni korijen modulo [math]\displaystyle{ n }[/math].

Teoremi vezani uz primitivne korijene

Neka je [math]\displaystyle{ d }[/math] red od [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ n }[/math]. Tada za prirodan broj [math]\displaystyle{ k }[/math] vrijedi [math]\displaystyle{ a^k \equiv 1 \pmod n }[/math] ako i samo ako [math]\displaystyle{ d \vert k }[/math]. Posebno, [math]\displaystyle{ d \vert \varphi{(n)} }[/math].

Dokaz. Ako [math]\displaystyle{ d \vert k }[/math], recimo [math]\displaystyle{ k = d \cdot l }[/math], onda je [math]\displaystyle{ a^k \equiv {(a^d)}^l \equiv 1 \pmod n }[/math]. Podijelimo sada [math]\displaystyle{ k }[/math] sa [math]\displaystyle{ d }[/math], pa dobivamo [math]\displaystyle{ k = q \cdot d + r }[/math], gdje je [math]\displaystyle{ 0 \leq r \lt d. }[/math] Sada je [math]\displaystyle{ 1 \equiv a^k \equiv a^{qd+r} \equiv {(a^d)}^q \cdot a^r \equiv a^r \pmod n }[/math] pa zbog minimalnosti od [math]\displaystyle{ d }[/math] slijedi da je [math]\displaystyle{ r = 0 }[/math], tj. [math]\displaystyle{ d \vert k }[/math].

Neka svojstva

Neka su [math]\displaystyle{ r, p, r \lt 5 \leq p }[/math] fiksirani prosti brojevi. Promotrimo koje ostatke pri dijeljenju s [math]\displaystyle{ p }[/math] redom daju elementi skupa [math]\displaystyle{ S = \{r, r^2, r^3, ..., r^{p - 1}\} }[/math]. Prva stvar koju treba uočiti je ta da će, prema Eulerovom teoremu, vrijediti [math]\displaystyle{ r^{p - 1} \equiv 1 \pmod p }[/math]. Zbog ovoga će se ostatci modulo p za [math]\displaystyle{ r^p, r^{p + 1}, r^{p + 2}, ..., r^{2p - 1} }[/math] redom podudarati sa ostatcima koji daju brojevi [math]\displaystyle{ r, r^2, r^3, ... }[/math] modulo p. Drugim riječima, vrijedit će [math]\displaystyle{ r \equiv r^p \pmod p, r^2 \equiv r^{p + 1} \pmod p }[/math], i tako dalje sve do [math]\displaystyle{ r^k \equiv r^{p + k} }[/math].

Zato će, za proučavanje ostataka brojeva u formi [math]\displaystyle{ r^k }[/math] (za bilo koji [math]\displaystyle{ k \in \mathbb{N} }[/math]) modulo p biti dovoljno promatrati svojstva skupa [math]\displaystyle{ S }[/math]. Uočimo još da prvi element skupa [math]\displaystyle{ S }[/math], broj [math]\displaystyle{ r }[/math], ne može davati ostatak 1 modulo p. Upravo ta pojavljivanja ostatka 1 u nizu brojeva [math]\displaystyle{ r, r^2, r^3, ..., r^{p - 1} }[/math] će zato određivati cikličku strukturu skupa [math]\displaystyle{ S }[/math], što će se dolje podrobnije objasniti.

Prva lema. Ne postoje dva uzastopna člana skupa [math]\displaystyle{ S }[/math] koja su kongruentna modulo p, tj. ne postoji [math]\displaystyle{ k \in \mathbb{N} }[/math] takav da je [math]\displaystyle{ r^k \equiv r^{k + 1} \pmod p }[/math]. Dokaz. Pretpostavimo da takav [math]\displaystyle{ k }[/math] postoji. Onda je [math]\displaystyle{ r^k \equiv r^{k + 1} }[/math] iz čega slijedi da [math]\displaystyle{ p }[/math] dijeli [math]\displaystyle{ r^k(r - 1), }[/math] što nije moguće jer su [math]\displaystyle{ r^k, p }[/math] relativno prosti te [math]\displaystyle{ r - 1 \not\mid p }[/math].

Druga lema. Neka je [math]\displaystyle{ x }[/math] najmanji broj takav da je [math]\displaystyle{ r^x \equiv 1 \pmod p }[/math]. Ako je [math]\displaystyle{ r^{x} \equiv r^y \pmod p, x \lt y }[/math] tada je [math]\displaystyle{ y }[/math] višekratnik od [math]\displaystyle{ x }[/math]. Dokaz. Naime, zapišimo [math]\displaystyle{ y }[/math] u obliku [math]\displaystyle{ y = x + n, n \in \mathbb{N} }[/math]. Tada iz tvrdnje leme slijedi [math]\displaystyle{ p \vert r^x(r^n - 1) }[/math]. Jedina mogućnost je da je [math]\displaystyle{ r^n \equiv 1 \pmod p }[/math]. Kako je [math]\displaystyle{ x }[/math] najmanji broj s ovim svojstvom slijedi da su brojevi [math]\displaystyle{ r^x, r^{2x}, r^{3x}, ... }[/math] skupa [math]\displaystyle{ S }[/math] kongruentni 1 modulo p. Isto tako, znači da će se ostatci brojeva u nizu [math]\displaystyle{ r, r^2, ..., r^x }[/math] redom ciklički ponavljati i poklapati sa ostatcima brojeva u nizu [math]\displaystyle{ r^{x + 1}, r^{x + 2}, ..., r^{2x} }[/math] i tako sve do [math]\displaystyle{ r^{p - 1 - x + 1} = r^{p - x}, r^{p - x + 1}, ..., r^{p - 1} }[/math].

Treća lema. Ako je najmanji broj [math]\displaystyle{ x }[/math] takav da je [math]\displaystyle{ r^x \equiv 1 \pmod p }[/math] jednak [math]\displaystyle{ x = p - 1 }[/math], tada skup [math]\displaystyle{ S }[/math] čini potpun sustav ostatka do na nulu (bez nule). Prvo, očito je da niti jedan od elemenata skupa [math]\displaystyle{ S }[/math] ne daje ostatak 0 pri dijeljenju s p. Dalje, pretpostavljamo da vrijedi [math]\displaystyle{ r^k \equiv r^{k + n} \pmod p }[/math] za [math]\displaystyle{ n \lt p - 1 }[/math]. Ovo povlači [math]\displaystyle{ r^n \equiv 1 \pmod p }[/math], što je u kontradikciji s pretpostavkom da je [math]\displaystyle{ x = p - 1. }[/math]

Četvrta lema. Ako je [math]\displaystyle{ r^x \equiv 1 \pmod p }[/math], tada [math]\displaystyle{ x | p - 1 }[/math]. Dokaz. Pretpostavimo da je [math]\displaystyle{ 2 \leq x \leq p - 3 }[/math] (prema svemu gore navedenome jasno je da vrijedi [math]\displaystyle{ x \neq 2, x \neq p - 2 }[/math]) najmanji prirodni broj takav da je [math]\displaystyle{ r^x \equiv 1 \pmod p, x \not\mid p - 1 }[/math].

Pretpostavimo još da je [math]\displaystyle{ r^x }[/math] prvi broj u nizu [math]\displaystyle{ r, r^2, ..., r^x }[/math] koji je kongruentan 1 modulo p. Pokazat ćemo da ovo ne smanjuje općenitost.

Dokazali smo gore da su ostatci [math]\displaystyle{ r, r^2, ..., r^{x - 1} }[/math] međusobno različiti. Očito je da će se, nakon [math]\displaystyle{ r^{x} }[/math], idućih [math]\displaystyle{ x }[/math] ostataka ponavljati, i onda sljedećih [math]\displaystyle{ x }[/math], itd. Uz to, uočimo da treba biti [math]\displaystyle{ r^{p - 1} \equiv r_1, ..., r^{p - 1 + x} \equiv r^x }[/math] modulo p. No, dolazimo do kontradikcije jer, bi se, zbog toga što [math]\displaystyle{ x \not\mid p - 1 }[/math], ostatak koji daje broj [math]\displaystyle{ r^x }[/math] pojavio na mjestu prije [math]\displaystyle{ r^{p - 1 + x} }[/math], što je u suprotnosti s pretpostavkom o minimalnosti broja [math]\displaystyle{ x }[/math].

Ako pak postoji [math]\displaystyle{ r^m \equiv 1 \pmod p, 1 \lt m \lt x, m | p - 1 }[/math] očito je da bi [math]\displaystyle{ x }[/math] "narušio" ponavljanja ostataka koja bi se tada trebala pojaviti.

Ovime je dokazano da ako je [math]\displaystyle{ r^x \equiv 1 \pmod p }[/math] mora biti [math]\displaystyle{ x | p - 1 }[/math].

Primjeri

Navest ćemo dva elementarna primjera.

Potencije [math]\displaystyle{ 2, 2^2, 2^3, 2^4, }[/math] modulo 5 će redom dati ostatke 2, 4, 3, 1 pri dijeljenju s 5. Dakle, ovdje nema cikličkog ponavljanja, jer se ostatak 1 prvi puta pojavljuje tek na posljednjem mjestu niza, ali su zato navedeni svi ostaci, osim nule, modulo 5.

Za primjer cikličkog ponavljanja ostataka, uzmimo potencije [math]\displaystyle{ 2, 2^2, , ..., 2^6 }[/math] modulo 7. Ovi brojevi redom daju ostatke 2, 4, 1, 2, 4, 1 modulo 7. Vidimo da očito nisu navedeni svi ostatci modulo 7, ali se zato ostatci uredno ciklički ponavljaju jer se ostatak 1 pojavio na trećem umjesto na posljednjem mjestu, za razliku od prethodnog primjera.