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(\mathrm{mod}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(\mathrm{mod}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 $\phi (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(\mathrm{mod}n)$ ako i samo ako $d|k$. Posebno, $d|\phi (n)$.

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

Neka svojstva

Neka su $r,p,r<5\le 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(\mathrm{mod}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(\mathrm{mod}p),r^2\equiv r^{p+1}(\mathrm{mod}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}(\mathrm{mod}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\mid ̸p$.

Druga lema. Neka je $x$ najmanji broj takav da je $r^x\equiv 1(\mathrm{mod}p)$. Ako je $r^x\equiv r^y(\mathrm{mod}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|r^x(r^n-1)$. Jedina mogućnost je da je $r^n\equiv 1(\mathrm{mod}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(\mathrm{mod}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}(\mathrm{mod}p)$ za $n<p-1$. Ovo povlači $r^n\equiv 1(\mathrm{mod}p)$, što je u kontradikciji s pretpostavkom da je $x=p-1.$

Četvrta lema. Ako je $r^x\equiv 1(\mathrm{mod}p)$, tada $x|p-1$. Dokaz. Pretpostavimo da je $2\le x\le p-3$ (prema svemu gore navedenome jasno je da vrijedi $x\ne 2,x\ne p-2$) najmanji prirodni broj takav da je $r^x\equiv 1(\mathrm{mod}p),x\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\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(\mathrm{mod}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(\mathrm{mod}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.