Worksheet: Unterschied zwischen den Versionen
(→Kleiner Satz von Fermat) |
(→Sätze zur Eulerschen Phi-Funktion) |
||
| Zeile 82: | Zeile 82: | ||
# <math>ggT(m,n)=1\Rightarrow \varphi(m\cdot n) = \varphi(m)\cdot\varphi(n)</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>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> | ||
| + | {{PHHDLückeMitText|Beweis: | ||
| + | <math>\varphi(n)\ =\ \varphi(\prod_{i=1}^r p_i^k_i)\ = \prod_{i=1}^r \varph (p_1^k_i)\ =\ \prod_{i=1}^r (p_i^k_i \ -\ p_i^{k_i-1}) \ =\ \prod_{i=1}^r p_i^k_i \ \ (1\ -\ \frac{1}{p_i} )\ =\ \prod_{i=1}^r p_i^k_i \ \prod_{i=1}^r(1\ -\ \frac{1}{p_i} )\ =\ n\ \prod_{i=1}^r(1\ -\ \frac{1}{p_i} )</math> | ||
| + | |||
# <math>\sum_{d|n} \varphi(d)=n</math> | # <math>\sum_{d|n} \varphi(d)=n</math> | ||
Version vom 12. Dezember 2012, 14:23 Uhr
Inhaltsverzeichnis |
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
mod
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 
Dies kann man zeigen, indem man annimmt, dass 
. Dies würde bedeuten, dass 
, da...
und dies ist ein Widerspruch dazu, dass...
Nun bilden wir das Produkt 
Anschließend teilen wir alles durch 
und erhalten somit...
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: 
mod
Nun haben wir den Satz von Euler und den Kleinen Satz von Fermat. Doch ein Problem bleibt weiterhin bestehen: Wie bestimmt man ganz allgemein ?
Fall 1: Wenn m eine Primzahl mit 
ist, dann gilt .
Fall 2: Wenn m eine Primzahlpotenz ist, dann ist 
Sätze zur Eulerschen Phi-Funktion
So, jetzt aber... wir bestimmen für verschiedene Fälle:
- Wenn prim, dann
-
- 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
{{PHHDLückeMitText|Beweis: Fehler beim Parsen(Unbekannte Funktion „\varph“): \varphi(n)\ =\ \varphi(\prod_{i=1}^r p_i^k_i)\ = \prod_{i=1}^r \varph (p_1^k_i)\ =\ \prod_{i=1}^r (p_i^k_i \ -\ p_i^{k_i-1}) \ =\ \prod_{i=1}^r p_i^k_i \ \ (1\ -\ \frac{1}{p_i} )\ =\ \prod_{i=1}^r p_i^k_i \ \prod_{i=1}^r(1\ -\ \frac{1}{p_i} )\ =\ n\ \prod_{i=1}^r(1\ -\ \frac{1}{p_i} )
Beweis:
Noch ein Satz
Für und Primzahl gilt: 
mod
Beweis: Mmh... hier brauchen wir jetzt aber eine Fallunterscheidung...
