Zum Inhalt springen
Inhaltsverzeichnis öffnen
Kapitel 8Fortgeschritten26 Min.

Ordnung als kleinste Periode

Multiplikative Ordnung · Abschnitt 29 von 64

Definition

Multiplikative Ordnung

Für ggT⁡(a,m)=1\operatorname{ggT}(a,m)=1 ist ord⁡m(a)\operatorname{ord}_m(a) der kleinste positive Exponent tt mit at≡1(modm)a^t\equiv1\pmod m.

Satz

Tatsächliche Potenzperiode

Ist t=ord⁡m(a)t=\operatorname{ord}_m(a), dann gilt an+t≡an(modm)a^{n+t}\equiv a^n\pmod m für alle nn. Kein kleinerer positiver Abstand besitzt diese Eigenschaft.

Gelöstes Beispiel

Ordnung drei statt zwölf

Modulo 13 gilt 31≡33^1\equiv3, 32≡93^2\equiv9 und 33≡13^3\equiv1. Also ist ord⁡13(3)=3\operatorname{ord}_{13}(3)=3, obwohl Fermat nur die größere Periodenlänge 12 garantiert.

Achtung

Nur für invertierbare Klassen

Die multiplikative Ordnung wird hier nur für ggT⁡(a,m)=1\operatorname{ggT}(a,m)=1 definiert. Nicht teilerfremde Basen können Vorperioden besitzen und erreichen möglicherweise nie den Rest 1.