Matheseitenüberblick   •  zurück   •  © Arndt Brünner

Der kleine Satz von Fermat

Pierre de Fermat

Pierre de Fermat Satz ist einer der wichtigsten der Zahlentheorie. Ich will versuchen, ihn im folgenden zu beweisen, ohne irgendwelche Kenntnisse der Zahlentheorie vorauszusetzen. Man sollte allerdings die Division mit Rest kennen und etwas von Gleichungen und Gleichungssystemen (Additionsverfahren) verstehen.
→Hier (pdf ) ein „professioneller“ Beweis (Vollständige Induktion).

Anders ausgedrückt: n^p-1 ergibt bei der Division durch die Primzahl p immer den Rest 1, wenn n kein Vielfaches von p ist.

   Ausprobieren:

→ Eine Möglichkeit, Divisionsreste von n^p-1 auch bei sehr großen Zahlen ohne Überlauf und schnell zu berechnen, wird hier beschrieben.
    Dort ist außerdem eine Anwendung des Fermatschen Satzes zur Berechnung der Periodenlänge von Dezimalbrüchen zu finden.

Beweis

Zuerst betrachten wir die ersten p-1 Vielfachen der Zahl n etwas genauer. Besser gesagt, wir betrachten ihre Reste bei der Division durch p.

a·n und b·n sind zwei unterschiedliche Vielfache von n, wobei a und b größer als 0, aber kleiner als p sein sollen. Außerdem sei a<b.

a·n ergebe bei der Division durch p den Quotienten q_a und den Rest r_a, analog ergebe b·n den Quotienten q_b und den Rest r_b. Wegen a<b ist q_a≤q_b.

Dann kann man schreiben:

        a·n = qa·p + ra 
  und   b·n = qb·p + rb

Nun kann man anhand dieser beiden Gleichungen leicht zeigen, daß r_a ≠ r_b sein muß.

Wir nehmen dazu an, daß die beiden Reste doch gleich seien und erhalten recht bald einen Widerspruch, wodurch bewiesen ist, daß sie nicht gleich sein können.
Dazu subtrahieren wir die erste Gleichung von der zweiten:

    (1)        a·n  =  qa·p   +   ra 
    (2)        b·n  =  qb·p   +   rb

  (2)-(1)   (b-a)n  = (qb-qa)p  

Der Ausdruck auf der rechten Seite (q_b-q_a)p ist offensichtlich ein positives Vielfaches von p oder Null, denn die Differenz in der Klammer ist wegen q_a≤q_b größer gleich Null.

Da wegen a<b sowohl (b-a)>0 ist, als auch n>0 gilt, ist das nicht möglich, denn die linke Seite kann nicht Null sein.

Falls rechts ein positives Vielfaches von p stehen sollte, müßte auch der Ausdruck links ein Vielfaches von p sein. Damit wäre p entweder ein Teiler von (b-a) oder von n. Auch dies ist unmöglich, denn a und b sind beide nach der Voraussetzung kleiner als p, aber größer als Null, womit b-a sicher kein Vielfaches von p sein kann. Und auch n ist nach der Voraussetzung kein Vielfaches von p.

Die Annahme, daß für irgendwelche a und b die Reste gleich seien, führte also auf eine falsche Aussage. Aus diesem Widerspruchsbeweis folgt, daß alle Reste der ersten p-1 Vielfachen von n verschieden sein müssen.

Als Reste bei der Division durch p können nur Zahlen vorkommen, die kleiner als p sind. Bei der Division von a·n durch p kann auch der Rest 0 nicht auftreten, wenn a kleiner als p ist und außerdem n kein Vielfaches von p.

Aus beiden Feststellungen folgt: Die ersten p-1 Vielfachen von n besitzen bei der Division durch p die Reste 1, 2, 3, 4, ... p-1 in irgendeiner Reihenfolge.

Nun bilden wir das Produkt dieser ersten p-1 Vielfachen von n und fassen die Zahlen und die n's zusammen:

   (3)    n · 2n · 3n · 4n · ... · (p-1)n  =  1·2·3·4·...·(p-1) · np-1

Eben hatten wir festgestellt, daß diese Vielfachen von n die Reste 1 bis p-1 erzeugen. Ähnlich wie oben schreiben wir nun für die Vielfachen von n:

          n  =  q1·p  + r1
         2n  =  q2·p  + r2
         3n  =  q3·p  + r3
         4n  =  q4·p  + r4
         ...        ...
     (p-1)n  =  qp-1·p + rp-1

