Kleiner Satz von Fermat Hilfssatz: mn ist durch n

Kleiner Satz von Fermat
© Arndt Brünner, 2012
n  ist durch n teilbar, sofern n eine Primzahl und 0 < m < n ist.
Hilfssatz:  m

 
n( n − 1)( n − 2 ) ... ( n − m + 1)
n!
n =
=
ist in jedem Fall ganzzahlig.
Beweis:  m

1⋅ 2 ⋅ 3 ⋅... ⋅ m
  ( n − m )! m !
Falls n prim und m<n, findet sich im Nenner kein Faktor zum Kürzen von n im Zähler.
Also muß nach vollständigem Kürzen aller Faktoren des Nenners n noch Teiler sein.
Satz (Fermat): kp ≡ k mod p
Beweis (Vollständige Induktion über k):
Induktions-Anfang: k=0: 0p=0 ≡ 0 mod p
Induktions-Schritt: kp ≡ k mod p ⇒ (k+1)p ≡ k+1 mod p:
p
p
p
p  1  p 0
( k + 1)p =   k p +   k p−1 +   k p−2 + ... + 
 k +  p k
0
1
2
p
 
 
 
 − 1
 
p
= 1⋅ k p + p ⋅k p−1 +   k p−2 + ... + p ⋅ k + 1⋅ k 0
2
p
=
k p + p ⋅ k p−1 +   k p−2 + ... + p ⋅ k + 1
{
 24
 244444
≡k
1444
4
3
nach
Induktions −
voraussetzung
≡ k
+ 0
≡ k + 1 mod p
⇒
alle Summanden sind teilbar durch p
wegen der Binomialkoeffiziente n
(s.o.: Hilfssatz)
+ 0
+ ... + 0
+ 1
mod p
kp ≡ k mod p ∀ k ≥ 0 und p prim
bzw.
kp–1≡ 1 mod p
Bsp.:
(falls k≡0 mod p. Das folgt nach Division durch k aus der ersten Version)
07 =
0=
0 ·7 + 0
7
1 =
1=
0 ·7 + 1
27 =
128 =
18 ·7 + 2
37 = 2187 = 312 ·7 + 3
47 = 16384 = 2340 ·7 + 4
57 = 78125 = 11160 ·7 + 5
67 = 279936 = 39990 ·7 + 6
⇒
⇒
⇒
⇒
⇒
⇒
⇒
07 ≡ 0 mod 7
17 ≡ 1 mod 7
27 ≡ 2 mod 7
37 ≡ 3 mod 7
47 ≡ 4 mod 7
57 ≡ 5 mod 7
67 ≡ 6 mod 7
(Binomischer
Lehrsatz)