Eulersche Funktion

05.12.2009, 10:53

imag

Eulersche Funktion

Hallo
Habe eine Frage: Es geht um eine Eigenschaft der Eulerschen Funktion $\begin{eqnarray*} \varphi \end{eqnarray*}$ .
Für $\begin{eqnarray*} d,n \in \mathbb N \end{eqnarray*}$ mit d|n gilt: $\begin{eqnarray*} \varphi(d)|\varphi(n) \end{eqnarray*}$
Das will ich irgendwie zeigen. Sieht irgendwie nicht so schwer aus, aber ich habe keine Idee wie ich das anstellen könnte. Kann mir da jemand einen Tipp geben?

05.12.2009, 11:00

Mystic

Auf diesen Beitrag antworten »

RE: Eulersche Funktion
Kennst du die explizite Formel für $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ ?

05.12.2009, 11:13

imag

Auf diesen Beitrag antworten »

RE: Eulersche Funktion
$\begin{eqnarray*} \varphi(n)=|\{1\leq a \leq n| ggT(a,n)=1\}| \end{eqnarray*}$
Ist damit das hier gemeint?

05.12.2009, 11:47

tmo

Auf diesen Beitrag antworten »

Nein, Mystic meinte bestimmt die Formel, mit der man $\begin{eqnarray*} \varphi (n) \end{eqnarray*}$ mit Hilfe der Primfaktorzerlegung von n berechnen kann. Daraus folgt die Aussage nämlich recht schnell.

05.12.2009, 12:34

imag

Auf diesen Beitrag antworten »

Achso. Jetzt weiß ich was gemeint ist.
$\begin{eqnarray*} \varphi(n)=n\prod_{p|n} (1-\frac{1}{p}) \end{eqnarray*}$
Also kann ich dann für $\begin{eqnarray*} \varphi(d)|\varphi(n) \end{eqnarray*}$ schreiben:
$\begin{eqnarray*} d\prod_{p|d} (1-\frac{1}{p})|n\prod_{p|n} (1-\frac{1}{p}) \end{eqnarray*}$ und da gilt d|n hätte ich schon meine Behauptung oder?

05.12.2009, 13:41

Mystic

Auf diesen Beitrag antworten »

Ich nehme an, dass du das Richtige meinst, aber du solltest zumindestens noch darauf hinweisen, dass Primteiler von d auch Primteiler von n sind...

05.12.2009, 13:45

imag

Auf diesen Beitrag antworten »

Ja ok war wirklich nicht gut aufgeschrieben. Aber genau das meinte ich. Danke.

05.12.2009, 16:02

Mystic

Auf diesen Beitrag antworten »

Ich denke, ganz so einfach ist, wie ich selber auch glaubte, ist die Sache dann doch nicht... Meine derzeitige Überlegung geht so, dass ich für jeden positiven Teiler d von n, eine Art "Vervollständigung" durch

$\begin{eqnarray*} \tilde{d}:= \prod_{p|d} p^{\nu_p(n)} \end{eqnarray*}$

definiere, wobei $\begin{eqnarray*} \nu_p(n) \end{eqnarray*}$ die Vielfachheit des Primfaktors p von n ist, mit der p in der Primfaktorzerlegung von n vorkommt... Man muss dann zeigen, dass

$\begin{eqnarray*} \frac {\varphi(n)}{\varphi(d)}= \varphi(\frac n{\tilde{d}}) \frac {\tilde{d}}d \in \mathbb{N} \end{eqnarray*}$

was nicht wirklich schwer ist, aber doch noch eine kleine Überlegung erdordert, die ich dir überlasse...

05.12.2009, 17:23

imag

Auf diesen Beitrag antworten »

Ok. Schade das andere habe ich so gut verstanden. Warum man das hier zeigen muss und daraus die Behauptung folgt verstehe ich nicht so ganz.

06.12.2009, 12:12

Mystic

Auf diesen Beitrag antworten »

Wenn du für einen positiven Teiler d von n den Quotienten

$\begin{eqnarray*} \frac {\varphi(n)}{\varphi(d)} = \frac nd \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$

bildest, dann hast doch das Problem zu erklären, warum das eine natürliche Zahl sein soll... Ich fürchte, wenn du das auf Anhieb und "gut" verstanden hast, wie du schreibst, dann hast du gar nichts verstanden...

06.12.2009, 13:04

imag

Auf diesen Beitrag antworten »

Ok. Ich weiß aber, dass

