Eulersche phi funktion, phi(n)=24

Neue Frage »

mullrich Auf diesen Beitrag antworten »
Eulersche phi funktion, phi(n)=24
Hallo,

ich habe 2 Fragen zur Eulerschen Phi Funktion. Zunächst soll ich alle Zahlen n bestimmen, für die gilt:



Hierzu habe ich mir zunächst die Primfaktorzerlegung von 24 angeschaut:



Für ist

Eine Lösung wäre demnach denn und

Ebenso erhalte ich die Lösung
Dieses Suchen nach Lösungen kann aber wohl kaum der effektivste Weg sein, um alle Lösungen zu erhalten oder?

2. Frage:

Ich soll zeigen, dass es nur endlich viele gibt mit

Also

Mein Ansatz:

hier komme ich allerdings auch nicht weiter. Wäre nett, wenn ihr mir auf die Sprünge helfen könntet! Danke!
tmo Auf diesen Beitrag antworten »

Für beide Aufgaben kannst du die Formel



benutzen.

Bei der 1. Aufgabe musst du dir überlegen, welche Werte (p-1) alle annehmen kann, damit am Ende 24 rauskommen kann.


Zur 2. Aufgabe:

Betrachte mal die Primfaktorzerlegung

Zeige: Aus folgt:

1.

2.

Daraus folgt z.b. direkt die sehr grobe (aber zum Ziel führende) Abschätzung
mullrich Auf diesen Beitrag antworten »

zu 1.

ok, also da das Produkt ja gleich 24 sein soll, muss (p-1) ein Teiler von 24 sein. Demnach ist
Wenn ich jetzt ein p fest wähle, z.B. , sagt mir die Formel, dass mein zweites sein muss. Demnach ist

Wenn ich aber wähle wird das ganze komplizierter, da 2 in verschiedenen Potenzen auftreten kann.

Beispiel:



die letzten Faktoren ergeben 2, also sollten die ersten Faktoren 12 ergeben. Meine zweite Primzahl könnte ich nun wählen. Dann ergibt sich für das ganze Produkt: . Demnach ist
ich kann aber auch die benötigte 12 anders darstellen, indem ich betrachte:
, demnach wäre

Sollte ich so vorgehen, um weitere Lösungen zu erhalten?
AD Auf diesen Beitrag antworten »

Ja, das sieht alles schon mal gar nicht schlecht aus. Du solltest vielleicht nur noch versuchen, die Systematik des Vorgehens etwas "strenger" zu gestalten, damit dir auch wirklich keine Lösung durch die Lappen geht.


Eine Möglichkeit dazu: Ausgehend von für teilerfremde arbeitest du dich von den größtmöglichen Primfaktoren langsam nach unten:


1.Angefangen mit , natürlich nur in erster Potenz. Also mit ist dann , mithin . Für den nächsten Primfaktor via gibt es zwei Möglichkeiten:

a) mit . Es verbleibt mit den beiden Möglichkeiten (führt zu ) und (führt zu )

b) mit , führt zu .


2.Nächste Möglichkeit , also mit . Hier gibt es dann sogar drei Möglichkeiten wie es via weiter geht:

a) mit . Es verbleibt ...

b) mit . Es verbleibt ...

b) mit , führt zu .


3.Nächste Möglichkeit , also mit UND alle Primfaktoren von sind kleiner als 5 ...


Zu Kontrolle: Wenn du am Ende alles zusammengefasst die Zahlen 35, 39, 45, 52, 56, 70, 72, 78, 84, 90 dastehen hast, dann hast du keine vergessen. Augenzwinkern
mullrich Auf diesen Beitrag antworten »

Ok, die erste Aufgabe bekomme ich so hin.

Die zweite habe ich noch nicht so ganz durchblickt. Die erste Abschätzung ist ok. Die zweite werde ich wohl auch hinbekommen.

und dann wird n durch seine größte Primzahl in der Primfaktorzerlegung, die maximal hoch irgendwas abgeschätzt. Ist das Prinzip, dass ich jeden Primfaktor von durch seinen potenziell größten, also durch nach oben abschätze? Habe ich denn Primfaktoren in der Primfaktorzerlegung von ?

P.S. Habe jetzt nur kurz drübergeguckt. Kann mich also auch total vertun. Habe erst heute abend Zeit mir das Ganze noch mal genauer anzugucken.
tmo Auf diesen Beitrag antworten »

Zitat:
Original von mullrich
und dann wird n durch seine größte Primzahl in der Primfaktorzerlegung, die maximal hoch irgendwas abgeschätzt. Ist das Prinzip, dass ich jeden Primfaktor von durch seinen potenziell größten, also durch nach oben abschätze? Habe ich denn Primfaktoren in der Primfaktorzerlegung von ?


Schau mal. Jeder Primfaktor von n tritt höchstens mit der Potenz M auf.
Wenn also das Produkt aller Primfaktoren von n z.b. N ist, so ist

Nun ist der größte Primfaktor nicht größer als .
Also ist das Produkt aller Primfaktoren von n sicher nicht größer als , denn wenn der größte Primfaktor t+1 ist, kann es auch nicht mehr als t+1 Primfaktoren geben.

Insgesamt folgt die erwähnte Abschätzung. Wie gesagt: Die ist sehr grob, aber mehr ist ja auch gar nicht verlangt.
 
 
jaaaa Auf diesen Beitrag antworten »
phi Funktion
hallo, kannst du bitte erklären: wo hast du 2, 3, 5, 7, 13 bekommen
ich muss so welche aufgabe lösen, aber ich checke irgendwie nicht
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von jaaaa
hallo, kannst du bitte erklären: wo hast du 2, 3, 5, 7, 13 bekommen

Das sind offenbar genau die Primzahlen mit der Eigenschaft , was ja angesichts von entscheidend für mögliche Primfaktoren der gesuchten Zahl ist.
jaaaa Auf diesen Beitrag antworten »
phi Funktion
ja, dankeschön, ich hatte gecheckt.

sorry, das ist vielleicht dumme Frage: aber wie kann man das aufschreiben? z.B bei p1 = 13
HAL 9000 Auf diesen Beitrag antworten »

Kann man was aufschreiben? Erstaunt1
jaaaa Auf diesen Beitrag antworten »
phi Funktion
die Aufgabe, wenn ich mit 13 anfange, wie soll ich das auf das heft darstellen... Hammer
HAL 9000 Auf diesen Beitrag antworten »

Wie gerade festgestellt, können die gesuchten Zahlen nur die Primfaktoren 2,3,5,7,13 enthalten. Und im Lichte dessen steht doch oben schon ein geeigneter "Aufschrieb". Den kannst du natürlich noch etwas ausschmücken, wenn dir das eine oder andere nicht ausreichend genug erklärt ist.
jaaaa Auf diesen Beitrag antworten »
phi Funktion
okaaaay Lesen2
jaaaa Auf diesen Beitrag antworten »
phi Funktion
hallo ,
sorry, für 72 wie funktioniert das Hammer kann nicht checken
HAL 9000 Auf diesen Beitrag antworten »

Zunächst mal startet man wie oben: Welche erfüllen erstmal ?

Das sind . Und dann geht's wieder in die Fallunterscheidung.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »