Alle m aus N mit Phi(m)=4 bestimmen

01.02.2015, 13:14

fuuman

Auf diesen Beitrag antworten »

Alle m aus N mit Phi(m)=4 bestimmen

Meine Frage:
Bestimmen Sie alle $\begin{eqnarray*} m \in N \end{eqnarray*}$ mit $\begin{eqnarray*} \Phi(m) = 4 \end{eqnarray*}$ .

Meine Ideen:
Ich denke $\begin{eqnarray*} \prod\limits_{k=1}^n p^{k-1} \cdot (p-1) = 4 \end{eqnarray*}$ .
Also muss ich mir überlegen welche Werte nimmt $\begin{eqnarray*} p - 1 \end{eqnarray*}$ in dem Fall an. 1, 2 und 4. Also sind die Primfaktoren 2, 3 und 5. Und an der Stelle hängt es jetzt. Der letzte Schritt zum m fehlt mir.

01.02.2015, 13:21

Captain Kirk

Auf diesen Beitrag antworten »

Jetzt solltest du dir noch das $\begin{eqnarray*} p^k \end{eqnarray*}$ anschauen.

01.02.2015, 13:50

fuuman

Auf diesen Beitrag antworten »

Ich komm nicht wirklich drauf.
Meine Gedanken, die ich mir gerade gemacht habe:
Wenn p-1 1,2 und 4 sind. Dann ist p 2,3 und 5.
Ich dachte grad erst, dass n nicht größer als 2*4 werden darf. Das ist aber Quatsch merke ich gerade.
Ansonsten wäre ich einfach die Exponenten k durchgegangen, ohne dass ich diese Grenze überschreite.
Jetzt weiß ich gar nicht inwiefern ich mir p^k anschauen muss.

Könnte ich noch einen tiefergehenden Tipp haben? smile

smile

01.02.2015, 13:53

Captain Kirk

Auf diesen Beitrag antworten »

Du hast das schlimmste eigentlich schon gemacht.

Du hast jetzt nur noch die Fälle: 2,3,5|m.
Dann ist das hier

Zitat:

Ansonsten wäre ich einfach die Exponenten k durchgegangen, ohne dass ich diese Grenze überschreite.

für die drei Primzahlen genau das richtige Vorgehen.

Danach noch Fälle mit mehr als einem Primfaktor.

01.02.2015, 14:07

fuuman

Auf diesen Beitrag antworten »

Okay. Aber: Bis zu welcher Grenze schaue ich mir k an. k = 1000 macht ja keinen Sinn. Aber warum macht das keinen Sinn? Mir fehlt für mich die formale Begründung? Über welchen Wert darf p^k nicht wachsen?
m kann ja theoretisch erst mal beliebig groß werden.

Sry, aber wo liegt mein Denkfehler? unglücklich

unglücklich

\\Edit: Ich prüfe z.B. für die 2:
m = 2^2 -> phi(m) = 2^1 * 1 = 2
m = 2^3 -> phi(m) = 2^2 * 1 = 4
usw.
Muss ich dann für jedes Ergebnis prüfen ob 4 rauskommt? Und wenn ich Werte über 4 bekomme weiß ich ab jetzt kann nichts mehr kommen?

01.02.2015, 14:13

Captain Kirk

Auf diesen Beitrag antworten »

Die Folge $\begin{eqnarray*} (\varphi(p^k) ) _k \end{eqnarray*}$ ist für jede Primzahl streng monoton wachsend.

Sobald du das erste k gefunden hast $\begin{eqnarray*} \varphi(p^k) \geq 4 \end{eqnarray*}$ bist du mit der Primzahl fertig.

Anzeige

01.02.2015, 14:14

fuuman

Auf diesen Beitrag antworten »

Ja genau. So langsam wird's.
Also finde ich für die 2 nur die 8. Für die 3 und 5 gar keine M's, right?
Und jetzt noch die Fälle falls m aus verschiedenen Primfaktoren besteht, wobei ich nur Kombis mit 2, 3 und 5 betrachten muss.

01.02.2015, 14:17

Captain Kirk

Auf diesen Beitrag antworten »

Die 5 solltest du dir nochmal anschauen.

01.02.2015, 14:20

fuuman

Auf diesen Beitrag antworten »

Achso, ja klar. Für die 5 selbst natürlich passt's. phi(5^1) ist natürlich 4 smile

smile

//edit: Wenn ich die Kombinationen aus 2 Primzahlen betrachte hab ich ja nur 2*3, 2*5 und 3*5. Da kommt mir dann noch die 10 als Lösung hinzu.

Jetzt hab ich 5, 8 und 10.
Muss ich jetzt solange weiter betrachten bis ich bei einer Kombinationsart ( Kombi aus 3 Zahlen, aus 4 Zahlen) nur noch Werte > 4 herausbekomme? Allein bei 3 Primzahlen sind das aber schon einige Varianten..

01.02.2015, 14:33

Captain Kirk

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \varphi (6)=2, \varphi(15)=8 \end{eqnarray*}$

Sind a,b teilerfremd, so ist $\begin{eqnarray*} \varphi (ab)=\varphi(a)\varphi(b) \end{eqnarray*}$ .
Hier heißt das also: Ist $\begin{eqnarray*} p^k|m \end{eqnarray*}$ so ist

Zitat:

\varphi(p^k) |4

,
das schränkt die möglichen Kombinationen ein.

09.02.2015, 17:37

fuuman

Auf diesen Beitrag antworten »

