Eulers Phi Funktion p|n

20.06.2013, 14:56

steviehawk

Eulers Phi Funktion p|n

Meine Frage:
Hallo Leute, ich brauche schnell Hilfe!

Es ist zu zeigen: $\begin{eqnarray*} p|n \end{eqnarray*}$ wobei $\begin{eqnarray*} p \end{eqnarray*}$ prim so gilt: $\begin{eqnarray*} \phi(pn) = p \phi(n) \end{eqnarray*}$

$\begin{eqnarray*} \phi \end{eqnarray*}$ ist Eulersphifunktion

Meine Ideen:
Ich weiß, dass für teilerfremde Zahlen die Funktion multiplikativ ist.

20.06.2013, 15:06

Mystic

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n
Ok, ich schreib dir mal die Formel für $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ auf, wobei $\begin{eqnarray*} \nu_p \end{eqnarray*}$ die Vielfachheit eines Primfaktors p von n bezeichnet:

$\begin{eqnarray*} \varphi(n)=\prod_{p|n}(p-1)p^{\nu_p-1} \end{eqnarray*}$
Du schreibst darunter dann die ensprechende Formel für $\begin{eqnarray*} \varphi(pn) \end{eqnarray*}$ für einen Primfaktor p von n und überprüfst dann, ob die behauptete Gleichheit gilt...

20.06.2013, 15:13

steviehawk

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n
Ist dann:

$\begin{eqnarray*} \varphi(pn)=\prod_{p|pn}(p-1)p^{\nu_p-1} \end{eqnarray*}$ ??

20.06.2013, 15:28

Mystic

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n
Ist zwar (erwartungsgemäß) total falsch, doch ich habe daran zumindestens Teilschuld, indem ich die Bezeichnungen vielleicht nicht optimal für diese Aufgabe gewählt habe...

Also dann nochmals: Sei

$\begin{eqnarray*} n=\prod_{i=1}^r p_i^{\nu_i} \end{eqnarray*}$

die Primfaktorzerlegung von n und sei p ein Primfaktor von n, wobei wir o.B.d.A. $\begin{eqnarray*} p=p_1 \end{eqnarray*}$ annehmen können... Die Formel für $\begin{eqnarray*} \varphi(n) \end{eqnarray*}$ ist dann

$\begin{eqnarray*} \varphi(n)=\prod_{i=1}^r (p_i-1)p_i^{\nu_i-1} \end{eqnarray*}$

Also nochmals jetzt die Frage: Wie schaut dann die Primfaktorzerlegung von $\begin{eqnarray*} p_1n \end{eqnarray*}$ und daher die Formel für $\begin{eqnarray*} \varphi(p_1n) \end{eqnarray*}$ aus?

21.06.2013, 08:56

steviehawk

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n
das ich Annehmen kann, dass mindestens eines der $\begin{eqnarray*} p_i \end{eqnarray*}$ gleich meinem $\begin{eqnarray*} p \end{eqnarray*}$ ist, liegt schon daran, dass $\begin{eqnarray*} p | n \end{eqnarray*}$ ist oder?

Also ich habe bis jetzt:

$\begin{eqnarray*} p_1n = p_1 \cdot \prod_{i=1}^{r}(p_i)^{\nu_i} = p_1^{\nu_1+1} \cdot \prod_{i=2}^{r}(p_i)^{\nu_i} \end{eqnarray*}$

und damit:

$\begin{eqnarray*} \varphi(p_1n) = \varphi(p_1^{\nu_1+1} \cdot \prod_{i=2}^{r}(p_i)^{\nu_i} ) = \varphi(p_1^{\nu_1+1}) \cdot \varphi ( \prod_{i=2}^{r}(p_i)^{\nu_i} ) = \varphi(p_1^{\nu_1+1} ) \cdot \prod_{i=2}^{r}(p_i-1)(p_i)^{\nu_i} \end{eqnarray*}$

jetzt kann ich für den ersten Faktor die Formel für Primzahlpotenzen verwenden:

$\begin{eqnarray*} \varphi(p_1^{\nu_1+1}) = p_1^{\nu_1}(p_1-1) \end{eqnarray*}$

also:

$\begin{eqnarray*} p_1^{\nu_1} (p_1-1)\cdot \prod_{i=2}^{r}(p_i-1)(p_i)^{\nu_i} = p_1 p_1^{\nu_1-1} (p_1-1)\cdot \prod_{i=2}^{r}(p_i-1)(p_i)^{\nu_i} = p_1 \cdot \prod_{i=1}^{r}(p_i-1)(p_i)^{\nu_i} = p_1 \cdot \varphi(n) \end{eqnarray*}$

passt das?

21.06.2013, 09:17

Mystic

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n

Zitat:

Original von steviehawk
das ich Annehmen kann, dass mindestens eines der $\begin{eqnarray*} p_i \end{eqnarray*}$ gleich meinem $\begin{eqnarray*} p \end{eqnarray*}$ ist, liegt schon daran, dass $\begin{eqnarray*} p | n \end{eqnarray*}$ ist oder?

Zitat:

Original von steviehawk
$\begin{eqnarray*} p_1^{\nu_1} (p_1-1)\cdot \prod_{i=2}^{r}(p_i)^{\nu_i} = (p_1-1)\cdot \prod_{i=1}^{r}(p_i)^{\nu_i} = (p_1-1) \varphi(n) = p_1 \varphi(n) - \varphi(n) \end{eqnarray*}$

irgendwo muss ich dann wohl noch einen Fehler haben. Ich hoffe jetzt ist es etwas richtiger.

Du hast da schon mal richtig angefangen, nur die oben zitierte Zeile gefällt mir so gar nicht... Sie muss natürlich lauten:

$\begin{eqnarray*} \varphi(p_1n)= p_1^{\nu_1} (p_1-1)\cdot \prod_{i=2}^{r} (p_i-1)p_i^{\nu_i-1} = p_1\cdot \prod_{i=1}^{r}(p_i-1)p_i^{\nu_i-1} = p_1 \varphi(n) \end{eqnarray*}$

Außerdem hast du in deinen Formel für die $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion vorher ziemlich konsequent die Hochzahl $\begin{eqnarray*} \nu_i \end{eqnarray*}$ stat $\begin{eqnarray*} \nu_i-1 \end{eqnarray*}$ verwendet...

21.06.2013, 14:54

steviehawk

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n
alles klar Danke, in meinem Edit passt es ja dann..

Ich soll jetzt noch zeigen, dass $\begin{eqnarray*} p \nmid n \Rightarrow \varphi(pn) = (p-1)\varphi(n) \end{eqnarray*}$

Ich dachte jetzt ich könnte direkt: $\begin{eqnarray*} \varphi(pn) = \varphi(p)\varphi(n) = (p-1)\varphi(n) \end{eqnarray*}$

schreiben, denn da $\begin{eqnarray*} p - prim \end{eqnarray*}$ folgt aus: $\begin{eqnarray*} p \nmid n \end{eqnarray*}$ sofort, dass $\begin{eqnarray*} p,n \end{eqnarray*}$ teilerfremd sind, also kann ich die Multiplikativität verwenden.

passt das?

21.06.2013, 15:26

Mystic

Auf diesen Beitrag antworten »

RE: Eulers Phi Funktion p|n
Ja, das stimmt so... Freude

Neue Frage »

Antworten »

Eulers Phi Funktion p|n

Verwandte Themen