Aufgabe zur Eulerschen Phi-Funktion

16.01.2013, 19:30

Alaster

Aufgabe zur Eulerschen Phi-Funktion

Hallo zusammen,
ich beschäftige mich zur Zeit mit folgender Aufgabe, bei der ich nicht so ganz weiterkomme:

Bestimmen Sie alle natürlichen Zahlen $\begin{eqnarray*} n \in 11\mathbb Z \end{eqnarray*}$ mit $\begin{eqnarray*} \varphi(n) = 60 \end{eqnarray*}$ , wobei $\begin{eqnarray*} \varphi \end{eqnarray*}$ die Eulersche Phi-Funktion bezeichnet.

Meine Ideen:
Wir definieren
$\begin{eqnarray*} M := \{n \in \mathbb N \colon \varphi(n) = 60 \land \exists z \in \mathbb N \colon n = 11z \} \end{eqnarray*}$ .
Ziel ist es also, die Elemente dieser Menge zu bestimmen. Nun habe ich die Behauptung aufgestellt, dass
$\begin{eqnarray*} M = \{77, 99, 154, 198\} =: L \end{eqnarray*}$ .
Um dies zu beweisen, muss ich ja beide Inklusionen zeigen. Die Inklusion $\begin{eqnarray*} M \supseteq L \end{eqnarray*}$ habe ich einfach durch Nachrechnen für jedes der vier Elemente schnell gezeigt. Die Inklusion $\begin{eqnarray*} M \subseteq L \end{eqnarray*}$ macht mir allerdings Probleme: Ich müsste hier unter anderem zeigen, dass, wenn $\begin{eqnarray*} n \in M \end{eqnarray*}$ , folgt, dass $\begin{eqnarray*} \operatorname{ggT}(11,z) = 1 \end{eqnarray*}$ , also dass $\begin{eqnarray*} 11 \end{eqnarray*}$ und $\begin{eqnarray*} z \end{eqnarray*}$ teilerfremd sind. Geht dies überhaupt? Und wenn ja, wie zeige ich das? Ich wollte die Teilerfremdheit voraussetzen, damit ich die Multiplikativität von $\begin{eqnarray*} \varphi \end{eqnarray*}$ benutzen kann, denn so würde folgen:
$\begin{eqnarray*} 60 = \varphi(n) = \varphi(11z) = \varphi(11)\varphi(z) = 10\varphi(z) \end{eqnarray*}$ .
Umstellen ergäbe $\begin{eqnarray*} \varphi(z) = 6 \end{eqnarray*}$ und das ist hoffentlich für genau die Elemente in $\begin{eqnarray*} L \end{eqnarray*}$ erfüllt.

Vielen Dank schonmal,
Alaster.

16.01.2013, 19:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Alaster
Die Inklusion $\begin{eqnarray*} M \subseteq L \end{eqnarray*}$ macht mir allerdings Probleme: Ich müsste hier unter anderem zeigen, dass, wenn $\begin{eqnarray*} n \in M \end{eqnarray*}$ , folgt, dass $\begin{eqnarray*} \operatorname{ggT}(11,z) = 1 \end{eqnarray*}$ , also dass $\begin{eqnarray*} 11 \end{eqnarray*}$ und $\begin{eqnarray*} z \end{eqnarray*}$ teilerfremd sind. Geht dies überhaupt? Und wenn ja, wie zeige ich das?

Mach doch gleich den allgemeineren Ansatz $\begin{eqnarray*} n=11^tz \end{eqnarray*}$ mit $\begin{eqnarray*} t\geq 1 \end{eqnarray*}$ und $\begin{eqnarray*} \operatorname{ggT}(z,11)=1 \end{eqnarray*}$ , dann ist

$\begin{eqnarray*} \varphi(n) = \varphi(11^t)\cdot \varphi(z) = 10\cdot 11^{t-1}\cdot \varphi(z) \end{eqnarray*}$ .

Im Fall $\begin{eqnarray*} t>1 \end{eqnarray*}$ wäre dann aber $\begin{eqnarray*} 11 \mid \varphi(n) \end{eqnarray*}$ , was auf den Zielwert 60 nicht zutrifft. Ergo muss $\begin{eqnarray*} t=1 \end{eqnarray*}$ gelten.

16.01.2013, 19:42

Alaster

Auf diesen Beitrag antworten »

Tausend Dank!!

16.01.2013, 20:12

Alaster

Auf diesen Beitrag antworten »

