Pierwiastek pierwotny

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

Przykłady

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

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

• Kolejnymi resztami modulo 15 z ${\displaystyle 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 ${\displaystyle n}$ istnieje wtedy i tylko wtedy, gdy ${\displaystyle n}$ jest jedną z następujących liczb:

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

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

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

${\displaystyle g^{\varphi (p_{i}^{a_{i}})}\equiv 1{\pmod {p_{i}^{a_{i}}}},}$

gdzie ${\displaystyle \varphi (n)}$ jest tocjentem Eulera

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

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

Gdyby wśród liczb ${\displaystyle \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):

${\displaystyle {\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 ${\displaystyle \varphi (n).}$

Na mocy wzoru:${\displaystyle \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 ${\displaystyle 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 ${\displaystyle d}$ – dzielnika liczby ${\displaystyle (p-1)}$ wielomian nad ciałem ${\displaystyle \mathbb {Z} _{p}{:}}$ ${\displaystyle x^{d}-1}$ ma ${\displaystyle d}$ różnych pierwiastków, ponieważ wielomian ${\displaystyle x^{p-1}-1}$ ma ${\displaystyle p-1}$ różnych pierwiastków na mocy małego twierdzenia Fermata, wielomian stopnia ${\displaystyle p-1-d}$ ma co najwyżej ${\displaystyle p-1-d}$ różnych pierwiastków, a zachodzi ${\displaystyle x^{p-1}-1=(x^{d}-1)w(x),}$ gdzie ${\displaystyle w(x)}$ jest stopnia ${\displaystyle p-1-d.}$

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

Pełny dowód twierdzenia znajduje się w^[1].

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

Przypisy