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^{\varphi (p_{i}^{a_{i}})}\equiv 1{\pmod {p_{i}^{a_{i}}}},$

gdzie $\varphi (n)$ jest tocjentem Eulera

Zatem dla dowolnej liczby $N$ podzielnej przez każdą z liczb $\varphi (p_{i}^{a_{i}})$ zachodzi:

$g^{N}\equiv 1{\pmod {n}}.$

Gdyby wśród liczb $\varphi (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}}\varphi (n)={\frac {1}{2}}\varphi (p_{1}^{a_{1}})\cdots \varphi (p_{k}^{a_{k}}),$

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

Na mocy wzoru:$\varphi (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)=\varphi (n)$ (funkcja φ Eulera) nazywamy pierwiastkiem pierwotnym.