Eigenschaft der < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:28 So 26.06.2011 | | Autor: | clemenum |
| Aufgabe | Man zeige:
[mm] $\forall [/mm] m,n [mm] \in \mathbb{N}:$ $\varphi(m)\varphi(n) [/mm] = [mm] \varphi(mn) \frac{d}{\varphi(d)} [/mm] $ (falls $d=ggT(m,n)$) |
Meine Beweisidee:
Hilfsmittel:
- Multiplikativität der Phi-Funktion (1)
- Eindeutige Primfaktorenzerlegung (2)
- Überlegung: [mm] $\varphi(p^{\alpha}) [/mm] = [mm] p^{\alpha} [/mm] - [mm] p^{\alpha -1 } [/mm] $ (3)
Sei nun für unsere Betrachtungen $d [mm] \in \mathbb{N} \setminus\mathbb{P} [/mm] $ .
(d.h. sei $d = [mm] r_1^{\gamma_1} \ldots r_n^{\gamma_n} [/mm] $ )
Seien [mm] $p_i, q_i, r_i \in \mathbb{P} [/mm] $ [mm] $\forall [/mm] i .$
Wegen (1) und (3) kann ich nun schreiben:
[mm] $\varphi(m) [/mm] = [mm] p_1^{\alpha_1-1} (p_1 [/mm] -1 ) [mm] \ldots p_n ^{\alpha_n-1}(p-1) r_1^{\gamma_1-1}(r_1 [/mm] -1 ) [mm] \ldots r_n^{\gamma_n-1} (r_n [/mm] - 1 ) $
[mm] $\varphi(n) [/mm] = [mm] q_1^{\beta_1-1} (q_1 [/mm] -1 ) [mm] \ldots q_n ^{\beta_n-1}(p-1) r_1^{\gamma_1-1}(r_1 [/mm] -1 ) [mm] \ldots r_n^{\gamma_n-1} (r_n [/mm] - 1 ) $
[mm] $\Rightarrow [/mm] $
[mm] $\varphi(m) \varphi(n) [/mm] = [mm] p_1^{\alpha_1-1}(p_1-1) \ldots p_n^{\alpha_n-1}(p_n-1) q_1^{\beta_1-1}(q_1-1) \ldots q_n^{\beta_n-1 } (q_n [/mm] -1 [mm] )\left((r_1^{\gamma_1-1}(r_1-1)(r_2^{\gamma_2 -1} (r_2- 1) ) \ldots (r_n ^{\gamma_n -1} (r_n-1))\right)^2 [/mm] $
Nun stehe ich aber ein wenig auf der Leitung; ich könnte den rechten Ausdruck mit [mm] $\varphi(d) [/mm] $ multiplizieren, aber, dann steht doch rechts nicht [mm] $\varphi(mn) \cdot [/mm] d $, oder??
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:32 So 26.06.2011 | | Autor: | clemenum |
Also, wenn euch diese Aufgabe zu schwer ist (was ja sein kann, da es sich um eine Eulersche Aufgabe handelt), muss ich mir ein Spezialbiuch über die Phi-Funktion kaufen! 
Die Frage ist nur: Wenn nicht mal ihr das lösen könnt, wie sollen es dann wir Studenten lösen können???
|
|
|
| |
|
Hallo clemenum,
es kann nie schaden, noch ein Fachbuch zu kaufen. Wer weiß, wie lange es die noch gibt...
Dein Weg ist kompliziert und wird schnell unübersichtlich. Verwende lieber eine alternative Schreibweise der Definition der Phi-Funktion:
[mm] \phi(n)=n*\produkt_{p|n}{\left(1-\bruch{1}{p}\right)}
[/mm]
Damit ist die Behauptung leicht und relativ schnell zu zeigen. Da Du um eine Fallunterscheidung [mm] p|d_{} [/mm] bzw. [mm] p\not|d [/mm] wohl nicht herumkommst, bleibt noch etwas Schreibarbeit.
Nicht nur für Studenten.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:46 Di 28.06.2011 | | Autor: | clemenum |
Hallo!
Danke für deine Antwort, lieber Reverend!.
Nun folgender (ähnlicher) Lösungsansatz:
Seit $d = ggT(m,n)$, dann folgt:
$m = a*d$
$n = b*d $ mit
$ggT(a,b)=1 [mm] \Rightarrow \varphi(ab) [/mm] = [mm] \varphi(a)\cdot\varphi(b)$ [/mm] und
$m*n = a*b*d²$
Leider kann man ja nicht davon ausgehen, dass $ab$ und [mm] $d^2$ [/mm] teilerfremd sind (oder irre ich mich??)
Die Primfaktorzerlegung von [mm] $d^2$ [/mm] würde lauter gerade Potenzen von Primzahlen ergeben......
Die Primfaktorzerlegung von [mm] $d^2$ [/mm] würde lauter gerade Potenzen von Primzahlen ergeben, auf die sich die Regel [mm] $\phi(p^n) [/mm] = [mm] p^n [/mm] - [mm] p^{n-1}$ [/mm] anwenden lässt.
Je zwei dieser Primzahlpotenzen sind zueinander teilerfremd, hier gilt also die Produktregel wieder!
Aber hier scheitere ich, da die einzelnen Primfaktoren ja zu unterschiedlichen Potenzen in den ggT einfließen können.
Kann mir jemand in diesem Gedankenstatus helfen?
|
|
|
| |
|
Hallo clemenum,
> Danke für deine Antwort, lieber Reverend!.
Du scheinst Dich trotzdem für einen komplizierteren Weg zu entscheiden.
> Nun folgender (ähnlicher) Lösungsansatz:
>
> Seit [mm]d = ggT(m,n)[/mm], dann folgt:
> [mm]m = a*d[/mm]
> [mm]n = b*d[/mm] mit
> [mm]ggT(a,b)=1 \Rightarrow \varphi(ab) = \varphi(a)\cdot\varphi(b)[/mm]
> und
> [mm]m*n = a*b*d²[/mm]
Die hochgestelle ASCII-² wird vom Formeleditor gänzlich ignoriert. Schreib also lieber d^2 für [mm] d^2.
[/mm]
Also [mm] m*n=a*b*d^2.
[/mm]
> Leider kann man ja nicht davon ausgehen, dass [mm]ab[/mm] und [mm]d^2[/mm]
> teilerfremd sind (oder irre ich mich??)
Nein, davon kann man nicht ausgehen. Sei a=45, b=75, dann ist d=15 und [mm] ab=3*15*5*15=15^3.
[/mm]
> Die Primfaktorzerlegung von [mm]d^2[/mm] würde lauter gerade
> Potenzen von Primzahlen ergeben, auf die sich die Regel
> [mm]\phi(p^n) = p^n - p^{n-1}[/mm] anwenden lässt.
Ja, klar.
> Je zwei dieser Primzahlpotenzen sind zueinander
> teilerfremd, hier gilt also die Produktregel wieder!
> Aber hier scheitere ich, da die einzelnen Primfaktoren ja
> zu unterschiedlichen Potenzen in den ggT einfließen
> können.
Dann lass es doch einfach allgemein formuliert:
[mm] \phi(d^2)=\produkt_{p|d}\left(p_i^{2\alpha_i}-p_i^{2\alpha_i-1}\right),
[/mm]
wobei [mm] d=\produkt_{p|d}p_i^{\alpha_i} [/mm] ist.
> Kann mir jemand in diesem Gedankenstatus helfen?
Bis dahin gehts ja noch. Jetzt kommt aber die Hürde, [mm] \phi(mn) [/mm] zu bestimmen. Dabei gilt immerhin, dass jeder Primfaktor von d entweder in a oder in b enthalten sein kann, oder in beiden nicht. Was heißt das dann für die Faktorisierung von [mm] \phi(mn)?
[/mm]
Grüße
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 00:33 Do 30.06.2011 | | Autor: | clemenum |
Stimmt, der Weg von Reverend ist der schnellere!
Aus der Definition der Euler-Phi-Funktion folgt [mm] $$\varphi(m) [/mm] = [mm] \prod_{p|m} \left(1-\frac{1}{p}\right) \Rightarrow \varphi(mn) [/mm] = [mm] mn\prod_{p|mn}\left(1-\frac{1}{p}\right) [/mm]
[mm] \varphi(m) \Rightarrow \varphi(m)\varphi(n) [/mm] = [mm] m\prod_{p|m} \left(1-\frac{1}{p}\right) n\prod_{p|n}\left(1-\frac{1}{p}\right) [/mm] $$
[mm] $$\Rightarrow \varphi(mn) [/mm] = [mm] \frac{\varphi(m)\varphi(n)}{\prod_{p|ggT(m,n)}\left(1-\frac{1}{p}\right)}.$$ [/mm]
Setzt man nun in die obige Definition ein, so folgt die Behauptung.
Frage: Ist der Beweis lücken- bzw fehlerfrei?
|
|
|
| |
|
Hallo clemenum,
> Stimmt, der Weg von Reverend ist der schnellere!
Sag ich doch... 
Im Prinzip stimmt Dein Beweis, aber er ist an zwei Stellen ein bisschen irreführend, und zuletzt wäre vielleicht noch [mm] \varphi(d) [/mm] hilfreich, um die Behauptung leichter wiederzuerkennen.
> Aus der Definition der Euler-Phi-Funktion folgt
[mm][/mm][mm] \varphi(m)[/mm] = [mm]\prod_{p|m} \left(1-\frac{1}{p}\right) \Rightarrow \varphi(mn)[/mm] = [mm]mn\prod_{p|mn}\left(1-\frac{1}{p}\right)[/mm]
Hier irritiert es eher, dass [mm] \varphi(m) [/mm] bestimmt wird; es ist für den nächsten Schritt ja nicht nötig. Der folgt auch aus der Definition.
> [mm]\varphi(m) \Rightarrow \varphi(m)\varphi(n)[/mm] = [mm]m\prod_{p|m} \left(1-\frac{1}{p}\right) n\prod_{p|n}\left(1-\frac{1}{p}\right)[/mm]
Auch hier: wozu steht da erst [mm] \varphi(m) [/mm] und dann noch der Doppelpfeil?
Es genügt doch, wenn Du in den ersten beiden Schritten (die ich sogar in umgekehrter Reihenfolge schreiben würde, das ist aber egal) eben nach Definition [mm] \varphi(m) \varphi(n) [/mm] sowie [mm] \varphi(mn) [/mm] ausschreibst.
> [mm]\Rightarrow \varphi(mn) = \frac{\varphi(m)\varphi(n)}{\prod_{p|ggT(m,n)}\left(1-\frac{1}{p}\right)}.[/mm]
Das ist richtig und ein guter Zwischenschritt.
Erweitert man jetzt mit d=ggT(m,n), so steht die Behauptung ja ausdrücklich da, wenn man den Nenner im letzten Schritt zu [mm] \varphi(d) [/mm] zusammenfasst.
> Setzt man nun in die obige Definition ein, so folgt die
> Behauptung.
Das ist richtig, aber für eine Übungsaufgabe würde ich das eben auch ausführen, damit mans so richtig überdeutlich sieht.
> Frage: Ist der Beweis lücken- bzw fehlerfrei?
Grüße
reverend
|
|
|
|
