Worksheet: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
(Die Seite wurde neu angelegt: „== Motivation == Wir hatten uns einmal mit Aufgaben der Form <math>a^e\equiv b</math> mod <math> m</math> befasst, beispielsweise bei der Frage, was die letzte …“)
 
Zeile 9: Zeile 9:
  
 
== Die Eulersche Phi-Funktion ==
 
== Die Eulersche Phi-Funktion ==
 
{{#ev:youtube|I74D-g1ZbDQ}}
 
 
  
 
Wir definieren die Eulersche Phi-Funktion folgendermaßen: <math>\varphi(m)=|\{x\in\mathbb{N}|1\leq x\leq m \wedge ggT(x,m)=1\}|</math>
 
Wir definieren die Eulersche Phi-Funktion folgendermaßen: <math>\varphi(m)=|\{x\in\mathbb{N}|1\leq x\leq m \wedge ggT(x,m)=1\}|</math>
Zeile 24: Zeile 21:
 
<math>ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1</math> mod <math>m</math>
 
<math>ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1</math> mod <math>m</math>
  
Beweis: Video
+
{{PHHDLückeMitText|Beweis: }}
 +
 
 +
 
  
{{#ev:youtube|DU082wcr40A}}
 
  
Hinweis des Studenten Flo1860: [http://wiki.zum.de/Zus%C3%A4tzlicher_Beweisteil_-_der_auf_dem_Video_fehlt_%28zu:_PH_Heidelberg/Zahlentheorie/S%C3%A4tze_von_Euler_und_Fermat_-_SoSe2012%29 Zusätzlicher Beweisteil - der im Video fehlt (zu: PH Heidelberg/Zahlentheorie/Sätze von Euler und Fermat - SoSe2012)] - fehlt das wirklich? Die Diskussion sei eröffnet! :-)
 
  
  
Zeile 38: Zeile 35:
 
== Kleiner Satz von Fermat ==
 
== Kleiner Satz von Fermat ==
  
{{#ev:youtube|o-aWqfaWVr4}}
 
  
 
Für <math>a\in\mathbb{N}</math> und Primzahlen <math>p</math> mit <math>p\not| a</math> gilt: <math>a^{p-1}\equiv 1</math> mod <math>p</math>
 
Für <math>a\in\mathbb{N}</math> und Primzahlen <math>p</math> mit <math>p\not| a</math> gilt: <math>a^{p-1}\equiv 1</math> mod <math>p</math>
Zeile 51: Zeile 47:
 
# <math>\sum_{d|n} \varphi(d)=n</math>
 
# <math>\sum_{d|n} \varphi(d)=n</math>
  
Beweise: Video
+
{{PHHDLückeMitText|Beweis: }}
 
+
{{#ev:youtube|9VI0LKh6c9g}}
+
 
+
{{#ev:youtube|ARoYsesiHdU}}
+
 
+
{{#ev:youtube|KEYIkRcDyAw}}
+
 
+
{{#ev:youtube|Z86ZU_vDiTM}}
+
  
 
== Noch ein Satz ==
 
== Noch ein Satz ==
Zeile 66: Zeile 54:
  
 
Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...
 
Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...
 
== Der große Satz von Fermat ==
 
 
{{#ev:youtube|dy-Queapz-I}}
 
 
{{#ev:youtube|3rS5dlZaymM}}
 
 
 
An dieser Stelle sollten wir vielleicht ein paar Worte über den "großen Satz von Fermat" verlieren, der besagt:
 
 
Es gibt keine <math>a,b,c\in\mathbb{Z}\setminus\{0\}</math>, welche die Gleichung <math>a^n+b^n=c^n</math> mit <math>n\geq 3</math> lösen.
 
 
Für <math>n=2</math> gibt es neben der allseits bekannten Lösung <math>a=3,b=4,c=5</math> auch unendlich viele weitere Lösungen in den natürlichen Zahlen (sogenannten Pythagoreische Zahlentripel), wie man leicht nachweisen kann, wenn man die Zahlen für <math>x,y\in\mathbb{N}</math> mit <math>x>y</math> folgendermaßen konstruiert: <math>a=x^2-y^2</math>, <math>b=2xy</math>, <math>c=x^2+y^2</math>
 
 
Aber zu beweisen, dass es für <math>n\geq 3</math> keine Lösung zu der Gleichung <math>a^n+b^n=c^n</math> gibt, ist nicht ganz so einfach, wie die Geschichte der Mathematik gezeigt hat...
 
 
* [http://de.wikipedia.org/wiki/Gro%C3%9Fer_fermatscher_Satz Großer Satz von Fermat] auf Wikipedia
 
* [http://didaktik1.mathematik.hu-berlin.de/files/fermat.pdf Der große Satz von Fermat - die Lösung eines 300 Jahre alten Problems] von Jürg Kramer
 
* [http://de.wikipedia.org/wiki/Andrew_Wiles Andrew Wiles]
 
* [http://de.wikipedia.org/wiki/Wolfskehl-Preis Wolfskehl-Preis]
 

Version vom 10. Dezember 2012, 16:31 Uhr

Inhaltsverzeichnis

Motivation

Wir hatten uns einmal mit Aufgaben der Form a^e\equiv b mod   m befasst, beispielsweise bei der Frage, was die letzte Dezimalstelle einer Potenz ist(3^{160} mod 10=...) oder ähnliche Probleme (3^{160} mod 8=...). Der Trick dabei war, dass man versucht hat die Potenz derart in a^{(e_1\cdot e_2)}=(a^{e_1})^{e_2} zu zerlegen, dass a^{e_1}\equiv 1 mod m (oder z.B. alternativ a^{e_1}\equiv -1 mod m... halt was einfaches). Die Zerlegung ist aber gar nicht immer leicht (Bsp: 11^{182} mod 19=...). In diesem Abschnitt werden wir ein paar Tricks kennen lernen, wie man in bestimmten Fällen herausfindet, welche Potenzen kongruent 1 mod m sind.

Wiederholung

  1. Zwei Zahlen a und b heißen teilerfremd genau dann, wenn ggT(a,b)=1
  2. Wenn ac\equiv bc mod m und ggT(c,m)=1, dann gilt auch a\equiv b mod m

Die Eulersche Phi-Funktion

Wir definieren die Eulersche Phi-Funktion folgendermaßen: \varphi(m)=|\{x\in\mathbb{N}|1\leq x\leq m \wedge ggT(x,m)=1\}|

Beispiele:

  • \varphi(8)=...
  • \varphi(12)=...
  • \varphi(17)=...

Satz von Euler

ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1 mod m

Beweis:




Im Allgemeinen ist natürlich jetzt interessant: Wie bekommt man denn nun \varphi(m) einfach heraus?

Für eine Primzahl p ist es noch einfach: \varphi(p)=p-1. Aber was, wenn m keine Primzahl ist? Bevor wir uns das überlegen, können wir aber schnell mal den Kleinen Satz von Fermat hinschreiben. Der ergibt sich nämlich als Spezialfall direkt aus dem Satz von Euler:

Kleiner Satz von Fermat

Für a\in\mathbb{N} und Primzahlen p mit p\not| a gilt: a^{p-1}\equiv 1 mod p

Sätze zur Eulerschen Phi-Funktion

So, jetzt aber... wir bestimmen \varphi(m) für verschiedene Fälle:

  1. Wenn p prim, dann \varphi(p^n)=p^n-p^{n-1}
  2. ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)
  3. Fehler beim Parsen(PNG-Konvertierung fehlgeschlagen. Bitte die korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): n=\prod_{i=1}^r p_i^k_i
und k_i\geq 1 \Rightarrow \varphi(n)=n\prod_{i=1}^r(1-\frac{1}{p_i})
  1. \sum_{d|n} \varphi(d)=n

Beweis:

Noch ein Satz

Für a\in\mathbb{N} und p Primzahl gilt: a^p\equiv a mod p

Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...