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 …“)
 
(Arbeitsblatt)
 
(39 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
 +
__NOTOC__
 +
[https://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Sätze_von_Euler_und_Fermat/Worksheet&printable=yes Druckversion]
 +
 
== Motivation ==
 
== Motivation ==
 +
Im Laufe der Veranstaltung hatten wir uns einmal mit Aufgaben der Form <math>a^e\equiv b</math> mod <math>  m</math> befasst, beispielsweise bei der Frage, was die letzte Dezimalstelle einer Potenz ist (<math>3^{160}</math> mod <math>10=...</math>) oder welchen Rest eine Zahl beispielsweise bei der Division durch 8 lässt (<math>3^{160}</math> mod <math>8</math>). Der Trick dabei war, dass man versucht hat die Potenz derart in <math>a^{(e_1\cdot e_2)}=(a^{e_1})^{e_2}</math> zu zerlegen, dass <math>a^{e_1}\equiv 1</math> mod <math>m</math> (oder z.B. alternativ <math>a^{e_1}\equiv -1</math> mod <math>m</math>... halt was einfaches). Die Zerlegung ist aber gar nicht immer leicht (Bsp: <math>11^{182}</math> mod <math>19=...</math>). In diesem Abschnitt werden wir ein paar Tricks kennen lernen, wie man in bestimmten Fällen herausfindet, welche Potenzen kongruent <math>1</math> mod <math>m</math> sind. An dieser Stelle bietet sich eine kleine Wiederholung an.
  
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 Dezimalstelle einer Potenz ist(<math>3^{160}</math> mod <math>10=...</math>) oder ähnliche Probleme (<math>3^{160}</math> mod <math>8=...</math>). Der Trick dabei war, dass man versucht hat die Potenz derart in <math>a^{(e_1\cdot e_2)}=(a^{e_1})^{e_2}</math> zu zerlegen, dass <math>a^{e_1}\equiv 1</math> mod <math>m</math> (oder z.B. alternativ <math>a^{e_1}\equiv -1</math> mod <math>m</math>... halt was einfaches). Die Zerlegung ist aber gar nicht immer leicht (Bsp: <math>11^{182}</math> mod <math>19=...</math>). In diesem Abschnitt werden wir ein paar Tricks kennen lernen, wie man in bestimmten Fällen herausfindet, welche Potenzen kongruent <math>1</math> mod <math>m</math> sind.
+
{{PHHDLückeMitText|Bestimme...<br /><br />
 +
<math>3^{160}</math> mod <math>10</math><br /><br />
 +
<math>3^{161}</math> mod <math>10</math><br /><br />
 +
<math>3^{160}</math> mod <math>8</math><br />
 +
<br />
 +
}}
  
== Wiederholung ==
+
{{PHHDLückeMitText|Ergänze folgende Aussagen!<br />
 
+
# Zwei Zahlen <math>a</math> und <math>b</math> heißen genau dann teilerfremd , wenn ...<br /><br />
# Zwei Zahlen <math>a</math> und <math>b</math> heißen teilerfremd genau dann, wenn <math>ggT(a,b)=1</math>
+
# Wenn <math>ac\equiv bc</math> mod <math>m</math> und <math>ggT(c,m)=1</math>, dann gilt ...
# Wenn <math>ac\equiv bc</math> mod <math>m</math> und <math>ggT(c,m)=1</math>, dann gilt auch <math>a\equiv b</math> mod <math>m</math>
+
}}
 +
<br />
  
 
== Die Eulersche Phi-Funktion ==
 
== Die Eulersche Phi-Funktion ==
  
{{#ev:youtube|I74D-g1ZbDQ}}
+
Wir definieren die Eulersche Phi-Funktion folgendermaßen: <math>\varphi(m)=</math>
  
 
+
{{PHHDLückeMitText|Beispiele:
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>
+
* <math>\varphi(6)= 2 </math> nämlich 1 und 5
 
+
Beispiele:
+
 
* <math>\varphi(8)=...</math>
 
* <math>\varphi(8)=...</math>
 
* <math>\varphi(12)=...</math>
 
* <math>\varphi(12)=...</math>
 
* <math>\varphi(17)=...</math>
 
* <math>\varphi(17)=...</math>
 +
* <math>\varphi(19)=...</math>
 +
* <math>\varphi(22)=...</math>
 +
* <math>\varphi(23)=...</math>
 +
* <math>\varphi(p)=...</math>
 +
}}
 +
<br />
  
 
== Satz von Euler ==
 
== Satz von Euler ==
  
<math>ggT(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1</math> mod <math>m</math>
+
<math>ggT(a,m)=1\Rightarrow </math>
  
Beweis: Video
+
{{PHHDLückeMitText|Beweis:
 +
Es gelte: <math>ggT(a,m)=1</math><br /><br />
 +
<math>\varphi(m)</math> liefert uns die Anzahl der zu m teilerfremden Zahlen aus <math>\mathbb {Z_m}</math>. Diese bezeichnen wir als <math>k_1, k_2, ..., k_{\varphi(m)}</math>. Dabei sind alle k teilerfremd zu m.<br />
 +
<br />
  
{{#ev:youtube|DU082wcr40A}}
+
----
 
+
Beispiel: <math>m=8\ \Rightarrow\ \varphi(8)=4</math> (1, 3, 5, 7)
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! :-)
+
----
  
 +
Nun multiplizieren wir diese k mit a, welches auch teilerfremd zu m ist (siehe Voraussetzung).
 +
Dabei erhalten wir...<br /><br />
 +
<math>ak_1, ak_2, ..., ak_{\varphi(m)}</math><br /><br />
 +
Für diese einzelnen Produkte gilt nun ...<br />
 +
----
 +
Beispiel: <math>m=8\ \Rightarrow\ \varphi(8)=4</math> (1, 3, 5, 7)
 +
Nun sei <math>a=3</math> und wir multiplizieren unsere k (1, 3, 5, 7) mit a und erhalten somit in <math>\mathbb {Z_8}</math> ...<br />
 +
Man kann an diesem Beispiel sehen, dass keine neuen Restklassen entstehen und es sich um eine Permutation handelt.
 +
----
 +
Es muss gelten, dass <math>ak_i\ \not =\ ak_j\ mod\ m</math><br /><br />
 +
Führe den Beweis an dieser Stelle weiter!<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />
 +
}}
  
 
Im Allgemeinen ist natürlich jetzt interessant: Wie bekommt man denn nun <math>\varphi(m)</math> einfach heraus?
 
Im Allgemeinen ist natürlich jetzt interessant: Wie bekommt man denn nun <math>\varphi(m)</math> einfach heraus?
  
 
Für eine Primzahl <math>p</math> ist es noch einfach: <math>\varphi(p)=p-1</math>. Aber was, wenn <math>m</math> keine Primzahl ist?
 
Für eine Primzahl <math>p</math> ist es noch einfach: <math>\varphi(p)=p-1</math>. Aber was, wenn <math>m</math> 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:
+
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 und muss somit nicht extra bewiesen werden.
  
 
== 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: <br />
 +
<br />
 +
Nun haben wir den Satz von Euler und den Kleinen Satz von Fermat. Doch ein Problem bleibt weiterhin bestehen: Wie bestimmt man ganz allgemein <math>\varphi (m)</math>?<br />
  
== Sätze zur Eulerschen Phi-Funktion ==
+
== Einige Sätze zur Eulerschen Phi-Funktion ==
  
 
So, jetzt aber... wir bestimmen <math>\varphi(m)</math> für verschiedene Fälle:
 
So, jetzt aber... wir bestimmen <math>\varphi(m)</math> für verschiedene Fälle:
  
# Wenn <math>p</math> prim, dann <math>\varphi(p^n)=p^n-p^{n-1}</math>
 
# <math>ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)</math>
 
# <math>n=\prod_{i=1}^r p_i^k_i</math> und <math>k_i\geq 1 \Rightarrow \varphi(n)=n\prod_{i=1}^r(1-\frac{1}{p_i})</math>
 
# <math>\sum_{d|n} \varphi(d)=n</math>
 
 
Beweise: Video
 
 
{{#ev:youtube|9VI0LKh6c9g}}
 
 
{{#ev:youtube|ARoYsesiHdU}}
 
 
{{#ev:youtube|KEYIkRcDyAw}}
 
 
{{#ev:youtube|Z86ZU_vDiTM}}
 
 
== Noch ein Satz ==
 
 
Für <math>a\in\mathbb{N}</math> und <math>p</math> Primzahl gilt: <math>a^p\equiv a</math> mod <math>p</math>
 
 
Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...
 
 
== Der große Satz von Fermat ==
 
  
{{#ev:youtube|dy-Queapz-I}}
+
* Wenn <math>m\ =\ p</math> und <math>p</math> prim, dann <math>\varphi(p^n)=p^n-p^{n-1}</math>
 +
{{PHHDLückeMitText|Mache dir diesen Satz zuerst am Beispiel 3<sup>5</sup> klar, um anschließend den allgemeinen Beweis besser nachvollziehen zu können.
 +
Zuerst muss klar sein wie viele Zahlen zwischen 1 und 3<sup>5</sup> liegen. Dies sind 3<sup>5</sup>. Nun kann man sich überlegen, welche Zahlen nicht teilerfremd zu 3<sup>5</sup> sind. Dies sind alle Vielfachen der 3, also jede dritte Zahl.<br />
 +
Also <math>\ 1\ \cdot\ 3,\ 2\ \cdot\ 3,\ 3\ \cdot\ 3,\ ...\ ,\ p^{5-1}\ \cdot\ 3</math><br />
 +
Also sind es 3<sup>5</sup> <math>\cdot\ \frac {1}{3} </math> bzw. 3<sup>5</sup> : 3<sup>1</sup>, also 3<sup>4</sup> Zahlen. Demzufolge sind 3<sup>5</sup> - 3<sup>4</sup> Zahlen zwischen 1 und 3<sup>5</sup> teilerfremd zu 3<sup>5</sup>.<br />
 +
Führe an dieser Stelle den allgemeinen Beweis: Gegeben sei p mit p prim und n <math>\in \mathbb{N}</math>.<br /><br /><br /><br /><br /><br /><br />
 +
}} <br /><br />
 +
* <math>ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)</math><br />
 +
{{PHHDLückeMitText|Beweis:<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />}}<br /><br />
 +
* <math>n=\prod_{i=1}^r {p_i}^{k_i}</math> und <math>k_i\geq 1 \Rightarrow \varphi(n)=n\prod_{i=1}^r(1-\frac{1}{p_i})</math><br />
 +
{{PHHDLückeMitText|Beweis:<br />
 +
<math>\varphi(n)\ =\ \varphi(\prod_{i=1}^r {p_i}^{k_i})\ = </math><br /><br /><br /><br /><br />
 +
}}<br /><br />
  
{{#ev:youtube|3rS5dlZaymM}}
+
* <math>\sum_{d|n} \varphi(d)=n</math>
  
 +
{{PHHDLückeMitText|Beweis:<br /><br /><br /><br /><br /><br /><br /><br />
 +
}}
 +
<br />
  
An dieser Stelle sollten wir vielleicht ein paar Worte über den "großen Satz von Fermat" verlieren, der besagt:
+
== Fragen ==
  
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.
+
Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!
  
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>
+
{{PHHDLückeGroß}}
  
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
+
[[Kategorie:Arbeitsblatt Mathematik PH Heidelberg|Sätze von Euler und Fermat]]
* [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]
+

Aktuelle Version vom 11. Dezember 2016, 16:43 Uhr

Druckversion

Motivation

Im Laufe der Veranstaltung hatten wir 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 welchen Rest eine Zahl beispielsweise bei der Division durch 8 lässt (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. An dieser Stelle bietet sich eine kleine Wiederholung an.

Bestimme...

3^{160} mod 10

3^{161} mod 10

3^{160} mod 8

Ergänze folgende Aussagen!

  1. Zwei Zahlen a und b heißen genau dann teilerfremd , wenn ...

  2. Wenn ac\equiv bc mod m und ggT(c,m)=1, dann gilt ...


Die Eulersche Phi-Funktion

Wir definieren die Eulersche Phi-Funktion folgendermaßen: \varphi(m)=

Beispiele:

  • \varphi(6)= 2 nämlich 1 und 5
  • \varphi(8)=...
  • \varphi(12)=...
  • \varphi(17)=...
  • \varphi(19)=...
  • \varphi(22)=...
  • \varphi(23)=...
  • \varphi(p)=...


Satz von Euler

ggT(a,m)=1\Rightarrow

Beweis: Es gelte: ggT(a,m)=1

\varphi(m) liefert uns die Anzahl der zu m teilerfremden Zahlen aus \mathbb {Z_m}. Diese bezeichnen wir als k_1, k_2, ..., k_{\varphi(m)}. Dabei sind alle k teilerfremd zu m.


Beispiel: m=8\ \Rightarrow\ \varphi(8)=4 (1, 3, 5, 7)


Nun multiplizieren wir diese k mit a, welches auch teilerfremd zu m ist (siehe Voraussetzung). Dabei erhalten wir...

ak_1, ak_2, ..., ak_{\varphi(m)}

Für diese einzelnen Produkte gilt nun ...


Beispiel: m=8\ \Rightarrow\ \varphi(8)=4 (1, 3, 5, 7) Nun sei a=3 und wir multiplizieren unsere k (1, 3, 5, 7) mit a und erhalten somit in \mathbb {Z_8} ...
Man kann an diesem Beispiel sehen, dass keine neuen Restklassen entstehen und es sich um eine Permutation handelt.


Es muss gelten, dass ak_i\ \not =\ ak_j\ mod\ m

Führe den Beweis an dieser Stelle weiter!











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 und muss somit nicht extra bewiesen werden.

Kleiner Satz von Fermat

Für a\in\mathbb{N} und Primzahlen p mit p\not| a gilt:

Nun haben wir den Satz von Euler und den Kleinen Satz von Fermat. Doch ein Problem bleibt weiterhin bestehen: Wie bestimmt man ganz allgemein \varphi (m)?

Einige Sätze zur Eulerschen Phi-Funktion

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


  • Wenn m\ =\ p und p prim, dann \varphi(p^n)=p^n-p^{n-1}

Mache dir diesen Satz zuerst am Beispiel 35 klar, um anschließend den allgemeinen Beweis besser nachvollziehen zu können. Zuerst muss klar sein wie viele Zahlen zwischen 1 und 35 liegen. Dies sind 35. Nun kann man sich überlegen, welche Zahlen nicht teilerfremd zu 35 sind. Dies sind alle Vielfachen der 3, also jede dritte Zahl.
Also \ 1\ \cdot\ 3,\ 2\ \cdot\ 3,\ 3\ \cdot\ 3,\ ...\ ,\ p^{5-1}\ \cdot\ 3
Also sind es 35 \cdot\ \frac {1}{3} bzw. 35 : 31, also 34 Zahlen. Demzufolge sind 35 - 34 Zahlen zwischen 1 und 35 teilerfremd zu 35.
Führe an dieser Stelle den allgemeinen Beweis: Gegeben sei p mit p prim und n \in \mathbb{N}.








  • ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)

Beweis:






















  • 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})

Beweis:
\varphi(n)\ =\ \varphi(\prod_{i=1}^r {p_i}^{k_i})\ =






  • \sum_{d|n} \varphi(d)=n

Beweis:








Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!