Ordnungen systematisch bestimmen

Aus $a^n\equiv1\pmod m$ folgt $\operatorname{ord}_m(a)\mid n$. Der Beweis teilt $n$ mit Rest durch die Ordnung und nutzt deren Minimalität.

Eulers Satz liefert $a^{\varphi(m)}\equiv1\pmod m$. Deshalb gilt stets $\operatorname{ord}_m(a)\mid\varphi(m)$.