Eine Frage noch: Du forderst ja bei deinem Ansatz $\begin{eqnarray*} \operatorname{ggT}(z,11) = 1 \end{eqnarray*}$ . Daraus folgt natürlich $\begin{eqnarray*} \operatorname{ggT}(z,11^t) = 1 \end{eqnarray*}$ und man kann die Multiplikativtät benutzen. Aber warum dürfen wir das voraussetzen? Ich dachte, man muss die Teilerfremdheit von z und 11 daraus folgern, dass n in M ist. Oder gilt auch die Rückrichtung? Dann wäre es ja äquivalent und egal, was gefordert wird.

Edit: Das soll heißen, ich würde es verstehen, wenn man $\begin{eqnarray*} \operatorname{ggT}(11^t,z) = 1 \end{eqnarray*}$ fordern würde.

Edit 2: Also ich verstehe es wie folgt:
Du nimmst deinen Ansatz und setzt voraus, dass 11 und z teilerfremd sind. Dann folgt auch, dass 11^t und z teilerfremd sind und man kann die Multiplikativität benutzen.

Angenommen, 11 und z wären NICHT teilerfremd, dann wäre t echt größer als 1.
Mein Verständnisproblem: Dann kann man doch auch nicht mehr folgern, dass 11^t und z teilerfremd sind, und die Multiplikativität nicht benutzen. Das heißt, man kann nicht folgern, dass $\begin{eqnarray*} 11 \mid \varphi(n) \end{eqnarray*}$ , oder?

16.01.2013, 20:37

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Alaster
Mein Verständnisproblem: Dann kann man doch auch nicht mehr folgern, dass 11^t und z teilerfremd sind

Das kann man o.B.d.A. immer voraussetzen, denn solange 11|z gilt, kann man ja einfach t um 1 erhöhen und gleichzeitg z durch z/11 ersetzen...

16.01.2013, 21:15

HAL 9000

Auf diesen Beitrag antworten »

@Alaster

Interessant, was für seltsame Gedankenrunden du so drehst...

Im Ansatz $\begin{eqnarray*} n=11^tz \end{eqnarray*}$ soll $\begin{eqnarray*} t \end{eqnarray*}$ selbstverständlich maximal gewählt werden, d.h. das ist dasjenige $\begin{eqnarray*} t \end{eqnarray*}$ mit $\begin{eqnarray*} 11^t \mid n \end{eqnarray*}$ und $\begin{eqnarray*} 11^{t+1} \nmid n \end{eqnarray*}$ . Oder mit der Primfaktorzerlegung von $\begin{eqnarray*} n \end{eqnarray*}$ ausgedrückt: $\begin{eqnarray*} 11^t \end{eqnarray*}$ ist gerade die 11er-Potenz aus dieser Primfaktorzerlegung. (Nach Voraussetzung $\begin{eqnarray*} n\in 11\mathbb{Z} \end{eqnarray*}$ ist nun bei dir $\begin{eqnarray*} t\geq 1 \end{eqnarray*}$ gewährleistet.) Dann ist von Haus aus $\begin{eqnarray*} \operatorname{ggT}(11^t,z)=1 \end{eqnarray*}$ erfüllt. Und dass

$\begin{eqnarray*} \operatorname{ggT}(p^t,z)=1\;\mbox{für ein}\;t\geq 1 \quad\Longleftrightarrow\quad \operatorname{ggT}(p,z)=1 \end{eqnarray*}$

für alle ganzen Zahlen $\begin{eqnarray*} z \end{eqnarray*}$ und Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ gilt, überlegst du dir mal bitte selbst.

16.01.2013, 22:24

Alaster

Auf diesen Beitrag antworten »

Vielen Dank, das hat alles geklärt. Eigentlich alles sehr logisch, ich hab echt lange da rumgeeiert... man kann auch zu viel denken.

Ich habe jetzt dann noch um den Beweis abzuschließen, solange Möglichkeiten für $\begin{eqnarray*} z \end{eqnarray*}$ aufgeschrieben bis ich vier Stück, die auf $\begin{eqnarray*} \varphi(z) = 6 \end{eqnarray*}$ passen, gefunden habe. Darüber habe ich dann natürlich vier Möglichkeiten (genau die Elemente der Menge $\begin{eqnarray*} L \end{eqnarray*}$ ) für $\begin{eqnarray*} n \end{eqnarray*}$ erhalten. Da $\begin{eqnarray*} n \end{eqnarray*}$ beliebig war und die Menge $\begin{eqnarray*} L \end{eqnarray*}$ nur vier Elemente hat, gilt auch die Inklusion $\begin{eqnarray*} M \subseteq L \end{eqnarray*}$ .
Hätte ich überhaupt alle vier Möglichkeiten raussuchen müssen oder hätte auch eine gereicht für das Zeigen der Inklusion?

Sorry für die vielleicht etwas dumme Frage...

Neue Frage »

Antworten »

Aufgabe zur Eulerschen Phi-Funktion

Verwandte Themen