$\begin{eqnarray*} \frac nd \end{eqnarray*}$ eine natürliche Zahl ist, weil dass ja als Voraussetzung in meiner Aufgabenstellung steht.
Also muss ich noch zeigen, dass das hier:
$\begin{eqnarray*} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$ auch eine natürliche Zahl ist oder? Wofür ich dann das hier:
$\begin{eqnarray*} \tilde{d}:= \prod_{p|d} p^{\nu_p(n)} \end{eqnarray*}$
$\begin{eqnarray*} \frac {\varphi(n)}{\varphi(d)}= \varphi(\frac n{\tilde{d}}) \frac {\tilde{d}}d \in \mathbb{N} \end{eqnarray*}$
benötige?
Habe ich das jetzt vom Prinzip her richtig verstanden?

06.12.2009, 13:35

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von imag
Also muss ich noch zeigen, dass das hier:
$\begin{eqnarray*} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$ auch eine natürliche Zahl ist oder?[...]
Habe ich das jetzt vom Prinzip her richtig verstanden?

$\begin{eqnarray*} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$ soll als Produkt von Zahlen r mit 0<r<1 eine natürliche Zahl sein? verwirrt

Damit läßt sich wohl deine letzte Frage klar mit nein beantworten...

06.12.2009, 13:41

imag

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Wenn du für einen positiven Teiler d von n den Quotienten

$\begin{eqnarray*} \frac {\varphi(n)}{\varphi(d)} = \frac nd \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$

bildest, dann hast doch das Problem zu erklären, warum das eine natürliche Zahl sein soll...

Aber du hattest doch das hier geschrieben. Daraus habe ich das geschlossen! Ich glaub jetzt bin ich ganz verwirrt.

06.12.2009, 13:51

Mystic

Auf diesen Beitrag antworten »

Ist also deiner Meinung nach der Schluss

$\begin{eqnarray*} \frac {12}2 (1 - \frac 12)=3 \in \mathbb N \Rightarrow 1 - \frac 12 \in \mathbb N \end{eqnarray*}$

zulässig? geschockt

06.12.2009, 14:01

imag

Auf diesen Beitrag antworten »

Nein natürlich nicht. Aber ich weiß doch, dass das $\begin{eqnarray*} \frac nd \end{eqnarray*}$ eine natürliche Zahl ist. Und ich soll das Problem erklären, warum $\begin{eqnarray*} \frac {\varphi(n)}{\varphi(d)} = \frac nd \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$ das ein natürliche Zahl ist. Also müsste ich doch zeigen, dass
$\begin{eqnarray*} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$ auch eine natürliche Zahl ist.

06.12.2009, 14:04

therisen

Auf diesen Beitrag antworten »

Sind $\begin{eqnarray*} n=\prod_p p^{\nu_p(n)} \end{eqnarray*}$ bzw. $\begin{eqnarray*} d=\prod_p p^{\nu_p(d)} \end{eqnarray*}$ die kanonischen Primfaktorzerlegungen von n bzw. d, so gilt $\begin{eqnarray*} \nu_p(d)\leq\nu_p(n) \end{eqnarray*}$ für alle p. Es folgt

$\begin{eqnarray*} \varphi(n)=\prod_{p|n}p^{\nu_p(n)-1}(p-1)=\prod_{p|d}p^{\nu_p(n)-1}(p-1)\prod_{p|n\atop{p\not|d}}p^{\nu_p(n)-1}(p-1) = \varphi(d)\prod_{p|d} p^{\nu_p(n)-\nu_p(d)}\prod_{p|n\atop{p\not|d}}p^{\nu_p(n)-1}(p-1) \end{eqnarray*}$ ,

also $\begin{eqnarray*} \varphi(d)|\varphi(n) \end{eqnarray*}$ .

06.12.2009, 14:06

Mystic

Auf diesen Beitrag antworten »

Sorry, aber ich werfe das Handtuch hier... unglücklich

Eigentlich hab ich schon viel mehr zur Lösung gesagt, als nach den Forumsregeln hier gesagt werden dürfte, einen klitzekleinen letzten Rest an Denkarbeit möchte ich dir aber nicht ersparen...

Edit: Aha, wie ich grad sehe, hat therisen dasselbe in etwas anderer Notation nochmals ausgeführt, vielleicht hilft das ja, wenn ich mir's auch nicht vorstellen kann... Wink

06.12.2009, 14:15

imag

Auf diesen Beitrag antworten »

