Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2017 / Logik und Diskrete Strukturen / Material / K04 Modulare Arithmetik


Inhaltsbereich

K04 Modulare Arithmetik

Entspricht Kapitel 3.1 und 3.2 aus A.Steger: Teilbarkeit, Primzahlen und modulare Arithmetik

Plain Text icon K04_ModulareArithmetik.txt — Plain Text, 17 KB (18039 bytes)

Dateiinhalt

Persönliche Notizen zur Vorbereitung der LDS Vorlesung. 
Diese Notizen waren ursprünglich nicht zur Herausgabe gedacht 
und sind entsprechend mit Vorsicht zu genießen. 

Es wird dringend empfohlen, dass Buch zu verwenden:
Angelika Steger: Diskrete Strukturen. 
Band 1: Kombinatorik, Graphentheorie, Algebra.
2. Auflage, Springer 2007, 978-3-540-46660-4


=========================================================
 Zahlentheorie und Arithmetik (Buch Kapitel 3.1 und 3.2)
=========================================================

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 Definitionen 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∈ℤ.
 * Auf ℕ ist Teilbarkeit ist partielle Ordnung: reflexiv, transitiv & anti-symmetrisch

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) (per Def. also (a-b) mod m = 0)
 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 durch qₐ∙m+rₐ und b durch "q_b∙m+r_b")
  = ((⌊a/m⌋∙m + a mod m) + (⌊b/m⌋∙m + b mod m)) mod m 
  = (   qₐ ∙m +   rₐ     +   q_b ∙m +    r_b ) mod m 
  Aus m|(q∙m+r)-(r) und den vorangegangen Beobachtungen
  folgt (q∙m+r) mod m = r mod m und erhalten
  =              rₐ    +              r_b ) 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                ( 49 = 3∙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
    
    
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= Σ  aᵢ∙10^i f
          i=0
  Damit gilt   k
    n mod 3 = (Σ (aᵢ mod 3)∙(10 mod 3)^i  ) mod 3
              i=0
              k           
            =(Σ aᵢ 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 (nach Def. von "|")
  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⌋∙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, da wir 
  sonst eine kleinere Zahl mit dieser Eigenschaft konstruiert hätten.
  Analog folgt wegen Symmetrie des Arguments auch: d|b
  Also auch d|ggT(a,b) und damit d=ggT(a,b), da | auf ℕ anti-symmetrisch ist.
  □

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 per Definition.
  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
           }   

{- OPTIONALER EXKURS HASKELL:           
Wer zeitgleich Programmierung und Modellierung hört, kann das auch           
leicht äquivalent in Haskell schreiben:
ggT(a,b) | a == 0    = b
         | b == 0    = a
         | b >  a    = ggT(b,a)
         | otherwise = ggT(a `mod` b, b)

Der Haskell-Code ist relativ nah an der mathematischen Notation, 
obwohl Haskell eine allgemeine Programmiersprache ist. 
(Für mathematische Anwendung empfehlen sich meist spezialisierte 
numerische Programmiersprachen wie etwa Matlab oder auch 
Computeralgebrasysteme, wie zum Beispiel Maple oder Mathematica.) 


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 (hier in Haskell-Notation):

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  
  
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 
    
-------------------------    
ALTERNATIVE SCHREIBWEISE:
-------------------------

eggT'(a0,b0)
  | b0 > a0   = eggT'(b0,a0)
  | b0 == 0   = (a0,1,0)
  | otherwise = aux((a0,1,0),(b0,0,1))
  where
    aux((a,x1,y1),(b,x2,y2)) 
      | b == 0    = (a,x1,y1)      
      | otherwise = 
          let (q,r) = a `divMod` b in          
          aux((b,x2,y2),(r,x1-q*x2,y1-q*y2))
    
In Tabellenform: 
   n       | ⌊n_(i-1)/nᵢ⌋  |  s                | t
  ---------+---------------+-------------------+-------------------
      a    |               |                   |
      b    | ⌊a/b⌋         |                   |
  (a mod b)| ⌊b/(a mod b)⌋ | sᵢ-₂ - ⌊a/b⌋∙sᵢ-₁ | tᵢ-₂ = ⌊a/b⌋∙tᵢ-₁
      ⋮
  
  Für jede Zeile gilt n = s∙a + t∙b
  
Beispiele:

  n ⌊n/m⌋  s    t
 ---+---+----+----
 24 |   |  1 |  0
 15 |  1|  0 |  1
  9 |  1|  1 | -1
  6 |  1| -1 |  2
  3 |  2|  2 | -3
  0 |            
  
  n ⌊n/m⌋  s    t
 ---+---+----+----
 96 |   |  1 |  0
 15 |  6|  0 |  1
  6 |  2|  1 | -6
  3 |  2| -2 | 13
  0 |              
  
     n ⌊n/m⌋   s     t
 ------+---+-----+------  
 24948 |   |   1 |    0 
  8721 | 2 |   0 |    1
  7506 | 1 |   1 |   -2
  1215 | 6 |  -1 |    3
   216 | 5 |   7 |  -20
   135 | 1 | -36 |  103
    81 | 1 |  43 | -123
    54 | 1 | -79 |  226
    27 | 2 | 122 | -349
  
    
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∈ℤ gelten würde. 
    Dies kann nicht sein, denn aus 2|2x und 2|t∙6 folgt nach 
    Lemma auch 2|3, was offensichtlich nicht gilt!
②  5x ≡ 2 (mod 7)
    hat Lösung x=6, x=-1, x=13, …
③  2x ≡ 4 (mod 6) 
    hat dagegen 2 Lösungen in {0,1,2,3,4,5}: x=2 und x=5 
    
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 erweiterten Euklidischen Algorithmus existieren s,t∈ℤ mit
  1 = s∙a + t∙m und damit auch 
  b = bsa + btm
  Damit ist x'=bs eine Lösung. Insbesondere ist 
  x=(b∙s) 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.
  Erweiterter euklidischer Algorithmus liefert x,y mit 
  ggT(a,b) = ax+by. Falls ggT(a,b)=1, mit c multiplizieren.
  Falls ggT(a,b)|c mit c/ggT(a,b) multiplizieren. Sonst keine Lösung.

  
Chinesische Restsatz (Chinese Remainder Theorem - CRT)
[ca.200-400 BC von Sun Tsu (Wei oder Jin Dynastie), bewiesen 1247 von Qin Jiushao]
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} 
  (also f:ℤₘ → ℤₘ₁×…×ℤₘₖ für m=Πmᵢ=m₁∙m₂∙…∙mₖ)
  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 "Kleine(r) (Vermutung/Satz) von Fermat":
[Pierre de Fermat, französischer Jurist & Mathematiker, 1607-1665]
Für alle natürlichen Zahlen n≥2 gilt:
  n ist prim genau dann, wenn a^(n-1)≡1 (mod n)  (auch a^n≡a (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:
[Leonhard Euler, schweizer Mathematiker & Physiker, 1707-1783]
  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