Elementordnung bestimmen. Bestimmen Sie die Ordnung von 889 modulo 1009 mit schneller Exponentiation.

Question

Hallo ich habe folgende Aufgabe zu lösen:

Aufgabe: Bestimmen Sie die Ordnung von 889 modulo 1009. Verwenden Sie die schnelle Exponentation.

Leider weiss ich nicht wie das geht.

Die Ordnung der Gruppe ist 1008 aber wie finde ich jetzt heraus, welche Ordnung 889 aus der Gruppe hat ?

Muss ich jede Zahl probieren oder gibt es noch einen anderen Weg ?

Über eine Antwort wäre ich sehr dankbar

Answer 1

Du musst nicht jede zahl probieren, ein paar werden es aber schon. Für jedes Element a einer Gruppe G gilt: ord(a)| |G| (z.B. nach Lagrange) Du musst also nur Potenzen durchprobieren, die Teiler von 1008 sind.