Worksheet: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
(Noch ein Satz)
Zeile 1: Zeile 1:
== Motivation ==
+
__NOTOC__
 +
[http://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Sätze_von_Euler_und_Fermat/Worksheet&printable=yes Druckversion]
  
 +
== 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.
 
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.
  

Version vom 12. Dezember 2012, 16:57 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 alggemeinen 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:






















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

Beweis:
Fehler beim Parsen(PNG-Konvertierung fehlgeschlagen. Bitte die korrekte Installation von LaTeX und dvipng überprüfen (oder dvips + gs + convert)): \varphi(n)\ =\ \varphi(\prod_{i=1}^r p_i^k_i)\ =






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

Beweis: