Ordnung

Die Ordnung von aa modulo nn ist das minimale kk, welches den Satz von Euler erfüllt.
Wir haben also

ord⁡n(a)=min⁡{k∈N:ak≡1 mod n}.\operatorname{ord}_n(a)=\min \left\{k \in \mathbb{N}: a^k \equiv 1 \bmod n\right\}.

Eigenschaften

ak≡1 mod n⟺ord⁡n(a)∣ka^k \equiv 1 \bmod n \Longleftrightarrow \operatorname{ord}_n(a) \mid k {k∈N:ak≡1 mod n}=N⋅ord⁡n(a)={ℓ⋅ord⁡n(a):ℓ∈N}\left\{k \in \mathbb{N}: a^k \equiv 1 \bmod n\right\}=\mathbb{N} \cdot \operatorname{ord}_n(a)=\left\{\ell \cdot \operatorname{ord}_n(a): \ell \in \mathbb{N}\right\}

Also alle Vielfachen der Ordnung von aa modulo nn erfüllen auch den Satz von Euler.

ord⁡n(a)∣φ(n)\operatorname{ord}_n(a) \mid \varphi(n) ak1≡ak2 mod n⟺k1≡k2 mod ord⁡n(a)a^{k_1} \equiv a^{k_2} \bmod n \Longleftrightarrow k_1 \equiv k_2 \bmod {\operatorname{ord}_n(a)}

Wir können so also leicht im Exponenten rechnen.

ord⁡n(ak)=ord⁡n(a)ggT⁡(ord⁡n(a),k)\operatorname{ord}_n\left(a^k\right)=\frac{\operatorname{ord}_n(a)}{\operatorname{ggT}\left(\operatorname{ord}_n(a), k\right)}

Ist dd mit d∣ord⁡n(a)d\mid \operatorname{ord}_n(a) , so hat

aord⁡n(a)da^{\frac{\operatorname{ord} n(a)}{d}}

Ordnung dd.

Bestimmung der Ordnung

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