3.5 DER KLEINE FERMATSCHE SATZ

Betrachtet man die Multiplikationstabellen der R_n aus Kapitel 3.1, so stellt man einen wesentlichen Unterschied zwischen der Tabelle zu n=5 und zu n=6 fest: Während in jeder Zeile der Tabelle für n=5 jedes Element von R₅ genau einmal vorkommt (außer natürlich in der Zeile für 0), kommen in einigen Zeilen der Tabelle zu n=6 einige Zahlen mehrfach, andere dafür gar nicht vor. Schauen wir uns ein weiteres Beispiel an und betrachten in R₇ den Faktor 4:
(*)     4× 1=4º 4;     4× 2=8º 1;     4× 3=12º 5;    
        4× 4=16º 2;   4× 5=20º 6;    4× 6=24º 3    (alle mod 7)   
- wir erhalten also wieder alle Elemente von R₇ außer der 0, die man natürlich durch 4×0º 0 erhält.

Wir untersuchen diesen Sachverhalt allgemein:
Es sei p prim und a<p mit a¹ 0. Dann sind m₁=1×a, m₂=2×a, m₃=3× a,...,m_p-1=(p-1)× a paarweise inkongruent, denn: 
m_sº m_r Þ saº ra Þ (s-r)aº 0 Þ s-rº 0 (da ja a<p und a¹ 0)
  Þ sº r Þ s=r (da ja s und r kleiner als p sind). 
Da sowohl a¹ 0 und alle Indizes inkongruent 0 sind, sind auch die m_i alle inkongruent 0. Damit repräsentieren die p-1 verschiedenen m_i die Restklassen von 1 bis p-1. Damit ergibt sich weiter:
1× 2× 3× × × (p-1)º m₁× m₂× m₃×× × m_p-1º a× (2a)× (3a)× × × (p-1)a mod p
Û (p-1)!º (p-1)!× a^p-1 mod p
Û a^p-1º 1 mod p (denn (p-1)! und p sind teilerfremd)

Diese bemerkenswerte Kongruenz geht auf den schon mehrfach erwähnten Fermat zurück und trägt deshalb seinen Namen:

SATZ 3.4         Kleiner Satz von Fermat

Ist p prim und aÎ Z teilerfremd zu p, so gilt a^p-1º 1 mod p

Was hatten wir doch Probleme mit Aufgaben wie: Welchen Rest läßt 29⁵⁵ mod 53? Das ist jetzt kein Problem mehr, denn 29⁵⁵=29⁵²⁺³=29⁵²× 29³º 1× 24389º 9 mod 53.

    Wir zeigen zwei Anwendungen:
    41ï 17¹⁰⁰⁰-1, denn 17¹⁰⁰⁰=(17⁴⁰)^25º 1^25º 1 mod 41

    4147ï 12⁵¹²-1, denn 4147=11× 13× 29 und
      1) 12º 1 mod 11 Þ 12⁵¹²-1º 1-1º 0 mod 11 Þ 11ï 12⁵¹²-1
      2) 12º -1 mod 13 Þ 12⁵¹²-1º 1-1º 0 mod 13 Þ 13ï 12⁵¹²-1
      3) 12⁵¹²-1=12^{28× 18+8º} 1^18× 12^8º 144^4º (-1)^4º 1 mod 29 Þ 29ï 12⁵¹²-1

AUFGABE 3.50  
Zeige:     a) 91ï 3⁹¹-3         b) 15ï 4¹⁵-4                 c) 7ï 2³ⁿ-1    
            d) 11ï 3⁵ⁿ-2¹⁰ⁿ      e) 7ï 2²⁺³ⁿ+3²⁺⁶ⁿ+1        f) 42ï n⁷-n   
            g) 121ï 2^20- 2¹¹+1  h) 15ï 71^6- 71^4- 71²+1    
            i) 323ï 8^34- 8^18- 8¹⁶+1        j) 1992ï 2^87- 2^85- 2⁵+2³

AUFGABE 3.51 
a) Zeige, dass für jede Primzahl p>2 und alle aÎZ gilt:  2pï a^p-a.
Begründe damit, dass a⁵ und a für alle aÎZ dieselbe Endziffer hat.
b) Zeige: Ist p eine Primzahl größer als 40, so ist z=p⁴⁰+368 stets durch 41 teilbar.

Download Kap_3_5 (26 KB)

Copyright © Michael Dorner, Januar 2002.