Primitivni korijen

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

Kažemo da je broj Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle g} primitivni korijen modulo $n$ ako je svaki broj relativno prost s $n$ kongruentan s potencijom broja Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle g} modulo $n$. Drugim riječima, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \varphi {(n)}} 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 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 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} 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 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} . 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 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 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, 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 \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 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 = 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 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} 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 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 = 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 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 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 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 = 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r,p,r<5\leq p} fiksirani prosti brojevi. Promotrimo koje ostatke pri dijeljenju s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r,r^{2},r^{3},...} modulo p. Drugim riječima, vrijedit će Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r\equiv r^{p}{\pmod {p}},r^{2}\equiv r^{p+1}{\pmod {p}}} , i tako dalje sve do Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{k}\equiv r^{p+k}} .

Zato će, za proučavanje ostataka brojeva u formi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{k}} (za bilo koji Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k\in \mathbb {N} } takav da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{k}\equiv r^{k+1}{\pmod {p}}} . Dokaz. Pretpostavimo da takav $k$ postoji. Onda je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{k}\equiv r^{k+1}} iz čega slijedi da Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p} dijeli Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{k}(r-1),} što nije moguće jer su $r^{k},p$ relativno prosti te Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r-1\not \mid p} .

Druga lema. Neka je $x$ najmanji broj takav da je $r^{x}\equiv 1{\pmod {p}}$. Ako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{x}\equiv r^{y}{\pmod {p}},x<y} tada je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y} višekratnik od $x$. Dokaz. Naime, zapišimo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y} u obliku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle y=x+n,n\in \mathbb {N} } . Tada iz tvrdnje leme slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 sa ostatcima brojeva u nizu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{x+1},r^{x+2},...,r^{2x}} i tako sve do Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x=p-1.}

Četvrta lema. Ako je $r^{x}\equiv 1{\pmod {p}}$, tada Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x|p-1} . Dokaz. Pretpostavimo da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2\leq x\leq p-3} (prema svemu gore navedenome jasno je da vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $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. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x|p-1} .

Primjeri

Navest ćemo dva elementarna primjera.

Potencije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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.