Der Satz von Euler-Fermat: Unterschied zwischen den Versionen

Aus FunFacts Wiki
Zur Navigation springen Zur Suche springen
(Weiter Beweis)
 
Zeile 64: Zeile 64:
  
  
−
== Beweis des Satzes von Euler-Fermat ==
 
−
Es gibt verschiedene Beweise für den Satz von Euler-Fermat. In diesem Beweis wird der Satz von Euler-Fermat als Anwendung des Satzes von Lagrange betrachtet. <br>
 
−
<br>
 
−
Betrachtet man den Ring <math> \mathbb{Z}/n\mathbb{Z} </math>, so existiert für <math> [k] </math> ein inverses Element <math> [k^{-1}] </math>, Da <math> \text{ggT}(k,n) = 1</math>.
 
  
−
=== Beispiele zum inversen Element ===
 
−
<b>Fall 1</b>: <math> n = 3, \ k = 2 </math> ,also <math> \text{ggT}(2,3) = 1 </math> <br>
 
−
In diesem Fall hat 2 ein inverses Element, denn <math> 2 * 2 = [4] = [1] </math>
 
−
 
−
<b>Fall 2</b>: <math> n = 4, \ k = 2 </math> ,also <math> \text{ggT}(4,2) = 2 </math> <br>
 
−
Damit 2 ein inverses Element hat, muss ein Element <math> i </math> in <math> \mathbb{Z}/4\mathbb{Z} </math> existieren, sodass <math> 2 * i = [1]</math>, also <math> 2 * i \in \{1, 5, 9, 13, \dots\}</math><br>
 
−
Aber:
 
−
*<math> 2*0 = 0 \not = [1] </math>
 
−
*<math> 2*1 = 2 \not = [1] </math>
 
−
*<math> 2*2 = 4 \not = [1] </math>
 
−
*<math> 2*3 = 5 \not = [1] </math>
 
−
 
−
Es gibt also kein inverses Element im Ring <math> \mathbb{Z}/4\mathbb{Z} </math>.
 
  
 
== Spezialfall ==
 
== Spezialfall ==

Aktuelle Version vom 31. März 2021, 18:32 Uhr

Aussage

Für alle [math] k, n \in \mathbb{Z}_{\gt 0}[/math] mit ggt[math](k,n) = 1 [/math] gilt \[ k^{\varphi(n)} \equiv 1 \ (\text{mod} \ n) \]

Für [math] k^{\varphi(n)}[/math] gilt also [math] [k^{\varphi(n)}] = [1] [/math].

ggT

ggT steht für größter gemeinsamer Teiler und liefert die größte ganze Zahl, die alle angegebenen Zahlen ohne Rest teilt.
Also ist eine Zahl [math]g=[/math] ggT([math]z_1, \dots , z_n)[/math], falls gilt:

[math] (i) \ z_i\text{ mod } g = 0 \ \forall 1 \leq i \leq n [/math]

[math] (ii)\ \text{Für alle } h \in \mathbb{Z} \text{ mit } z_i \text{ mod } h = 0 \ \forall 1 \leq i \leq n \text{ gilt: } h \leq g [/math]

Beispiel

Betrachten wir ggT(8,12).

  • Die Zahl 9 wird ganzzahlig von den Zahlen [math] \{1, 2, 4, 8\}[/math] geteilt.
  • Die Zahl 12 wird ganzzahlig von den Zahlen [math] \{1, 2, 3, 4, 6, 12\} [/math] geteilt.
  • Die gemeinsamen Teiler sind also [math] \{1, 2, 4\} [/math].
  • Somit ist der größte gemeinsame Teiler 4.

Also: [math]\text{ggT}(8,12) = 4[/math].

Sonderfall

Gilt [math] \varphi(p) = p-1 [/math] für eine Zahl [math] p [/math], so ist [math]p[/math] eine Primzahl. Dies folgt daraus, dass in diesem Fall jede Zahl, die kleiner als [math]p[/math] ist, nur 1 als größten gemeinsamen Teiler hat.


Die Eulersche [math] \varphi [/math]-Funktion

Die Eulersche [math] \varphi [/math]-Funktion ordnet einer positiven ganzen Zahl [math]m[/math] die Anzahl der ganzen positiven Zahlen zu, für die gilt:

  • Die Zahl ist kleiner oder gleich [math]m[/math].
  • Der größte gemeinsame Teiler von [math]m[/math] und der Zahl ist 1.

Also: \[ \varphi: \ \mathbb{Z}_{>0} \longrightarrow \mathbb{C}\] \[ m \mapsto |\{d \in \mathbb{Z} | 1 \leq d \leq m \text{ und ggT}(d,m) = 1\}|\]

Beispiel

Wir betrachten [math] \varphi(6)[/math].

  • Es werden alle Zahlen betrachtet, die kleiner oder gleich 6 sind.
  • Zuerst wird der [math]\text{ggT}(h,6) \ \forall 1\leq h \leq 6[/math] betrachtet.
[math]h[/math] 1 2 3 4 5 6
[math]\text{ggT}(h,6)[/math] 1 2 3 2 1 2
  • Für die [math]\varphi[/math]-Funktion werden nur die Zahlen betrachtet, für die der größte gemeinsame Teiler von 6 und der Zahl 1 ist. Also bleiben [math]\{1,5\}[/math].
  • Da gilt [math]|\{1,5\}| = 2[/math] ist [math] \varphi(6) = 2 [/math]



Spezialfall

Ein Spezialfall des Satzes ist der kleine Fermatsche Satz.

Anwendungen

Der Satz von Euler-Fermat findet unter anderem in der Kryptographie anwendung. Beispielsweise beim RSA-Verfahren.


Quellen

Lassueur, Dr. Caroline(2017): Elementare Zahlentheorie – Kurzskript zur Vorlesung

Abgerufen von „https://funfacts.mathi.uni-heidelberg.de/index.php?title=Der_Satz_von_Euler-Fermat&oldid=2724“