Eulersche Phi-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Konnte dieses Mal die Aufgabe nicht in dem Aufgabenfeld eingeben?!
Deswegen hier:
Die eulersche Phi-Funktion [mm] \Phi: \IN \to \IN [/mm] ist definiert über:
[m]\Phi(n) := | \left\{ k \in \left\{1, ...,n-1 \right\} | \, ggT(k,n) = 1 \right\} |.[/m]
Weisen Sie nach:
a) [m]p \in \IP \Rightarrow \Phi(p) = p - 1[/m]
b) [m]p,q \in \IP, p \ne q \Rightarrow \Phi(p*q) = (p - 1)(q - 1)[/m]
Als Hinweis ist angegeben, dass man die Aufgaben durch Abzählen der nicht teilerfremden Zahlen lösen / nachweisen kann.
Ich kann Prinzip mit dem RSA Verfahren was anfangen, aber sowas nachzuweisen fällt mir schwer? Kann mir jemand helfen (Tipp geben)? Muss ich hier mit den Aussagenlogik spielen oder die Implikation negieren und einen Fall aufzeigen, für das die Phi Funktion nicht gilt und dann ist die Sache gegessen?
Vielen Dank!
|
|
| |
|
Hallo,
> Die eulersche Phi-Funktion [mm]\Phi: \IN \to \IN[/mm] ist definiert
> über:
> [m]\Phi(n) := | \left\{ k \in \left\{1, ...,n-1 \right\} | ggT(k,n) = 1 \right\} |.[/m]
>
> Weisen Sie nach:
>
> a) [m]p \in \IP \Rightarrow \Phi(p) = p - 1[/m]
> b) [m]p,q \in \IP, p \ne q \Rightarrow \Phi(p*q) = (p - 1)(q - 1)[/m]
>
> [mm]\left\{ \right\}[/mm]
> Als Hinweis ist angegeben, dass man die
> Aufgaben durch Abzählen der nicht teilerfremden Zahlen
> lösen / nachweisen kann.
>
> Ich kann Prinzip mit dem RSA Verfahren was anfangen,
Das hier hat gar nichts mit RSA zu tun.
> aber sowas nachzuweisen fällt mir schwer? Kann mir jemand
> helfen (Tipp geben)? Muss ich hier mit den Aussagenlogik
> spielen oder die Implikation negieren und einen Fall
> aufzeigen, für das die Phi Funktion nicht gilt und dann
> ist die Sache gegessen?
Was soll es bitte heißen, dass eine Funktion nicht gilt?
Das hier ist ein Fall von Probieren geht über studieren. Evtl noch den Hinweis beachten (wobei der nur für die 2. wichtig ist); Nimm die Defintion her und schau dir die entsprechende Situation an, mehr nicht.
>
> Vielen Dank!
|
|
|
| |
|
Def. Inverse in [m]\IZ_m[/m]
Sei [m]a \in \IZ_m[/m]. Gibt es ein b [mm] \in[/mm] [m]\IZ_m[/m] mit [m]ab = 1[/m], so heißt a invertierbar (in [m]\IZ_m[/m]) und b heißt (multiplikative) Inverse von a. Man schreibt: [m]b \equiv a^{-1}[/m]
Def. eulersche Phi-Funktion
Sei m > 1. Dann ist [mm] \Phi(m) [/mm] definiert als die Anzahl der zu m teilerfremden Zahlen zwischen 1 und m-1.
Die Funktion [mm] \Phi [/mm] heißt eulersche Phi-Funktion. (Anders gesagt: [m]\Phi(m)[/m] ist gleich der Anzahl der invertierbaren Elemente in [m]\IZ_m[/m])
Satz:
a) Ist p eine Primzahl, so ist [m]\Phi(p) = p - 1[/m]
b) Sind p und q Primzahlen, so ist [m]\Phi(pq) = (p - 1) (q - 1)[/m]
Soll ich jetzt konkrete Zahlenwerte für p und q einsetzen?
|
|
|
| |
|
> Def. Inverse in [m]\IZ_m[/m]
> Sei [m]a \in \IZ_m[/m]. Gibt es ein b [mm]\in[/mm] [m]\IZ_m[/m] mit [m]ab = 1[/m], so
> heißt a invertierbar (in [m]\IZ_m[/m]) und b heißt
> (multiplikative) Inverse von a. Man schreibt: [m]b \equiv a^{-1}[/m]
>
> Def. eulersche Phi-Funktion
> Sei m > 1. Dann ist [mm]\Phi(m)[/mm] definiert als die Anzahl der
> zu m teilerfremden Zahlen zwischen 1 und m-1.
> Die Funktion [mm]\Phi[/mm] heißt eulersche Phi-Funktion. (Anders
> gesagt: [m]\Phi(m)[/m] ist gleich der Anzahl der invertierbaren
> Elemente in [m]\IZ_m[/m])
>
> Satz:
> a) Ist p eine Primzahl, so ist [m]\Phi(p) = p - 1[/m]
> b) Sind p
> und q Primzahlen, so ist [m]\Phi(pq) = (p - 1) (q - 1)[/m]
>
>
> Soll ich jetzt konkrete Zahlenwerte für p und q einsetzen?
Hi.
Du sollst den Satz beweisen. Wenn $p$ Primzahl ist, besagt a) lediglich, dass alle natürlichen Zahlen $<p$ teilerfremd zu $p$ sind. Schreib noch einen, oder zwei Sätze drum herum und das ist schon der fertige Beweis.
Bei b) fehlt zunächst einmal, dass [mm] $p\not=q$ [/mm] gelten musst. Zeige dann allgemeiner, dass für teilerfremde Zahlen $m,n$ eine Zahl genau dann teilerfremd zu $mn$ ist, wenn sie sowohl zu $m$ als auch zu $n$ teilerfremd ist. Dies zeigt [mm] $\phi(mn)=\phi(m)\phi(n)$ [/mm] für teilerfremde $m,n$. b) ist dann ein Spezialfall.
Liebe Grüße,
UniversellesObjekt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Mo 10.03.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
