Es sei
durch die Bedingung
-
festgelegt. Wir betrachten alle Vielfachen
,
. Die Menge all dieser Vielfachen ist selbst ganz
, da ja
eine Einheit und daher die Multiplikation mit
eine Bijektion ist. Es ist
für
. Daher ist
. Deshalb gilt
und somit
-

Durch kürzen mit
(das ist eine Einheit)
ergibt sich
-

und
das Euler-Kriterium,
nämlich
-

liefert das Ergebnis.