Primitivni korijen

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

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

Broj $k$ zovemo indeks ili diskretni logaritam od $a$ po bazi $g$ modulo $n$. Uočimo da je $g$ primitivni korijen modulo $n$ ako i samo ako je $g$ generator multiplikativne grupe cijelih brojeva modulo $n$.

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

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

Teoremi vezani uz primitivne korijene

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

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

Neka svojstva

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

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

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

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

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

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

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

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

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

Ovime je dokazano da ako je $r^{x}\equiv 1{\pmod {p}}$ mora biti $x|p-1$.

Primjeri

Navest ćemo dva elementarna primjera.

Potencije $2,2^{2},2^{3},2^{4},$ 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 $2,2^{2},...,2^{6}$ 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.