Und bilden wie bei (3) das Produkt der Vielfachen, allerdings multiplizieren wir diesmal die rechten Seiten, die ja ebenfalls diese Vielfachen darstellen:

    (q1·p + r1)·(q2·p + r2)·(q3·p + r3)· ... ·(qp-1·p + rp-1)

Welchen Rest läßt dieses Produkt bei der Division durch p? In jeder Klammer finden wir ein Vielfaches von p, das auf diesen Rest einflußlos ist. (Beweis dieser Aussage im Anhang).
Übrig bleiben die r₁ bis r_p-1, von denen wir wissen, daß sie die Zahlen 1 bis p-1 darstellen. Der gesuchte Rest ist also der Rest des Produktes 1·2·3·4·...·(p-1).

Dies bedeutet: Das Produkt der ersten p-1 Vielfachen von n hat denselben Rest wie das Produkt der ersten p-1 natürlichen Zahlen.

Mit dieser Erkenntnis gehen wir zurück zur Darstellung des Produktes aus (3) und denken auch hier über den Rest bei der Division durch p nach.

 
   (3)    n · 2n · 3n · 4n · ... · (p-1)n  =  1·2·3·4·...·(p-1) · np-1

Links steht das Produkt aus den ersten p-1 Vielfachen, rechts ein Produkt aus einerseits dem Produkt aus den ersten p-1 natürlichen Zahlen und der Potenz n^p-1. Wir wissen, daß die linke Seite denselben Rest hat wie der erste Faktor rechts, also die farbig gedruckten Teile besitzen denselben Rest.

Was bedeutet das für n^p-1?

Überlegen wir das anhand einer übersichtlicheren Situation: (4) a = b·c.
Auch hier sollen a und b denselben Rest r bei der Division durch p haben. Außerdem seien a,b,c > 0 und r, r_c < p. Schreiben wir wieder Gleichungen für die Divisionen mit Rest durch p:

   (5)      a = qa·p + r 
   (6)      b = qb·p + r 
   (7)      c = qc·p + rc 

Wir subtrahieren (5)-(6), lösen nach a auf und ersetzen a in (4) durch diesen Ausdruck:

 (5)-(6)  a-b = (qa-qb)p       | + b
            a = (qa-qb)p + b
  in (4)   (qa-qb)p + b = b·c

In dieser Gleichung ersetzen wir c durch die rechte Seite von (7).

           (qa-qb)p + b = b·(qc·p + rc)    | : b       (b>0)


           (qa-qb)p
           ——————— + 1  =  qc·p + rc      |  - qc·p
              b

           (qa-qb)p
           ——————— - qc·p + 1  =  rc  
              b

           (qa - qb - qcb)p  
    (8)    ———————————————  +  1  =  rc  
                  b

Weil in (8) r_c und 1 ganzzahlig sind, muß auch der Bruch ganzzahlig sein. Außerdem kann b kein Teiler der Primzahl p sein. Damit ist der Bruch nicht nur ganzzahlig, sondern ein Vielfaches von p. Der Rest r_c ist also 1 plus irgendein Vielfaches von p.

Daraus folgt, daß c bei der Division durch p den Rest 1 läßt, denn Vielfache von p haben auf den Rest keinen Einfluß.

Gleich ist es geschafft. Denn wenn wir erneut zur Gleichung (3) zurückkehren, sind wir ein gutes Stück klüger als vorhin, denn wir wissen nun, welchen Rest n^p-1 haben muß, wenn die Reste der blauen und der grünen Zahl einander gleich sind, und das sind sie!

   (3)    n · 2n · 3n · 4n · ... · (p-1)n  =  1·2·3·4·...·(p-1) · np-1

Wir wissen nun: n^p-1 hat bei der Division durch p den Rest 1. Und das genau ist der Satz von Fermat.

© Arndt Brünner, 15. 2. 2003
Matheseitenüberblick
zurück
Die Primzahlseite
Periodenlänge von Dezimalbrüchen
Gästebuch
Version: 28. 4. 2012

Anhang

Auf den Rest bei der Division eines Produktes aus natürlichen Zahlen haben nur die Reste der einzelnen Faktoren Einfluß.

Zum Beweis werden wir die beiden beliebigen natürlichen Zahlen a und b multiplizieren. Dazu definieren wir zunächst Quotienten und Reste von a und b bei der Division durch die beliebiege natürliche Zahl m:

  (I)     a : m = qa Rest ra
  (II)    b : m = qb Rest rb

Das kann man so schreiben:

  (I)'    a = qa·m + ra
  (II)'   b = qb·m + rb

