Pierwiastek pierwotny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Przykłady[edytuj]

  • Kolejnymi resztami modulo 5 z są: 2, 4, 3, 1. Liczba 2 jest pierwiastkiem pierwotnym modulo 5.
  • Kolejnymi resztami modulo 7 z sa: 2, 4, 1, 2, ... . Liczba 2 nie jest pierwiastkiem pierwotnym modulo 7.
  • Kolejnymi resztami modulo 15 z 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 potencjalnymi 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.


Warunek konieczny i dostateczny istnienia[edytuj]

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

  • potęgi liczb pierwszych nieparzystych (,);
  • podwojone potęgi liczb pierwszych nieparzystych ();
  • liczby: 2 i 4;

Dowód konieczności dla n niebędących potęgami 2[edytuj]

Jeśli , a jest pierwiastkiem pierwotnym modulo n, to dla każdego na mocy twierdzenia Eulera zachodzi:

gdzie jest tocjentem Eulera

Zatem dla dowolnej liczby podzielnej przez każdą z liczb zachodzi:

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

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

Na mocy wzoru:, dla liczb pierwszych nieparzystych oraz potęg dwójki większych od 1 funkcja Eulera przyjmuje wartości parzyste. Zatem w rozwinięciu 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]

Dla dowolnego - dzielnika liczby wielomian nad ciałem : ma różnych pierwiastków, ponieważ wielomian ma różnych pierwiastków na mocy małego twierdzenia Fermata, wielomian stopnia ma co najwyżej różnych pierwiastków, a zachodzi , gdzie jest stopnia .

Niech . Każdy wielomian ma różnych pierwiastków, więc wśród nich istnieje taki (oznaczmy go ), który nie jest pierwiastkiem wielomianu . Zatem jest elementem grupy multyplikatywnej o rzędzie . Zgodnie z twierdzeniem o rzędzie iloczynu elementów o rzędach względnie pierwszych w grupie przemiennej iloczyn wszystkich ma rząd i jest generatorem grupy.

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


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