Eulersche Funktion und Primfaktorzerlegung |
08.04.2009, 11:21 | Sensi | Auf diesen Beitrag antworten » | ||||
Eulersche Funktion und Primfaktorzerlegung Ich hab noch ein Problem bei einer Aufgabe: Die natürliche Zahl n sei das Produkt zweier Primzahlen p und q. Bekanntlich läßt sich aus p und q leicht phi(n) berechnen. Zeige, dass sich umgekehrt die Zerlegung n= p*q allein anhand der Werte von n und phi(n) bestimmen lässt. Also, wie ich phi(n) aus p und q berechne, ist mir klar. Aber andersherum fehlt mir leider jeglicher Ansatz... Wäre super, wenn mir jemand helfen könnte! Vielen Dank schon mal im Vorraus, viele liebe Grüße, Sensi |
||||||
08.04.2009, 12:01 | Huggy | Auf diesen Beitrag antworten » | ||||
RE: Eulersche Funktion und Primfaktorzerlegung
Wie ist das gemeint? Die Primfaktorzerlegung einer natürlichen Zahl n kann man doch bestimmen, ohne zu kennen. |
||||||
08.04.2009, 16:08 | Elvis | Auf diesen Beitrag antworten » | ||||
Eulersche Funktion und Primzerlegung @Sensi wenn dir klar ist, wie du berechnen kannst, dann schreib's doch bitte mal hin. Damit wäre dein Problem schon fast gelöst. |
||||||
08.04.2009, 20:05 | Sensi | Auf diesen Beitrag antworten » | ||||
RE: Eulersche Funktion und Primzerlegung Zu Elvis: Also für n= p*q ist phi(n)= (p-1)*(q-1) oder nicht? Zu Huggy: Allgemein kann man die PFZ zwar auch so finden, aber das ist ja nicht die Aufgabe und bei großen Zahlen auch recht aufwendig... Jedenfalls vielen Dank schon mal. |
||||||
08.04.2009, 20:43 | Elvis | Auf diesen Beitrag antworten » | ||||
Euler und Primzahlen Ja, genau Das gilt, weil für prim, und weil die Eulersche -Funktion multiplikativ ist. Was macht man üblicherweise mit einem Produkt , in dem Klammern stehen ??? |
||||||
08.04.2009, 20:46 | Huggy | Auf diesen Beitrag antworten » | ||||
RE: Eulersche Funktion und Primzerlegung
Das ist für richtig. Ist dir jetzt klar, wie man dann aus n und p und q berechnen kann?
Auch das ist richtig. Nur braucht man ja für normalerweise die Primfaktorzerlegung von n. @Edit Elvis: Sorry, hat sich mit dir überschnitten. |
||||||
Anzeige | ||||||
|
||||||
08.04.2009, 20:53 | Sensi | Auf diesen Beitrag antworten » | ||||
RE: Euler und Primzahlen Zu Elvis: Also Ausklammern ergebe ja p*q - p - q + 1 Ich seh´s gerade irgendwie nicht... Tut mir echt leid, wenn ich ein bisschen schwerr von Verstand bin... Vielen Dank für eure Geduld! |
||||||
08.04.2009, 20:59 | Elvis | Auf diesen Beitrag antworten » | ||||
Euler Bin noch da, und helfe gern ein bißchen weiter. Man muß schon ziemlich genau hinsehen, und das geht am besten, wenn man Gleichungen schreibt, und nicht nur Terme. Du weißt schon alles, was du brauchst. Tip: Schreibe 1. 2. |
||||||
08.04.2009, 21:03 | Sensi | Auf diesen Beitrag antworten » | ||||
RE: Euler Danke, das ist total nett! Also: 1. n= p*q 2. phi(n)= n - p - q + 1? |
||||||
08.04.2009, 21:06 | Elvis | Auf diesen Beitrag antworten » | ||||
Euler Genial. Das ist es. Jetzt kommt die 100 Millionen Dollar Frage: Wieviele Variable haben wir und wieviele Gleichungen haben wir ? |
||||||
08.04.2009, 21:12 | Elvis | Auf diesen Beitrag antworten » | ||||
euler entschuldigung . mit Variable meine ich Unbekannte |
||||||
08.04.2009, 21:13 | Sensi | Auf diesen Beitrag antworten » | ||||
RE: Euler Hmmh, Zwei Formeln und da n und phi(n) ja bekannt sind zwei Variablen... Also eine Formel nach einer Variablen umstellen und in die andere einsetzen? Etwa p= n/q und dann also phi(n)= n - (n/q) - q + 1 |
||||||
08.04.2009, 21:21 | Elvis | Auf diesen Beitrag antworten » | ||||
Hätte Euler auch nicht besser machen können Ja, das war's dann wohl. Hat Spaß gemacht und ist immer wieder schön, wenn jemand mitdenkt. Der Beweis ist erbracht, denn wir haben gezeigt, daß p und q aus n und phi(n) berechnet werden könen, wenn n=pq ist. Falls du noch ein bißchen weiter rechnen möchtest, kommst du auf eine quadratische Gleichung, deren beide Nullstelle dann die gesuchten Primzahlen sind. Tschüs, bis zum nächsten mal |
||||||
26.06.2022, 18:56 | Clod | Auf diesen Beitrag antworten » | ||||
RE: Hätte Euler auch nicht besser machen können Ich jetzt an einer Aufgabe, die genau das von mir verlangt. Die PFZ von 34081=pxq, wobei phi(34081)=33712 Jedoch komme ich nicht darauf, wie man als nächsten Schritt eine quadratische Funktion hat. |
||||||
26.06.2022, 18:56 | Clod | Auf diesen Beitrag antworten » | ||||
RE: Hätte Euler auch nicht besser machen können Ich jetzt an einer Aufgabe, die genau das von mir verlangt. Die PFZ von 34081=pxq, wobei phi(34081)=33712 Jedoch komme ich nicht darauf, wie man als nächsten Schritt eine quadratische Funktion hat. |
||||||
26.06.2022, 19:08 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Einfach mal zuhören und befolgen: Damit ist , was eingesetzt in die zweite Gleichung ergibt . Jetzt alles nach links gebracht und mit multipliziert gelangt man zu . Für dein Beispiel wäre das dann die Gleichung ... |
||||||
26.06.2022, 20:07 | Leopold | Auf diesen Beitrag antworten » | ||||
Kleine Variante zu HALs Argumentation. Wenn man in rechts ausmultipliziert und durch ersetzt, bekommt man das Gleichungssystem Nach dem Satz von Vieta sind Lösungen der quadratischen Gleichung |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|