Ich wollte garkeine komplett Lösung. Will das schon selbst verstehen und auch lösen können. Hatte nur Probleme die Tipps zu verstehen und richtig einzuordnen. Ich glaube das wurde irgendwie etwas missverstanden. Aber trotzdem danke für die Hilfe.

06.12.2009, 15:07

Auf diesen Beitrag antworten »

Off-topic: Ich find's lustig (oder immer öfter auch nicht), dass Leute beteuern, sie wollen gar keine Komplettlösungen - und dann doch noch um Tipps oder gar "Ansätze" nachsuchen zu einem Zeitpunkt, wo geschätzte 90-95% der Lösung schon dastehen... Augenzwinkern

06.12.2009, 15:13

Mystic

Auf diesen Beitrag antworten »

Vielleicht doch noch ein erklärender Kommentar von meiner Seite (nachdem therisen eine Komplettlösung hingeschrieben hat, spielt das jetzt auch keine Rolle mehr!)...

Die Ausgangssituation ist die, dass wir für das Produkt

$\begin{eqnarray*} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$

auf der rechten Seite von

$\begin{eqnarray*} \frac {\varphi(n)}{\varphi(d)} = \frac nd \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$

einen "Partner" brauchen, mit dem zusammen es eine natürliche Zahl ergibt, da es von Haus (außer in dem trivialen Fall eines leeren Produkts!) eben keine natürliche Zahl ist, entgegen deiner hartnäckigen anderslautenden Behauptung...

Nun ist aber offensichtlich n/d dieser Partner, wenn die Behauptung, um die es hier geht, überhaupt richtig ist, und man könnte zunächst glauben, dass obiges Produkt zusammen mit n/d als Produkt gerade $\begin{eqnarray*} \varphi(n/d) \end{eqnarray*}$ ergibt... Leider kann aber n/d immer noch Primfaktoren p enthalten, die in der Produktbildung

$\begin{eqnarray*} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \end{eqnarray*}$

gar nicht mehr vorkommen, nämlich dann, wenn

$\begin{eqnarray*} \nu_p(d)<\nu_p(n) \end{eqnarray*}$

ist... Was liegt also näher, als das "Splitting"

$\begin{eqnarray*} \frac nd=\frac n{\tilde d} \frac {\tilde d} d \end{eqnarray*}$

vorzunehmen, wobei wie oben angegeben

$\begin{eqnarray*} \tilde d = \prod_{p|d} p^{\nu_p(n)} \end{eqnarray*}$

ist, da wir dann in $\begin{eqnarray*} \frac n {\tilde d} \end{eqnarray*}$ offensichtlich diesen Partner gefunden haben, denn nun gilt wirklich

$\begin{eqnarray*} \phi (\frac n {\tilde d}) = \frac n {\tilde d} \prod_{\stackrel{p \mid n}{p \nmid d}} (1-\frac 1p) \in \mathbb N \end{eqnarray*}$

und damit auch schlussendlich

$\begin{eqnarray*} \varphi(n) =\varphi(d) (\tilde d/d) \varphi(n/ \tilde d) \end{eqnarray*}$

wobei ich die 3 Faktoren rechts nun in der gleichen Reihenfolge wie therisen angeschrieben habe, damit du eine bessere Vergleichsmöglichkeit hast...

@Arthur

In diesem Punkt kann ich dir nur aus ganzem Herzen beipflichten, wenngleich ich mir nach allen Kommentaren des TE zwischendurch nicht sicher bin, ob selbst eine Komplettlösung in diesem Fall was nützt... Augenzwinkern

07.12.2009, 19:26

imag

Auf diesen Beitrag antworten »

Vielen Dank. Habe es jetzt verstanden. Und nochmal ich bin wirklich dankbar für jeden Tipp und versuche damit meine Aufgabe zu lösen. Ich habe auch herausgefunden, woran es lag das mir hier das Verständnis der Tipps solche Probleme bereitet hat. Ich hatte nicht erkannt dass das hier ein p teilt d nicht ist.
$\begin{eqnarray*} p \nmid d \end{eqnarray*}$
In dieser Größe hier wird es jetzt deutlich aber ich hatte es einfach übersehen.
Tut mir Leid. Deswegen machte das für mich alles keinen Sinn und hatte irgendwann total den Durchblick verloren. Als ich das erkannt hatte wurde mir schnell einiges klar.
Deswegen hatte ich auch scheinbar nicht erkannt, dass (wie Arthur Dent sagt) schon der größte Teil der Aufgabe die ganze Zeit hier stand.

Neue Frage »

Antworten »

Eulersche Funktion

Verwandte Themen