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\;$.

Warunek konieczny i dostateczny istnienia

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

• potęgi liczb pierwszych nieparzystych ($n=p^a$,$a \in \mathbb{N}$);
• podwojone potęgi liczb pierwszych nieparzystych ($n=2 p^a$);
• liczby: 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,\ldots ,k}$ na mocy twierdzenia Eulera zachodzi:

$g^{\varphi(p_i^{a_i})} \equiv 1 \pmod {p_i^{a_i}}$

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 multyplikatywnej $\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 .

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\;$ sa: 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.

• Ażeby liczba była pierwiastkiem pierwotnym mod 15 jej reszta z dzielenia przez 3 musi być równa 2. Zatem jedynymi potencjalymi pierwiastkami mod 15 sa liczby: 2, 5, 8, 11, 14. żadna z nich nie jest pierwiastkiem, więc nie istnieje pierwiastek pierwotny mod 15.

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

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