Nun multiplizieren wir a mit b und ersetzen dann a durch die rechte Seite aus (I)' und b durch die rechte Seite aus (II)':

         a  ·  b
       = (qa·m + ra) · (qb·m + rb)
       =  qa·qb·m² + qa·m·rb + qb·m·ra + ra·rb

Das sieht zwar recht kompliziert aus, ist aber halb so schlimm. Denn es interessiert uns ja, was "passiert", wenn man dieses Produkt durch m teil. Genauer gesagt, wollen wir sogar nur wissen, welcher Divisionsrest bleibt:

          qa·qb·m² + qa·m·rb + qb·m·ra + ra·rb
          —————————————————————————————————
                         m

                                    ra·rb
       =  qa·qb·m + qa·rb + qb·ra  +  —————— 
                                      m

Fast alles geht ganzzahlig auf, nur r_a·r_b läßt sich nicht durch m teilen. Damit ist r_a·r_b der Rest.

Also ist der Rest des Produktes a·b bei der Division durch m gleich dem Rest des Produktes der Reste.

Auch für die Addition gilt ein ähnlicher Satz:

Auf den Rest bei der Division einer Summe aus natürlichen Zahlen haben nur die Reste der einzelnen Summanden Einfluß.

Addiert man (I)' mit (II)' und dividiert wieder durch m, so ergibt sich auch hier, daß nur die Summe der Reste r_a+r_b für den Rest der Summe verantwortlich ist:

       qa·m + ra  +  qb·m + rb  =  qa·m + qb·m  +  ra + rb


       qa·m + qb·m  +  ra + rb                    ra+rb
       ——————————————————————   =   qa + qb  +   —————
                   m                              m

In der Mathematik wird eine elegantere Schreibweise für dieses Rechnen mit Resten verwendet, die ich auf dieser Seite völlig vermieden habe. In der Zahlentheorie spielen diese Rechenarten, Betrachtungsweisen und damit auch die "fachmännischen" Schreibweisen eine sehr große Rolle.

Stets unendlich viele Zahlen besitzen denselben Rest bei einer Division durch eine bestimmte natürliche Zahl. Z.B. besitzen alle Zahlen aus der Menge {1, 8, 15, 22, 29, 36, 43, 50, ...} den Rest 1 bei der Division durch 7. Man sagt, daß diese Zahlen kongruent bezüglich der 7 sind. Sie gehören einer gemeinsamen Restklasse an. Zu der Zahl 7 sagt man in diesem Fall auch Modul.

Daß 15 und 43 denselben Rest bei der Division durch 7 haben, kann man dann so ausdrücken: 15 ≡ 43 modulo 7 oder noch kürzer 15 ≡ 43 mod 7.

Das Zeichen ≡ steht für "kongruent". Die Verwandtschaft dieses Zeichens mit dem Gleichheitszeichen ist kein Zufall, denn schließlich verhalten sich diese kongruenten Zahlen gleich, wenn man modulo einer Zahl rechnet und nur "erlaubte" Rechenarten, wie + und · verwendet. So sind beispielsweise die folgenden Aussagen richtig: 5·5 ≡ 4·4 mod 3 (sowohl 5·5=25 als auch 4·4=16 ergeben bei der Division durch 3 den Rest 1); 1·2 + 3·4 + 5·6 ≡ 1 + 2·3 + 4·5 + 6 mod 11; 10 - 3 ≡ 10 + 3 mod 4.

Der Satz von Fermat heißt übrigens in dieser Schreibweise:

                             np-1 ≡ 1 mod p

Übigens bist Du schon geübt im Rechnen mit Restklassen; wahrscheinlich beherrscht Du es sogar, ohne es zu wissen, wie im Schlaf!

Hier drei kleine Beispiele:

• Wenn Du um 21 Uhr einschläfst und 8 Stunden schläfst, dann wachst Du nicht etwa um 29 Uhr auf, sondern um 5 Uhr. Wir rechnen nämlich die Stunden modulo 24, und tatsächlich gilt: 29 ≡ 5 mod 24.
• Um 17 Uhr und um 5 Uhr zeigt der Stundenzeiger einer Uhr in dieselbe Richtung, denn das Zifferblatt geht nur bis 12, die Stunden werden also von der Uhr selbst modulo 12 "gerechnet": 17 ≡ 5 mod 12.
• Nach je 4 Schulstunden à 45min, also nach 180min, beginnen Schulstunden und Zeitstunden wieder zur gleichen Minute, denn 4·45 = 180 ≡ 0 mod 60.