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