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