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 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.
Warunek konieczny i dostateczny istnienia 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 2 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: