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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } ako i samo ako je $g$ generator multiplikativne grupe cijelih brojeva modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } .

Dodajmo da se, ako su $a$ i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } relativno prosti prirodni brojevi, najmanji prirodni broj $d$ sa svojstvom da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^d \equiv 1 \pmod n } zove red od $a$ modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } . Još kažemo da $a$ pripada eksponentu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } modulo $n$.

Alternativna definicija primitivnog korijena kaže da ako je red broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} modulo $n$ jednak Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi{(n)} } tada je $a$ primitivni korijen modulo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Teoremi vezani uz primitivne korijene

Neka je $d$ red od Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} modulo $n$. Tada za prirodan broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} vrijedi $a^{k}\equiv 1{\pmod {n}}$ ako i samo ako Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \vert k} . Posebno, $d\vert \varphi {(n)}$.

Dokaz. Ako Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \vert k} , recimo $k=d\cdot l$, onda je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a^k \equiv {(a^d)}^l \equiv 1 \pmod n } . Podijelimo sada $k$ sa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} , pa dobivamo $k=q\cdot d+r$, gdje je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} slijedi da je $r=0$, tj. Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \vert k} .

Neka svojstva

Neka su $r,p,r<5\leq p$ fiksirani prosti brojevi. Promotrimo koje ostatke pri dijeljenju s Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 sa ostatcima koji daju brojevi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^k \equiv r^{p + k}} .

Zato će, za proučavanje ostataka brojeva u formi $r^{k}$ (za bilo koji Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \in \mathbb{N}} ) modulo p biti dovoljno promatrati svojstva skupa $S$. Uočimo još da prvi element skupa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} , broj $r$, ne može davati ostatak 1 modulo p. Upravo ta pojavljivanja ostatka 1 u nizu brojeva Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} koja su kongruentna modulo p, tj. ne postoji $k\in \mathbb {N}$ takav da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^k \equiv r^{k + 1} \pmod p} . Dokaz. Pretpostavimo da takav $k$ postoji. Onda je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^k \equiv r^{k + 1}} iz čega slijedi da $p$ dijeli Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^k(r - 1),} što nije moguće jer su $r^{k},p$ relativno prosti te Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r - 1 \not\mid p} .

Druga lema. Neka je $x$ najmanji broj takav da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^x \equiv 1 \pmod p} . Ako je $r^{x}\equiv r^{y}{\pmod {p}},x<y$ tada je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} višekratnik od $x$. Dokaz. Naime, zapišimo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} u obliku $y=x+n,n\in \mathbb {N}$. Tada iz tvrdnje leme slijedi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p \vert r^x(r^n - 1)} . Jedina mogućnost je da je $r^{n}\equiv 1{\pmod {p}}$. Kako je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} najmanji broj s ovim svojstvom slijedi da su brojevi $r^{x},r^{2x},r^{3x},...$ skupa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 sa ostatcima brojeva u nizu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} takav da je $r^{x}\equiv 1{\pmod {p}}$ jednak Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} ne daje ostatak 0 pri dijeljenju s p. Dalje, pretpostavljamo da vrijedi $r^{k}\equiv r^{k+n}{\pmod {p}}$ za Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n < p - 1} . Ovo povlači $r^{n}\equiv 1{\pmod {p}}$, što je u kontradikciji s pretpostavkom da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = p - 1.}

Četvrta lema. Ako je $r^{x}\equiv 1{\pmod {p}}$, tada Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x | p - 1 } . Dokaz. Pretpostavimo da je $2\leq x\leq p-3$ (prema svemu gore navedenome jasno je da vrijedi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r, r^2, ..., r^{x - 1} } međusobno različiti. Očito je da će se, nakon $r^{x}$, idućih Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} ostataka ponavljati, i onda sljedećih $x$, itd. Uz to, uočimo da treba biti Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r^x} pojavio na mjestu prije $r^{p-1+x}$, što je u suprotnosti s pretpostavkom o minimalnosti broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .

Ako pak postoji $r^{m}\equiv 1{\pmod {p}},1<m<x,m|p-1$ očito je da bi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.