Primitivni korijen jedan je od temeljnih pojmova elementarne teorije brojeva, odnosno njene grane, modularne aritmetike.
Kažemo da je broj primitivni korijen modulo ako je svaki broj relativno prost s kongruentan s potencijom broja
modulo . Drugim riječima, je primitivni korijen modulo ako za svaki cijeli broj relativno prost s postoji neki cijeli broj za koji je .
Broj zovemo indeks ili diskretni logaritam od po bazi modulo . Uočimo da je primitivni korijen modulo ako i samo ako je generator multiplikativne grupe cijelih brojeva modulo .
Dodajmo da se, ako su i relativno prosti prirodni brojevi, najmanji prirodni broj sa svojstvom da je zove red od modulo . Još kažemo da pripada eksponentu modulo .[1]
Alternativna definicija primitivnog korijena kaže da ako je red broja modulo jednak tada je primitivni korijen modulo .
Neka je red od modulo . Tada za prirodan broj vrijedi ako i samo ako . Posebno, .
Dokaz. Ako , recimo , onda je . Podijelimo sada sa , pa dobivamo , gdje je Sada je pa zbog minimalnosti od slijedi da je , tj. .
Neka su fiksirani prosti brojevi. Promotrimo koje ostatke pri dijeljenju s redom daju elementi skupa . Prva stvar koju treba uočiti je ta da će, prema Eulerovom teoremu, vrijediti . Zbog ovoga će se ostatci modulo p za redom podudarati s ostatcima koji daju brojevi modulo p. Drugim riječima, vrijedit će , i tako dalje sve do .
Zato će, za proučavanje ostataka brojeva u formi (za bilo koji ) modulo p biti dovoljno promatrati svojstva skupa . Uočimo još da prvi element skupa , broj , ne može davati ostatak 1 modulo p. Upravo ta pojavljivanja ostatka 1 u nizu brojeva će zato određivati cikličku strukturu skupa , što će se dolje podrobnije objasniti.
Prva lema. Ne postoje dva uzastopna člana skupa koja su kongruentna modulo p, tj. ne postoji takav da je . Dokaz. Pretpostavimo da takav postoji. Onda je iz čega slijedi da dijeli što nije moguće jer su relativno prosti te .
Druga lema. Neka je najmanji broj takav da je . Ako je tada je
višekratnik od . Dokaz. Naime, zapišimo u obliku . Tada iz tvrdnje leme slijedi . Jedina mogućnost je da je . Kako je najmanji broj s ovim svojstvom slijedi da su brojevi skupa kongruentni 1 modulo p. Isto tako, znači da će se ostatci brojeva u nizu redom ciklički ponavljati i poklapati s ostatcima brojeva u nizu i tako sve do .
Treća lema. Ako je najmanji broj takav da je jednak , tada skup čini potpun sustav ostatka do na nulu (bez nule). Prvo, očito je da niti jedan od elemenata skupa ne daje ostatak 0 pri dijeljenju s p. Dalje, pretpostavljamo da vrijedi za . Ovo povlači , što je u kontradikciji s pretpostavkom da je
Četvrta lema. Ako je , tada . Dokaz. Pretpostavimo da je (prema svemu gore navedenome jasno je da vrijedi ) najmanji prirodni broj takav da je .
Pretpostavimo još da je prvi broj u nizu koji je kongruentan 1 modulo p. Pokazat ćemo da ovo ne smanjuje općenitost.
Dokazali smo gore da su ostatci međusobno različiti. Očito je da će se, nakon , idućih ostataka ponavljati, i onda sljedećih , itd. Uz to, uočimo da treba biti modulo p. No, dolazimo do kontradikcije jer, bi se, zbog toga što , ostatak koji daje broj pojavio na mjestu prije , što je u suprotnosti s pretpostavkom o minimalnosti broja .
Ako pak postoji očito je da bi "narušio" ponavljanja ostataka koja bi se tada trebala pojaviti.
Ovime je dokazano da ako je mora biti .
Navest ćemo dva elementarna primjera.
Potencije 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 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.
- ↑ Andrej Dujella, Teorija brojeva, Školska knjiga, 2019.