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 ordm(a)\operatorname{ord}_m(a) der kleinste positive Exponent tt mit at1(modm)a^t\equiv1\pmod m.

Satz

Tatsächliche Potenzperiode

Ist t=ordm(a)t=\operatorname{ord}_m(a), dann gilt an+tan(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 3133^1\equiv3, 3293^2\equiv9 und 3313^3\equiv1. Also ist ord13(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.