1 Der kleine Satz von Fermat

1
1.1
Der kleine Satz von Fermat
Behauptung
Der kleine Satz von Fermat behauptet, dass für ∀b ∈ N und p ∈ N(p ist dabei
eine Primzahl) gelte
bp ≡p b
Beispielhaft bedeutet dies, dass z.B. für b = 2, p = 3
23 ≡3 2
hier also
8
mod 3 = 2 mod 3
gilt, was offensichtlich ist.
1.2
Beweis
Sei Z∗p = {n ∈ {1, ..., p − 1}|ggT (n, p) = 1}, wobei Zp hier die möglichen
Restklassen darstellt. Z∗p sei nun eine Algebra, die über der modularen Multiplikation ∗p erfüllt sei, eine Gruppe bilde und deren Elemente teilerfremd
zu p seien. Aus diesem Grund ist auch die 0 nicht enthalten. Man betrachtet
nun eine Fallunterscheidung, um den Satz von Fermat zu beweisen:
1.2.1
Fall 1: b = 0
In diesem Falle wäre
0p ≡p 0
es ist klar, dass für diesen Fall der Satz erfüllt ist.
1.2.2
Fall 2: 1 ≤ b < p
Man betrachte die Untergruppe
Sb = h{b0 , b1 , ..., bord(b)−1 }, ∗i
Da Z∗p eine Gruppe bildet und abgeschlossen ist, ist Sb eine Untergruppe von
Z∗p . Nach dem Satz von Lagrange gilt, dass die Anzahl der Untergruppen eine
ganze Zahl sein muss, oder äquivalent zu dieser Aussage
|Sb | | |Z∗p |
1
|Sb | teilt |Z∗p | ganzzahlig. Dies bedeutet, es existiert ein q ∈ N, für das gilt
|Z∗p | = q ∗ |Sb |
Nach den obigen Definitionen ist die Kardinalität von Z∗p = p - 1, da p eine
Primzahl ist und somit p nur von p oder 1 geteilt wird. Nach der Definition
von Sb gilt, dass die Kardinalität von |Sb | = ord(b)−1 ist. Unter Einbeziehung
des Satzes von Lagrange gilt also folgendes:
(∃q ∈ N[q ∗ ord(b) = p − 1]
Laut der Definition der Ordnung eines Elementes ist
bord(b) = 1
(wobei 1 hier das Einselement darstellt). Aus der Gruppeneigenschaft der
Existenz eines inversen Elements zu jedem Element folgt
bp = bp−1 ∗ b
Wie vorher gezeigt existiert jedoch ein q, dass
bp−1 = bq∗ord(b)
erfüllt. Somit lässt sich bp = 1p ∗ b vereinfachen. Es gilt ferner
1q ∗ b ≡p b
da b kleiner als p ist. Somit ist der Satz für diesen Fall bewiesen.
1.2.3
Fall 3: b ≥ p
Für b ≥ p gilt b = q ∗ p + r, wobei r ∈ N0 den Rest b mod p und q ∈ N0 die
ganzzahlige Division b ÷ p darstellt.
(∃q, r ∈ N0 , 0 ≤ r < p)[b = q ∗ p + r]
Es lässt sich also wie folgt umformen:
bp = (q ∗ p + r)p
Nach der allgemeinen binomischen Formel
n X
n n−k k
n
a
∗b
(a + b) =
k
k=0
2
für n ∈ N ist
(q ∗ p + r)p = (q ∗ p)p + ... + r p
Für die ersten p Summanden gilt, dass sie kongruent modulo p immer ∈ [0]
(also in der Restklasse [0] enthalten)sind, da (q ∗ p)y ∗ r x mod p = 0 bzw.
(q ∗ p)y ∗ r x ≡p 0
ist(x ≤ n, y < n). Für den letzten Summanden r p gilt r p ≡p r. Dies erinnert
an den 2. Fall wo bp ≡p b. Da die anderen Summanden alle ∈ [0] sind, muss
r ≡p b sein bzw. r ∈ [b].
1.3
Die umgekehrte Richtung
Selbstverständlich lässt sich der Satz von Fermat uminterpretieren. Der Einfachheit halber teilt man die bekannte Gleichung durch b und erhält
bp−1 ≡p 1
Die Behauptung ist nun, dass wenn ∀b ∈ Zp obige Gleichung erfüllt ist, p
eine Primzahl ist. Damit ergibt sich eine elegante Möglichkeit, um schnell
einen Primzahltest durchzuführen.
1.4
Beweis der umgekehrten Richtung
Man nehme an, es existiere eine Zahl r ∈ N mit r > 1 und r|p. Nach dem
Satz von Fermat ergibt sich
r p−1 ≡p 1 ⇐⇒ r p−1 − 1 ≡p 0
da es nach den Gesetzen der modularen Arithmetik unbedeutend ist, ob
zuerst der Rest genommen oder die Addition ausgeführt wird. Da r p teilt, gilt
für den Modulus r mod p ⇔ r. Die Behauptung lässt sich also umschreiben
zu
r p−1 − 1 ≡p 0 ⇐⇒ (r mod p)p−1 − 1 = 0
womit die Kongruenz in eine Äquivalenz überführt wurde. Nach der Definition der Kongruenz gilt für einen Term kongruent modulo 0, dass ein q
existiert, das folgende Gleichung erfüllt:
r p−1 − 1 = q ∗ p, q ∈ Z
Laut der Definition teilt r jedoch p, sodass zusätzlich ein q 0 existieren muss
mit der Eigenschaft q 0 ∗ r = n. Durch Einsetzen erhält man
r p−1 − 1 = q ∗ q 0 ∗ r
3
umformen ergibt
r p−1 − q ∗ q 0 ∗ r = 1 ⇐⇒ r ∗ (r p−2 − q ∗ q 0 ) = 1
Dies bedeutet, dass r 1 teilt, was ein Widerspruch zur Annahme, dass r > 1
ist, darstellt. In diesem Sinne ist die Gleichung nur dann erfüllt wenn p die
trivialen Teiler 1,p besitzt.
1.5
Verallgemeinerung - Satz von Euler/Fermat
Wie vieles im Leben, lässt sich auch der Satz von Fermat verallgemeinern. Die
Funktion ϕ(n) sei dabei die eulersche Phi-Funktion, die sich z.B. so definieren
lässt:
ϕ(n) = |Z∗n |
wobei
Z∗n = {a ≡n b|a, b ∈ Z, n ∈ N|ggT (a, n) = ggT (b, n) = 1}
Anschaulich stellt Z∗n also die Menge aller zu n teilerfremden Restklassen
über n dar und ϕ(n) deren Anzahl. Nach dem Satz von Euler/Fermat gilt
∀b ∈ Z∗n
bϕ(n) ≡n 1
1.6
Beweis Verallgemeinerung - Satz von Euler/Fermat
Sei b ∈ Z∗n dann gilt für ein beliebiges a ∈ Z∗n , dass ggT (a, n) = ggT (b, n) = 1.
Somit muss auch für den gemeinsamen größten Teiler des Produktes a ∗ b
gelten ggT (ab, n) = 1. Im Endeffekt bedeutet dies, dass wenn
S = hZ∗n , ∗n , 1i
eine Algebra darstellt, selbige abgeschlossen und eine Gruppe ist. Wenn
{[x0 ], [x1 ], ..., [xϕ(n)−1 ]} die einzelnen Restklassen aus Z∗n darstellen, gilt also folglich(aufgrund der Abgeschlossenheit von S):
[x0 ] ∗n [x1 ] ∗n ... ∗n ∗[xϕ(n)−1 ] = [b] ∗n [x0 ] ∗n [b] ∗n [x1 ] ∗n ... ∗n [b] ∗n [xϕ(n)−1 ]
Da S eine Gruppe ist, lässt sich die Kürzungsregel anwenden und der Term
vereinfacht sich zu
[b]ϕ(n) = [1] ⇐⇒ bϕ(n) ≡n 1
Der Satz von Fermat ist als Folgerung nur ein Spezialfall des Satzes von
Euler, nämlich genau dann, wenn n eine Primzahl p ist, da ϕ(p) = p − 1(Eine
Primzahl besitzt logischerweise aufgrund ihrer Definition p − 1 teilerfremde
Restklassen).
4