Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2016 / Logik und Diskrete Strukturen / Material / Zahlentheorie (Vorlesungsnotizen)


Inhaltsbereich

Zahlentheorie (Vorlesungsnotizen)

Vorlesungsnotizen zum Abschnitt Zahlentheorie und modulare Arithmetik

Plain Text icon 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


Funktionsleiste