Aufgabe zur Phi-Funktion

02.05.2012, 13:59

lilithilli1210

Aufgabe zur Phi-Funktion

Hi,

ich habe folgende Aufgabe:

Welche n aus N erfüllen: phi(n)=n/3

Die Phi-Funktion gibt ja an, wieviele (positive) teilerfremde Zahlen vor der Zahl n liegen.

Also zB. phi(6)=2

Es können ja nur Vielfach von 3 in Frage kommen, da phi(n) aus N sein muss.

Wie kann ich weiter vorgehen, um diese Aufgabe zu lösen?

LG lilithilli smile

02.05.2012, 14:09

HAL 9000

Auf diesen Beitrag antworten »

Es gibt ja verschiedene Darstellungen von $\begin{eqnarray*} \varphi \end{eqnarray*}$ , am besten zugeschnitten auf die vorliegende Aufgabe scheint mir

$\begin{eqnarray*} \varphi(n) = n\cdot \prod\limits_{p \mid n} \left( 1-\frac{1}{p} \right) \end{eqnarray*}$

zu sein...

02.05.2012, 14:23

lilithilli1210

Auf diesen Beitrag antworten »

wie ist das produkt zu lesen...?
kannst du mir eine beispielaufgabe dazu aufschreiben?

LG

02.05.2012, 14:49

HAL 9000

Auf diesen Beitrag antworten »

Das Produkt läuft über alle Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ , die Teiler von $\begin{eqnarray*} n \end{eqnarray*}$ sind - das soll das Kürzel $\begin{eqnarray*} p\mid n \end{eqnarray*}$ bedeuten.

02.05.2012, 14:57

lilithilli1210

Auf diesen Beitrag antworten »

ok, aber wenn eine primzahl zweimal in der primfaktorzerlegung vorkommt, dann zieht man sie nur einmal ab oder?

LG

02.05.2012, 14:59

HAL 9000

Auf diesen Beitrag antworten »

Ja natürlich. Welche Selbstverständlichkeiten muss ich denn da noch bestätigen?

P.S.: Und "abgezogen" wird da nix, sondern multipliziert.

02.05.2012, 15:26

lilithilli1210

Auf diesen Beitrag antworten »

sorry, ich wollte nur sichergehen.

Ich verstehe aber leider auch nicht, wie mich diese Formel bei der Aufgabe weiterbringt.
Ich müsste ja hier wieder zeigen, dass 3 n teilt...

LG

02.05.2012, 15:34

HAL 9000

Auf diesen Beitrag antworten »

Für die $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} \varphi(n)=\frac{n}{3} \end{eqnarray*}$ bedeutet diese Formel

$\begin{eqnarray*} \prod\limits_{p \mid n} \left( 1-\frac{1}{p} \right) = \frac{1}{3} \end{eqnarray*}$

oder etwas anders geschrieben

$\begin{eqnarray*} \prod\limits_{p \mid n} \frac{p-1}{p} = \frac{1}{3} \end{eqnarray*}$ .

Jetzt kann man sich als nächstes folgendes überlegen: Ist $\begin{eqnarray*} q \end{eqnarray*}$ der größte Primteiler von $\begin{eqnarray*} n \end{eqnarray*}$ , sowie $\begin{eqnarray*} \frac{u}{v}=\prod\limits_{p \mid n} \frac{p-1}{p} \end{eqnarray*}$ mit teilerfremden $\begin{eqnarray*} u,v \end{eqnarray*}$ , dann muss $\begin{eqnarray*} q \mid v \end{eqnarray*}$ gelten. Warum ist das so? Weil dieses $\begin{eqnarray*} q \end{eqnarray*}$ im Nenner des "letzten" Faktors $\begin{eqnarray*} \frac{q-1}{q} \end{eqnarray*}$ nicht als Faktor im Zähler dieses oder evtl. vorangegangener Faktoren enthalten sein kann und folglich auch nicht "weggekürzt" werden kann!

Wenn du das verstanden hast, sollte der Rest der Aufgabe ein Klacks sein.

02.05.2012, 20:20

lilithilli1210

Auf diesen Beitrag antworten »

ok vielen Dank der Groschen ist gefallen Freude

Es gilt also für alle n aus N, die eine Primfaktorzerlegung von
$\begin{eqnarray*} 2^i* 3^j \end{eqnarray*}$ haben mit $\begin{eqnarray*} i, j \in \mathbb N \end{eqnarray*}$

weil enthielte die Zahl einen größeren Primfaktor als 3, dann würde sich dieser aus dem Nenner nicht wegkürzen.
Und enthält die Zahl den Primfaktor 3, muss sie auch den Primfaktor 2 enthalten, bzw. sich in diese zerlegen lassen, da dann die 1/2 die 2/3 zu 1/3 kürzen.

Ich habe das ganze etwas schöner formuliert Augenzwinkern

Vielen Dank für die schnelle Hilfe Freude

LG lilithilli smile

02.05.2012, 20:25

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von lilithilli1210
Es gilt also für alle n aus N, die eine Primfaktorzerlegung von
$\begin{eqnarray*} 2^i* 3^j \end{eqnarray*}$ haben mit $\begin{eqnarray*} i, j \in \mathbb N \end{eqnarray*}$

Richtig, sofern bei dir $\begin{eqnarray*} \mathbb N \end{eqnarray*}$ die natürlichen Zahlen ohne Null bedeutet (da gibt es ja manchmal abweichende Auffassungen Augenzwinkern

02.05.2012, 21:06

lilithilli1210

Auf diesen Beitrag antworten »

ja wir haben N immer definiert ab 1.

LG

Neue Frage »

Antworten »

Aufgabe zur Phi-Funktion

Verwandte Themen