Pierwiastek pierwotny

liczba

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

PrzykładyEdytuj

  • 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 są 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 istnieniaEdytuj

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

  • potęgą liczb pierwszych nieparzystych  
  • podwojoną potęgą liczb pierwszych nieparzystych  
  • liczbą 2 i 4.

Dowód konieczności dla   niebędących potęgami 2Edytuj

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 pierwszychEdytuj

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 multiplikatywnej   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   w grupie multiplikatywnej reszt modulo   względnie pierwszych z modułem, taki że   (funkcja φ Eulera) nazywamy pierwiastkiem pierwotnym.

PrzypisyEdytuj

  1. Wacław Sierpiński, Teoria liczb, Monografie Matematyczne 19, rozdział VIII.