eulerische phi funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:52 So 29.07.2012 | | Autor: | perl |
| Aufgabe | von einer Zahl N weiß man, dass sie das Produkt N = pq zweier verschiedener primzahlen p,q ist. zeige, dass man p und q bestimmen kann, wenn man N und phi(N) kennt.
Führe dies am Beispiel N = 438751 und phi(N) = 437400 aus. |
Hallo :)
Ich glaube die Lösung hier muss ganz simpel gehen... ich komm nur nicht drauf.
gegeben ist pq=N und die Mächtigkeit ihrer Primzahlen phi(N).
Ich hab leider keine Idee... intuitiv würde ich sagen, dass ich N durch phi(n) teile.
N:phi(N) = 438751 : 437400 =1 Rest(1351)
Doch was hätte ich damit gewonnen? oder ist es totaler quatsch?
DANKE <3
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:16 So 29.07.2012 | | Autor: | Teufel |
Hi!
Eventuell führt dein Weg auch noch irgendwann zum Ziel, aber ich würde es so machen:
$N=pq$
[mm] $\varphi(N)=(p-1)(q-1)$,
[/mm]
wobei die 2. Gleichung die einzige wichtige Beobachtung ist. Nun kannst du die 1. Gleichung z.B. nach $p$ umstellen und in die 2. einsetzen. Den Rest schaffst du sicher!
Und wo kommt deine 1351 überhaupt her? :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:19 So 29.07.2012 | | Autor: | perl |
Verrückt... auf dem Weg war ich auch schon... ich hab blos kein 2. Lgs gesehn :D
oh man... Danke!
(und ja... jetz krieg ichs hin :D )
|
|
|
|
