Ordnung

Die Ordnung von $a$ modulo $n$ ist das minimale $k$, welches den Satz von Euler erfüllt. Wir haben also ${\mathrm{ord}}_n(a)=\min \left\{k\in \mathbb{N}:a^k\equiv 1\mathrm{mod}n\right\}.$

Eigenschaften

$a^k\equiv 1\mathrm{mod}n⟺{\mathrm{ord}}_n(a)\mid k$ $\left\{k\in \mathbb{N}:a^k\equiv 1\mathrm{mod}n\right\}=\mathbb{N}\cdot {\mathrm{ord}}_n(a)=\left\{\ell \cdot {\mathrm{ord}}_n(a):\ell \in \mathbb{N}\right\}$ Also alle Vielfachen der Ordnung von $a$ modulo $n$ erfüllen auch den Satz von Euler.

${\mathrm{ord}}_n(a)\mid \phi (n)$ $a^{k_1}\equiv a^{k_2}\mathrm{mod}n⟺k_1\equiv k_2\mathrm{mod}{\mathrm{ord}}_n(a)$ Wir können so also leicht im Exponenten rechnen.

${\mathrm{ord}}_n\left(a^k\right)=\frac{{\mathrm{ord}}_n(a)}{\mathrm{ggT}\left({\mathrm{ord}}_n(a),k\right)}$ Ist $d$ mit $d\mid {\mathrm{ord}}_n(a)$ , so hat $a^{\frac{\mathrm{ord}n(a)}{d}}$ Ordnung $d$.

Bestimmung der Ordnung

Ein naives Verfahren bei dem $n$ klein ist oder die Ordnung selbst vermutlich klein ist: