Eulersche Funktion und Primfaktorzerlegung

Neue Frage »

Sensi Auf diesen Beitrag antworten »
Eulersche Funktion und Primfaktorzerlegung
Hi,
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
Huggy Auf diesen Beitrag antworten »
RE: Eulersche Funktion und Primfaktorzerlegung
Zitat:
Original von Sensi
Zeige, dass sich umgekehrt die Zerlegung n= p*q allein anhand der Werte
von n und phi(n) bestimmen lässt.

Wie ist das gemeint?
Die Primfaktorzerlegung einer natürlichen Zahl n kann man doch bestimmen, ohne zu kennen.
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. smile
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.
Elvis Auf diesen Beitrag antworten »
Euler und Primzahlen
Ja, genau smile Das gilt, weil für prim, und weil die Eulersche -Funktion multiplikativ ist.
Was macht man üblicherweise mit einem Produkt , in dem Klammern stehen ???
Huggy Auf diesen Beitrag antworten »
RE: Eulersche Funktion und Primzerlegung
Zitat:
Original von Sensi
Zu Elvis: Also für n= p*q ist phi(n)= (p-1)*(q-1) oder nicht?

Das ist für richtig. Ist dir jetzt klar, wie man dann aus n und p und q berechnen kann?

Zitat:
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...

Auch das ist richtig. Nur braucht man ja für normalerweise die Primfaktorzerlegung von n.

@Edit
Elvis: Sorry, hat sich mit dir überschnitten.
 
 
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!
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. Freude
Tip: Schreibe
1.
2.
Sensi Auf diesen Beitrag antworten »
RE: Euler
Danke, das ist total nett!
Also: 1. n= p*q
2. phi(n)= n - p - q + 1?
Elvis Auf diesen Beitrag antworten »
Euler
Genial. smile Wink Freude Das ist es. Jetzt kommt die 100 Millionen Dollar Frage: Wieviele Variable haben wir und wieviele Gleichungen haben wir ?
Elvis Auf diesen Beitrag antworten »
euler
entschuldigung . mit Variable meine ich Unbekannte
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
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. smile
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 Wink
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.
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Falls du noch ein bißchen weiter rechnen möchtest, kommst du auf eine quadratische Gleichung, deren beide Nullstelle dann die gesuchten Primzahlen sind.

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 ...
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

Neue Frage »
Antworten »



Verwandte Themen

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