Zahlentheorie (Vorlesungsnotizen)
Vorlesungsnotizen zum Abschnitt Zahlentheorie und modulare Arithmetik
modarithmetik.txt
—
Plain Text,
14 KB (15186 bytes)
Dateiinhalt
============================== Zahlentheorie und Arithmetik ============================== Teilbarkeit und ganzzahlige Division ==================================== Satz: Für a,b∈ℤ gibt es eindeutig bestimmte Zahlen q,r∈ℤ mit 0≤r<|b| a=q∙b+r Notation: Falls a=q∙b+r mit 0≤r<|b|, so schreiben wir q = ⌊a/b⌋ r = a mod b ("modulo") wobei ⌊x⌋∈ℤ die größte ganze Zahl ≤ x∈R bezeichnet (also abrunden) Beispiel: 23 mod 7 = 2 ⌊23/7⌋= 3 und es gilt 23 = 3∙7+2 -10 mod 3 = 2 ⌊-10/3⌋=-4 und es gilt -10 = -4∙3+2 Bemerkung: Implementierung mancher Programmiersprachen können hier von den mathematischen Notationen abweichen! Definition Teilbarkeit: b|a ⇔ a mod b = 0 d.h. es gibt ein q∈ℤ mit q∙b = a NB: es gilt 1|a und a|a für alle a∈ℤ. Definition: a und b sind _teilerfremd_, wenn c|a und c|b nur für c=1 gilt. Definition _Primzahl_: Eine Zahl p∈ℕ ist prim, falls d|p nur für d=1 und d=p gilt. Beispiel: Sieb des Eratosthenes: Man schreibt alle Zahlen hin 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 ... Man geht alle Zahlen durch und streicht jeweils alle Vielfachen aus. Für 2: 2 3 / 5 / 7 / 9 / 11 / 13 / 15 / 17 / 19 / 21 / 23 / 25 / 27 / 29 / 31 / 33 / 35 / ... Für 3: 2 3 / 5 / 7 / / / 11 / 13 / / / 17 / 19 / / / 23 / 25 / / / 29 / 31 / / / 35 / ... usw. Ineffizient in der Praxis. Satz: Fundamentalsatz der Arithmetik Jede Zahl n∈ℕ, n≥2, kann als Produkt von Primzahlpotenzen geschrieben werden. k n = Π pi^ei i=1 für k∈ℕ; p₁,..,pₖ paarweise verschiedene Primzahlen; e₁,..,eₖ ∈ ℕ Diese pi,ei sind bis auf Reihenfolge eindeutig bestimmt. Beispiel: 420=2²∙3¹∙5¹∙7¹ 1260=2²∙3²∙5¹∙7¹ Satz von Euklid: Es gibt unendlich viele Primzahlen. Beweis: Für führen den Beweis durch Widerspruch. Annahme: es gibt nur endlich viele Primzahlen: p₁,..,pₙ Wir definieren n m ≝ 1 + Π pi = 1 + p₁∙p₂∙...∙pₙ i=1 Für alle i mit 1≤i≤n gilt nach dieser Definition also m mod pi = 1 also ist pi⍭m (pi kein Teiler von m). Damit ist keines der pi ein Primfaktor von m, d.h. entweder ist m eine weitere Primzahl ↯ oder pi enthalten nicht alle Primzahlen, weil Primfaktoren von m fehlen. Hinweis: Beweisidee enthält Konstruktion von Zahlen, welche gegebene Primfaktoren gerade _nicht_ enthält. Definition: Primzahlfunktion. Funktion π(x) bezeichne die Anzahl von Primzahlen ≤ x, d.h. π(x) = |{p | p≤x und p ist Primzahl}| Beispiel: π(6)=3, π(7)=4, π(15)=6 Bemerkung: π() ist "Stufenfunktion" Primzahlsatz: Es gilt: π(n) ~ n/ln(n) d.h. lim π(n)/(n/ln(n)) = 1 n→∞ (Beweis ist aufwändig) Beispiel: π(10000)=1229 10000/ln(10000)=1085,73 Ratio: 1,1320 π(10^20)/(10^20/ln(10^2)) = 1,0227 Modulare Arithmetik =================== Definition: Für m∈ℕ; a,b∈ℤ definieren wir a≡b (mod m), lies "a ist kongruent zu b modulo m", falls m|(a-b). Es gilt außerdem, dass folgende Aussagen äquivalent sind: 1) a≡b (mod m) 2) a mod m = b mod m 3) ∃t∈ℤ.a=b+t∙m Beispiel: a=23 b=-12 Es ist a≡b (mod 7), denn 23 mod 7 = 2 = -12 mod 7 oder auch 7|(23-(-12) also 7|35 oder 23 = -12 + 5∙7 (also t =5) Lemma: Für alle a,b∈ℤ und m∈ℕ gilt 1) (a+b) mod m = (a mod m + b mod m) mod m 2) (a∙b) mod m = (a mod m ∙ b mod m) mod m Beispiel: 35 mod 3 = (5 mod 3 ∙ 7 mod 3) mod 3 = 2 ∙ 1 mod 3 = 2 Beweis: (a+b) mod m (ersetze a und b durch "q∙m+r") = (⌊a/m⌋∙m + a mod m + ⌊b/m⌋∙m + b mod m) mod m = ( qₐ ∙m + rₐ + q₂ ∙m + r₂ ) mod m Wir verwenden (q∙m+r) mod m = r mod m und erhalten = rₐ + r₂ ) mod m = ( a mod m + b mod m) mod m (a∙b) mod m (ersetze a und b durch "q∙m+r") = ((⌊a/m⌋∙m + a mod m) ∙ (⌊b/m⌋∙m + b mod m)) mod m = (⌊a/m⌋∙⌊b/m⌋∙m² + (b mod m)∙⌊a/m⌋∙m + (a mod m)∙⌊b/m⌋∙m + (a mod m)∙(b mod m)) mod m = (a mod m ∙ b mod m) mod m □ Anwendungs-Beispiel aus Kryptographie: "Schnelles Potenzieren" Berechne 7^66 mod 13 7 mod 13 = 7 7² mod 13 = 10 7⁴ mod 13 = 10∙10 mod 13 = 9 (100=7*13+9) 7⁸ mod 13 = 9∙9 mod 13 = 3 (81 =6*13+3 7^16 mod 13 = 3∙3 mod 13 = 9 7^32 mod 13 = 9∙9 mod 13 = 3 7^64 mod 13 = 3∙3 mod 13 = 9 damit 7^66 mod 13 = 7^64 ∙ 7^2 mod 13 = 9∙10 mod 13 = 90 mod 13 = 12 ========================================================= ENDE VORLESUNG 10.5.16, BEWEIS LEMMA NOCH NICHT GEMACHT ========================================================= Beispiel Quersumme: Eine Zahl n ist durch 3 teilbar (d.h. n mod 3 = 0), wenn ihre Quersumme durch 3 teilbar ist. k Sei n= Σ ai∙10^i i=0 Damit gilt k n mod 3 = (Σ (ai mod 3)∙(10 mod 3)^i ) mod 3 i=0 k =(Σ ai mod 3) mod 3 (Quersumme) i=0 Korollar: Aus a≡b (mod m) und c≡d (mod m) folgt a+c ≡ b+d (mod m) und a∙c ≡ b∙d (mod m) Lemma: Wenn z|x und z|y dann z|x+y Beweis: z|x bedeutet x mod z = 0. Also gilt x mod z = 0 und y mod z = 0. Es gilt (x+y) mod z = ((x mod z) + (y mod z)) mod z = (0 + 0) mod z = 0 Lemma: Wenn z|x+y und z|x dann z|y Beweis: 0 = (x+y) mod z = ((x mod z) + (y mod z)) mod z = (0 + (y mod z)) mod z = y mod z Größter gemeinsamer Teiler und Euklidische Algorithmus ====================================================== Definition: Der größter gemeinsame Teiler von a,b∈ℤ, geschrieben ggT(a,b), ist die größte Zahl d∈ℕ mit d|a und d|b. Beispiel: ggT(60,21)=3 Bestimmung über Primfaktorzerlegung oder mit euklidischem Algorithmus. Satz: Zu a,b∈ℕ existieren s,t∈ℤ so dass ggT(a,b)=s∙a + t∙b Bemerkung: s,t sind nicht eindeutig Beispiel: s=-1, t=3, denn (-1)∙60+3∙21 = 63-60 = 3 Beweis (indirekt): Sei d die kleinste natürliche Zahl, die man in der Form d=s∙a+t∙b, also a Linearkombination von a und b, schreiben kann. (Bem.: indirekter Beweis, da Konstruktion von d nicht angegeben wird) Nach Definition gilt (ggT(a,b)|a) und (ggT(a,b)|b) und damit auch (ggT(a,b)|d). Wir zeigen, das auch d|a gilt: wir schreiben a= q∙d + r mit 0≤r<d (ganzzahlige Division mit Rest) a=⌊a/d⌋+(a mod d) r = a-q∙d = a-q(sa+tb) = (1-qs)∙a+tb also muss r=0 sein, sonst wegen r<d folgt der Widerspruch zur Annahme, dass d minimal war. Analog folgt wegen Symmetrie auch: d|b Also auch d|ggT(a,b) und damit d=ggT(a,b). □ Beispiel Berechnung von ggT(60,21) mit euklidischem Algorithmus: ggT(60,21)=ggt(60-2∙21,21)=ggt(18,21)=ggt(18,21-1∙18)=ggt(18,3)=3 Wir erinnern uns an Teilerverbände: Alle Teiler einer Zahl bilden einen Verband. Als ⊑ nehmen wir | d.h. a "kleiner" als b, falls a ein Teiler von b; der ggT(a,b) entspricht dann Infimum a⊓b im Verband. Damit können wir die Beweisprinzipien von dort wiederverwenden! z.B. z ⊑ x und z ⊑ y dann z ⊑ x⊓y wird zu z | x und z | y dann z | ggt(x,y) Satz: Für a,b∈ℤ mit a≠0, b≠0, a≥b und b∤a gilt ggT(a,b) = ggT(a mod b, b) Beweis: Da ggT(a,b) das Infimum im Teilerverband ist, genügt es zu zeigen: ① ggT(a,b) | a mod b ② ggT(a,b) | b ③ ggT(a mod b,b) | a ④ ggT(a mod b,b) | b ( ①&② besagen: ggT(a,b) ⊑ ggT(a mod b, b) wobei ⊑ ja gerade | ist ③&④ besagen: ggT(a,b) ⊒ ggT(a mod b, b) und alle vier bedeuten Gleicheit ) ②: Trivial. (Beweisprinzip Inf.2) ①: Es gilt a = ⌊a/b⌋∙b + a mod b Aus ggT(a,b)|a folgt ggT(a,b)|⌊a/b⌋∙b + a mod b und damit ggT(a,b) | a mod b, denn nach Lemma folgt aus z|x+y und z|x auch z|y. ③: Es gilt a = ⌊a/b⌋∙b + a mod b Nach Definition ggT(a mod b,b) | b (und damit auch ggT(a mod b,b) | ⌊a/b⌋∙b) und ggT(a mod b,b) | a mod b also gilt ggT(a mod b,b) | a wie benötigt, denn nach Lemma folgt aus z|x und z|y auch z|x+y ④: Trivial. (Beweisprinzip Inf.2) □ Daraus entwickeln wir den Euklidischen Algorithmus zur Berechnung des ggT(a,b): ggT(a,b) = { b , falls a == 0 a , falls b == 0 ggT(b,a) , falls b > a ggT(a mod b,b), sonst } äquivalent in Haskell: ggT(a,b) | a == 0 = b | b == 0 = a | b > a = ggT(b,a) | otherwise = ggT(a `mod` b, b) Haskell-Code (siehe Promo, ohnehin nahe an mathematischer Notation) 1. Beispiel: > ggT (24,15) = ggT(9,15) = ggT(15,9) = ggT(6,9) = ggT(9,6) = ggT(3,6) = ggT(6,3) = ggT(0,3) 3 2. Beispiel: 24948 8721 | 7506 8721 | 7506 1215 | 216 1215 | 216 135 | 81 135 | 81 54 | 27 54 | 27 0 | Erweiterter Euklidischer Algorithmus liefert Linearkombination für ggT, d.h. Zahlen s,t∈ℤ mit ggT(a,b)=s∙a+t∙b, d.h. konstruktiver Beweis für den vorletzen Satz: eggT(a,b) | a == 0 = (b,0,1) | b == 0 = (a,1,0) | b > a = let (d,s,t) = eggT(b,a) in (d,t,s) | otherwise = (d,s,t-s*(a `div` b)) where (d,s,t) = eggT(a `mod` b, b) eggT (a,b) | a == 0 = (b,0,1) | b == 0 = (a,1,0) | b > a = (d,t,s) where (d,s,t) = eggT(b,a) eggT (a,b) = (d,s,t-s*(a `div` b)) where (d,s,t) = eggT(a `mod` b, b) Nebenrechnung im letzten Fall: Es gilt d = s∙(a mod b) + t∙b d = s∙(a-⌊a/b⌋∙b) + t∙b = s∙a + (t - s∙⌊a/b⌋)∙b 1. Beispiel: > eggT (24,15) 3 = 0*6 + 1*3 3 = 1*9 + -1*6 3 = -1*15 + 2*9 3 = 2*24 + -3*15 (3,2,-3) In Tabellenform: a b | ⌊a/b⌋ t s-⌊a/b⌋∙t b (a mod b) | ⌊b/a mod b⌋ s t 1. Beispiel: a b | ⌊a/b⌋ s t 24 15 | 1 2 -3 15 9 | 1 -1 2 9 6 | 1 1 -1 6 3 | 2 0 1 3 0 | 1 0 ========================================================= ENDE VORLESUNG 18.5.16 ========================================================= 2. Beispiel: a b | ⌊a/b⌋ s t 96 15 | 6 -2 13 15 6 | 2 1 -2 6 3 | 2 0 1 3 0 | 1 0 3. Beispiel: 24948 8721 | 2 122 -349 8721 7506 | 1 -105 122 7506 1215 | 6 17 -105 1215 216 | 5 -3 17 216 135 | 1 2 -3 135 81 | 1 -1 2 81 54 | 1 1 -1 54 27 | 1 0 1 27 0 | 1 0 Anwendungen: * Lineare Kongruenzgleichungen Gegeben: a,b,m ∈ ℤ, mit m > 1 Man bestimme x∈ℤ mit ax≡b (mod m) Beispiele: ① 2x ≡ 3 (mod 6) hat keine Lösung, da sonst 2x=3+t∙6 für t∈ℤ, aber 2|2x aber 2∤3+t∙6 ② 5x ≡ 2 (mod 7) hat Lösung x=6, x=-1, x=13, … Satz: Für a,b,m ∈ ℤ, m∈ℕ mit m > 1 hat die Gleichung ax≡b (mod m) genau eine Lösung im Bereich {0,…,m-1}, wenn a und m teilerfremd sind. [Ohne Beweis:] Ist ggT(a,m)>1, so gibt es nur dann eine Lösung, wenn ggT(a,m)|b und diese ist modulo m eindeutig. Beweis: (ggf. Übung) Es sei ggT(a,m)=1. Nach dem erw. eukl. Alg. existieren s,t∈ℤ mit 1 = s∙a + t∙m und damit auch b = sab + tbm Damit ist x'=sb eine Lösung. Insbesondere ist x=(sb) mod m die gesuchte Lösung im Bereich {0,…,m-1}. Die Eindeutigkeit dieser Lösung modulo m: Sei a,m fest aber beliebig. Zu jedem b∈{0,…,m-1} gibt es ein x∈{0,…,m-1} mit ax≡b(mod m). Damit gehört jedes x zu genau einem b, bzw. die Abbildung von b nach x ist injektiv, denn ein x kann nicht Lösung von ax≡b₁(mod m) und ax≡b₂(mod m) sein. Da beide Mengen gleich groß sind, muss die Abbildung auch surjektiv sein. Spezialfall b=1: Eine Lösung x von ax≡1 (mod m) heisst _Inverses_ von "a modulo m". Solche Inversen existieren genau dann, wenn ggT(a,m)=1. NB: z.B. wichtig in der Kryptographie. Berechnung mit erw.eukl.Alg.: eggT(a,m)=(1,s,t), d.h. 1=s∙a+t∙m, d.h. s mod m ist das Inverse. Beispiel: Inverses zu 5 modulo 7 ist 3: 3∙5=15 und 15≡1(mod 7) Bemerkung: Damit können wir auch lineare diophantische Gleichung ax+by=c mit x,y,a,b,c∈ℤ. lösen, indem wir ax≡c(mod b) betrachten. Chinesische Restsatz (Chinese Remainder Theorem - CRT) Für b₁,…,bₖ∈ℕ und m₁,…,mₖ∈ℕ mit ggT(mᵢ,mⱼ)=1 für i≠j (also paarweise teilerfremd), so existiert genau eine Lösung x∈{0,…,(m₁∙m₂∙…mₖ)-1} (also x∈ℤ_{Πmᵢ}) mit x≡b₁ (mod m₁) x≡b₂ (mod m₂) ⋮ x≡bₖ (mod mₖ) Beispiel: x≡0 (mod 2) x≡1 (mod 3) x≡4 (mod 5) Lösung: x=4 Beweis (nicht-konstruktiv): Betrachte f:{0,…,(Πmᵢ)-1} → {0,…,m₁-1}×{0,…,m₂-1}×…{0,…,mₖ-1} gegeben durch f(x)=(x mod m₁,x mod m₂,…,x mod mₖ), d.h. f "probiert" einfach alles durch. Behauptung: f ist injektiv. Indirekter Beweis: angenommen, es gäbe x₁≠x₂ mit f(x₁)=f(x₂), dann ist f((x₁-x₂) mod (Πmᵢ)) = (0,…,0) da modulo mit Differenz vertauschbar ist. Damit gilt m₁|x₁-x₂ m₂|x₁-x₂ ⋮ mₖ|x₁-x₂ Da die mᵢ paarweise teilerfremd sind, gilt auch Πmᵢ|x₁-x₂ und deshalb ist x₁≡x₂(mod Πmᵢ) ↯ Da f injektiv und Definitions- und Wertemenge von f die gleiche Zahl von Elementen haben, ist f auch surjektiv. Damit existiert immer eine Lösung! □ Anwendung: Lösung mehrerer linearer diophantischer Gleichungen gemäß der vorher besprochenen Inversion. Satz "Kleiner Fermat": Für alle natürlichen Zahlen n≥2 gilt: n ist prim genau dann, wenn a^(n-1)≡1 (mod n) für alle a∈ℤₙ\{0} gilt (d.h. a ∈{1,2,…,n-1}) Später bewiesen von Euler durch Verallgemeinerung: Satz von Euler: Für alle n∈ℕ mit n≥2 gilt: a^(φ(n))≡ 1 (mod n) für alle a∈ℤₙ* Dabei ist: φ(n)≝ |ℤₙ*| (eulersche Phi-Funktion) ℤₙ* ≝ { a ∈ ℤₙ\{0} | ggT(a,n)=1 } d.h. ℤₙ* sind alle zu n teilerfremden Zahlen modulo n Lemma: Ist n = p₁^e₁∙…∙pₖ^eₖ für paarweise verschiedene Primzahlen pᵢ, so gilt k φ(n) = Π (pᵢ-1)pᵢ^(eᵢ-1) i=1 Beweis: Für eine Primzahl p gilt φ(p)=(p-1), da alle kleineren Zahlen teilerfremd sind. Weiterhin gilt auch für jedes j∈ℕ auch φ(pʲ)=(p-1)p^(j-1), denn die einzigen Teiler von pʲ sind Vielfache von p, genauer: p,2p,3p,…,pʲ. Dazwischen liegen jeweils (p-1)-viele der gesuchten teilerfremden Zahlen. Weiterhin gilt für zwei teilerfremde Zahlen q und r, dass φ(q∙r)=φ(q)∙φ(r). Der Rest der Behauptung folgt dann mit Induktion über k.
Artikelaktionen