Kleiner Satz von Fermat Hilfssatz: mn ist durch n
Transcrição
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)