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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n} ako je svaki broj relativno prost s Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k} za koji je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle g^{k}\equiv a{\pmod {n}}} .

Broj Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle g} primitivni korijen modulo $n$ ako i samo ako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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, 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r} , ne može davati ostatak 1 modulo p. Upravo ta pojavljivanja ostatka 1 u nizu brojeva Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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 $S$ koja su kongruentna modulo p, tj. ne postoji $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle x} najmanji broj takav da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{k}\equiv r^{k+n}{\pmod {p}}} za $n<p-1$. Ovo povlači Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\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. (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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r^{x}} pojavio na mjestu prije Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 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^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 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} 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 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^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.