Du musst da mehr Systematik reinlegen. In der Algebra lernt man, dass die 23 Elemente von F23 die Wurzeln sind des Polynoms
f ( x ) = x ^ 23 - x = 0 ( 1 )
( Schau noch mal im v.d. Waerden oder noch besser in dem Skript von Otto Haupt; es ist eine direkte Folge des binomischen Lehrsdatzes. ) D. h. aber die multiplikative Gruppe G23 , das sind alle außer der Null, bestehen aus sämtlichen 22 . Einheitswurzeln:
g ( x ) = x ^ 22 - 1 = 0 ( 2 )
Sämtliche Einheitswurzeln bilden grundsätzlich eine zyklische Gruppe. Was ist die Strategie? Gehen wir aus von einem Element, das Teiler fremd ist zu 22 , im einfachsten Fall 3 . Bilden wir alle 22 Potenzen:
3 ^ 1 = 3 , 3 ² = 9 , 3 ³ = 4 , 3 ^ 4 = ( - 11 ) ( 3a )
3 ^ 5 = ( - 10 ) ; 3 ^ 6 = ( - 7 ) , 3 ^ 7 = 2 ( 3b )
3 ^ 8 = 6 , 3 ^ 9 = ( - 5 ) , 3 ^ 10 = 8 , 3 ^ 11 = 1 ( 3c )
Ist das Prinzip so weit verstanden?
Hey merkste was? Meine Strategie geht auf. Ursprünglich hatten wir ja einen Zyklus der Periode 22 erwartet. Ich hatte dir aber auch empfohlen, als Reste nur zuzulassen
+/- ( 1 , .... , 11 ) ( 4a )
und nicht wie üblich
1 , 2 , 3 , ... , 22 ( 4b )
Mit Vorzeichen rechnen können wir nämlich; und der Vollzyklus zerfällt auf einmal in zwei Halbzyklen.
Ich sortiere ( 3a-c ) noch einmal wegen der besseren Übersicht:
1 = 3 ^ 11 , 2 = 3 ^ 7 , 3 = 3 ^ 1 , 4 = 3 ³ , 5 = - 3 ^ 9 ( 5a )
6 = 3 ^ 8 , 7 = - 3 ^ 6 , 8 = 3 ^ 10 , 9 = 3 ² ( 5b )
10 = - 3 ^ 5 , 11 = - 3 ^ 4 ( 5c )
So jetzt sieht das schon mal nach was aus. Beginnen wir mit 1/5 . Die 5 finden wir in ( 5a ) , das ist 5 = - 3 ^ 9 . wo wollen wir hin? 1 = 3 ^ 11 , also müssen wir multiplizieren mit ( - 3 ² ) = ( - 9 ) Machen wir die Probe;
5 * ( - 9 ) = ( - 45 ) = 1 mod 23 .
Jetzt 1/6 . In ( 5b ) kriegst du gesagt 6 = 3 ^ 8 . Wir müssen also suchen nach 3 ³ in ( 3a ) , und das ist 4 . Also 1/6 = 4 . Probe geht glaub ich im Kopf.
7 findest du in ( 5b ) , das ist ( - 3 ^ 6 ) Wir suchen also ( - 3 ^ 5 ) ; und das gibt 10 in ( 3b ) . 1/7 = 10 . Probe:
10 * 7 = 70 = 1 mod 23
