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

• Kolejnymi resztami modulo 5 z są: 2, 4, 3, 1. Liczba 2 jest pierwiastkiem pierwotnym modulo 5.

• Kolejnymi resztami modulo 7 z są: 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.

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

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.

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.

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.