Pierwiastek pierwotny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 [1].

Przykłady[edytuj | edytuj kod]

  • 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.

Przypisy