Ich komme mittlerweile auf die Lösungen. Brauche allerdings mE viel zu lange dafür. Ich bräuchte einfach nochmal ein ganz klares Rezept an das ich mich halten kann. So dass ich das dann auf Anfrage nur noch durchgehen muss und fertig. Ich verstehe z.B. nicht "das schränkt die Kombinationen dann ein".

Mein bisheriger Plan für diesen Aufgabentyp:
Aufgrund der Zusammensetzung von phi(n) können nur Primzahlen p als Primfaktoren in Frage kommen, welche folgendes erfüllen: (p-1)|8. (Im Falle von phi(n) = 8).
Das wären dann hier für p-1 1,2 und 4. Für p dann 2,3 und 5. Das sind jetzt zufällig alles Primzahlen. Sollten da mal keine Primzahlen vorkommen, kann ich diese beim weiteren Vorgehen einfach ignorieren, richtig?

Jetzt schaue ich mir für diese p (2,3 und 5) alle möglichen Potenzen an. Wobei ich mit der größten Primzahl beginne. Dann schau ich mir Phi(5^k) an und sehe: 5^(k-1) * 4 ist größer als 8 wenn k > 1 ist. Also kann 5 eigentlich entweder mit dem Exponent 1 oder gar nicht auftreten. Dann schau ich mir die Primzahlen 2 und 3 an. Jetzt weiß ich allerdings nicht mehr genau wie ich vorgehe. Ab da ist es eigentlich unkontrolliertes Testen ohne Struktur. Damit bin ich unzufrieden.

Kann mir jmd helfen?

09.02.2015, 17:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fuuman
Jetzt hab ich 5, 8 und 10.

Was ist mit $\begin{align*} 12 = 2^2\cdot 3 \end{align*}$ ?

09.02.2015, 17:55

fuuman

Auf diesen Beitrag antworten »

Ja, gehört auch dazu, klar. Aber wie komme ich darauf. Also wie ist der Weg.

Ich habe 2,3 und 5.

Dann fange ich mit der 5 an. Wie gehe ich dann vor. Ich weiß ja nicht wie viele Primfaktoren neben der 5 auftreten. Ich habe das Gefühl dass ich ohne wietere Einschränkungen sehr viele Fälle manuell betrachten muss.

09.02.2015, 18:08

HAL 9000

Auf diesen Beitrag antworten »

Zunächst mal die Situation etwas präziser dargestellt: Für $\begin{align*} m=\prod_{i=1}^n p_i^{k_i} \end{align*}$ haben wir $\begin{align*} \varphi(m) = \prod_{i=1}^n p_i^{k_i-1}(p_i-1) \stackrel{!}{=} 4 \end{align*}$ .

Und dann heißt es eben systematisch und exakt vorzugehen.

(a) Ok, fang mit $\begin{align*} p_1=5 \end{align*}$ an: Dann fängt Faktor $\begin{align*} p_1-1=4 \end{align*}$ faktormäßig bereits alles ab, für den zugehörigen Exponenten muss $\begin{align*} k_1=1 \end{align*}$ gelten. Nun gibt es zwei mögliche Unterfälle:

1) Keine weiteren Primfaktoren, d.h. $\begin{align*} m=5 \end{align*}$

2) Für evtl. weitere Primfaktoren verbleibt die Restbedingung

$\begin{align*} \prod_{i=2}^n p_i^{k_i-1}(p_i-1) \stackrel{!}{=} 1 \end{align*}$ .

Das geht offenbar nur für $\begin{align*} p_2=2 \end{align*}$ sowie $\begin{align*} k_2=1 \end{align*}$ , insgesamt dann $\begin{align*} m=5\cdot 2 = 10 \end{align*}$

(b) Untersuchen wir $\begin{align*} p_1=3 \end{align*}$ an: Dann ist $\begin{align*} p_1-1=2 \end{align*}$ , und wegen $\begin{align*} 3\nmid 2 \end{align*}$ muss auch hier für den Exponenten $\begin{align*} k_1=1 \end{align*}$ gelten. Es verbleibt die Restbedingung

$\begin{align*} \prod_{i=2}^n p_i^{k_i-1}(p_i-1) \stackrel{!}{=} 2 \end{align*}$ ,

d.h. hier brauchen wir noch einen weiteren Primfaktor. Das kann nach Lage der Dinge nur noch $\begin{align*} p_2=2 \end{align*}$ sein, wobei $\begin{align*} 2^{k_2-1}\cdot (2-1) = 2 \end{align*}$ gelten muss, das führt zu $\begin{align*} k_2=2 \end{align*}$ , also zu $\begin{align*} m= 3\cdot 2^2 = 12 \end{align*}$ .

(c) Wir haben nur Primfaktor $\begin{align*} p_1=2 \end{align*}$ .... (blablabla) ... $\begin{align*} k_1=3 \end{align*}$ , also $\begin{align*} m=2^3 =8 \end{align*}$ .

09.02.2015, 18:31

fuuman

Auf diesen Beitrag antworten »

Das hat auf jeden Fall weitergeholfen, vielen vielen Dank für die Mühe!

Nur eine Aussage versteh ich nicht: und wegen 3 teilt nicht 2 muss auch hier für den Exponenten k1=1 gelten

09.02.2015, 18:44

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fuuman
Nur eine Aussage versteh ich nicht: und wegen 3 teilt nicht 2 muss auch hier für den Exponenten k1=1 gelten

Für $\begin{align*} k_1\geq 2 \end{align*}$ folgt, dass Primfaktor 3 im Produkt präsent ist - was nicht sein darf.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »