Pierwiastek pierwotny

Pierwiastek pierwotny modulo $n$ to taka liczba, że jej potęgi dają wszystkie możliwe reszty modulo $n,$ które są względnie pierwsze z $n.$

Przykłady

• Kolejnymi resztami modulo 5 z $2^k$ są: 2, 4, 3, 1. Liczba 2 jest pierwiastkiem pierwotnym modulo 5.

• Kolejnymi resztami modulo 7 z $2^k$ są: 2, 4, 1, 2,... Liczba 2 nie jest pierwiastkiem pierwotnym modulo 7.

• Kolejnymi resztami modulo 15 z $2^k$ są: 2, 4, 8, 1, 2,... Liczba 2 nie jest pierwiastkiem pierwotnym modulo 15.

• Aby liczba była pierwiastkiem pierwotnym modulo 15, jej reszta z dzielenia przez 3 musi być równa 2. Zatem jedynymi potencjalnymi pierwiastkami mod 15 są liczby: 2, 5, 8, 11, 14. Żadna z nich nie jest pierwiastkiem pierwotnym, więc takowy nie istnieje modulo 15.

• Pierwiastkiem pierwotnym modulo 2 jest 1, a pierwiastkiem pierwotnym modulo 4 jest 3.

Warunek konieczny i dostateczny istnienia

Pierwiastek pierwotny modulo $n$ istnieje wtedy i tylko wtedy, gdy $n$ jest jedną z następujących liczb:

• potęgą liczb pierwszych nieparzystych $(n=p^a,a\in \mathbb{N}),$
• podwojoną potęgą liczb pierwszych nieparzystych $(n=2p^a,a\in \mathbb{N}),$
• liczbą 2 i 4.

Dowód konieczności dla $n$ niebędących potęgami 2

Jeśli $n=p_1^{a_1}\cdots p_k^{a_k},$ a $g$ jest pierwiastkiem pierwotnym modulo n, to dla każdego $i\in 1,\dots ,k$ na mocy twierdzenia Eulera zachodzi:

$g^{\phi (p_i^{a_i})}\equiv 1(\mathrm{mod}{p}_i^{a_i}),$

gdzie $\phi (n)$ jest tocjentem Eulera

Zatem dla dowolnej liczby $N$ podzielnej przez każdą z liczb $\phi (p_i^{a_i})$ zachodzi:

$g^N\equiv 1(\mathrm{mod}n).$

Gdyby wśród liczb $\phi (p_i^{a_i})$ były co najmniej dwie parzyste, to za liczbę N można by przyjąć (korzystając z własności funkcji Eulera dla iloczynu liczb względnie pierwszych):

$\frac{1}{2}\phi (n)=\frac{1}{2}\phi (p_1^{a_1})\cdots \phi (p_k^{a_k}),$

co przeczyłoby temu, że g jest pierwiastkiem pierwotnym, gdyż wtedy najmniejszą liczbą o tej własności jest $\phi (n).$

Na mocy wzoru:$\phi (p^k)=p^{k-1}(p-1),$ dla liczb pierwszych nieparzystych oraz potęg dwójki większych od 1 funkcja Eulera przyjmuje wartości parzyste. Zatem w rozwinięciu $n$ na czynniki pierwsze nie mogą występować dwie różne liczby pierwsze nieparzyste, a jeśli liczba ma dzielnik nieparzysty, to dwójka występuje w co najwyżej pierwszej potędze.

Dowód istnienia dla liczb pierwszych

Dla dowolnego $d$ – dzielnika liczby $(p-1)$ wielomian nad ciałem ${\mathbb{Z}}_p:$ $x^d-1$ ma $d$ różnych pierwiastków, ponieważ wielomian $x^{p-1}-1$ ma $p-1$ różnych pierwiastków na mocy małego twierdzenia Fermata, wielomian stopnia $p-1-d$ ma co najwyżej $p-1-d$ różnych pierwiastków, a zachodzi $x^{p-1}-1=(x^d-1)w(x),$ gdzie $w(x)$ jest stopnia $p-1-d.$

Niech $p-1=p_1^{a_1}\cdots p_k^{a_k}.$ Każdy wielomian $x^{p_i^{a_i}}-1$ ma $p_i^{a_i}$ różnych pierwiastków, więc wśród nich istnieje taki (oznaczmy go $r_i$), który nie jest pierwiastkiem wielomianu $x^{p_i^{a_i-1}}-1.$ Zatem $r_i$ jest elementem grupy multiplikatywnej ${\mathbb{Z}}_p$ o rzędzie $p_i^{a_i}.$ Zgodnie z twierdzeniem o rzędzie iloczynu elementów o rzędach względnie pierwszych w grupie przemiennej iloczyn wszystkich $r_i$ ma rząd $p-1$ i jest generatorem grupy.

Pełny dowód twierdzenia znajduje się w.

W języku algebry: element $g$ w grupie multiplikatywnej reszt modulo $n$ względnie pierwszych z modułem, taki że $rz(g)=\phi (n)$ (funkcja φ Eulera) nazywamy pierwiastkiem pierwotnym.