Worksheet: Unterschied zwischen den Versionen
(→Noch ein Satz) |
|||
| Zeile 1: | Zeile 1: | ||
| − | == | + | __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
Motivation
Im Laufe der Veranstaltung hatten wir uns einmal mit Aufgaben der Form 
mod 
befasst, beispielsweise bei der Frage, was die letzte Dezimalstelle einer Potenz ist (
mod 
) oder welchen Rest eine Zahl beispielsweise bei der Division durch 8 lässt ( mod 
). Der Trick dabei war, dass man versucht hat die Potenz derart in 
zu zerlegen, dass 
mod (oder z.B. alternativ 
mod ... halt was einfaches). Die Zerlegung ist aber gar nicht immer leicht (Bsp: 
mod 
). In diesem Abschnitt werden wir ein paar Tricks kennen lernen, wie man in bestimmten Fällen herausfindet, welche Potenzen kongruent 
mod sind. An dieser Stelle bietet sich eine kleine Wiederholung an.
Bestimme...
mod 
mod
mod
Ergänze folgende Aussagen!
- Zwei Zahlen
und 
heißen genau dann teilerfremd , wenn ...
- Wenn
mod und 
, dann gilt ...
Die Eulersche Phi-Funktion
Wir definieren die Eulersche Phi-Funktion folgendermaßen: 
Beispiele:
-
nämlich 1 und 5
-
-
-
-
-
-
-
Satz von Euler
Beweis:
Es gelte: 
liefert uns die Anzahl der zu m teilerfremden Zahlen aus 
. Diese bezeichnen wir als 
. Dabei sind alle k teilerfremd zu m.
Beispiel: 
(1, 3, 5, 7)
Nun multiplizieren wir diese k mit a, welches auch teilerfremd zu m ist (siehe Voraussetzung).
Dabei erhalten wir...
Für diese einzelnen Produkte gilt nun ...
Beispiel: (1, 3, 5, 7)
Nun sei 
und wir multiplizieren unsere k (1, 3, 5, 7) mit a und erhalten somit in 
...
Man kann an diesem Beispiel sehen, dass keine neuen Restklassen entstehen und es sich um eine Permutation handelt.
Es muss gelten, dass 
Führe den Beweis an dieser Stelle weiter!
Im Allgemeinen ist natürlich jetzt interessant: Wie bekommt man denn nun einfach heraus?
Für eine Primzahl 
ist es noch einfach: 
. Aber was, wenn 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 
und Primzahlen mit 
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 ?
Einige Sätze zur Eulerschen Phi-Funktion
So, jetzt aber... wir bestimmen für verschiedene Fälle:
- Wenn
und prim, dann 
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 
Also sind es 35 
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 
.
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
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)\ =
Beweis:
