Eulersche phi funktion, phi(n)=24 |
24.11.2009, 13:54 | mullrich | Auf diesen Beitrag antworten » | ||
Eulersche phi funktion, phi(n)=24 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! |
||||
24.11.2009, 16:20 | 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 |
||||
25.11.2009, 12:20 | 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? |
||||
25.11.2009, 14:01 | 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. |
||||
25.11.2009, 15:37 | 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. |
||||
25.11.2009, 16:08 | tmo | Auf diesen Beitrag antworten » | ||
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. |
||||
Anzeige | ||||
|
||||
17.12.2017, 12:01 | 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 |
||||
17.12.2017, 12:36 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Das sind offenbar genau die Primzahlen mit der Eigenschaft , was ja angesichts von entscheidend für mögliche Primfaktoren der gesuchten Zahl ist. |
||||
17.12.2017, 12:47 | 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 |
||||
17.12.2017, 13:01 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Kann man was aufschreiben? |
||||
17.12.2017, 13:11 | jaaaa | Auf diesen Beitrag antworten » | ||
phi Funktion die Aufgabe, wenn ich mit 13 anfange, wie soll ich das auf das heft darstellen... |
||||
17.12.2017, 13:15 | 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. |
||||
17.12.2017, 13:17 | jaaaa | Auf diesen Beitrag antworten » | ||
phi Funktion okaaaay |
||||
17.12.2017, 15:22 | jaaaa | Auf diesen Beitrag antworten » | ||
phi Funktion hallo , sorry, für 72 wie funktioniert das kann nicht checken |
||||
17.12.2017, 17:26 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |