| Autor |
Beitrag |
    
wolfgang
| | Veröffentlicht am Sonntag, den 17. Juni, 2001 - 14:47: | 
|
Hallo!
Ich bin mit der folgenden Aufgabe schier am verzweifeln. Und das, obwohl unser Prof gemeint har, sie wäre recht einfach 
Könnt ihr mir bitte dabei helfen?
Sei n eine gegebene natürliche Zahl, von der man zusätzlich weiß, dass n das Produkt zweier verschiedener Primzahlen p und q ist und den Wert phi(n) der Eulerschen phi-Funktion kennt.
Wie kann ich nun zeigen, wie man dann p und q mit geringem(!) Aufwand berechnen kann?
Wolfgang |
Fstrichvonx (Fstrichvonx)
| | Veröffentlicht am Montag, den 18. Juni, 2001 - 11:40: |
|
Hi,
also:
man weiss:
n=p*q , p,q-prim, p|=q ,phi(n)=a
es gilt:
phi(n)=n*produkt_ueber_alle_primteiler_i_von_n(1-1/i)
phi(n)=n*(1-1/p)*(1-1/q)=a
->
I. n=p*q
II. n*(1-1/p)*(1-1/q)=a
du hast dann zwei gleichungen mit zwei unbekannten.
hoffe es hilft dir |
Fstrichvonx (Fstrichvonx)
| | Veröffentlicht am Montag, den 18. Juni, 2001 - 11:47: |
|
da ggT(p,q)=1
kannst du auch die gleichung
phi(p*q)= phi(p)*phi(q)=a =phi(n)
und da p,(q) prim -> phi(p)=p-1
I. (p-1)(q-1)=a
II. n=p*q
ist ja noch einfacher! |
wolfgang
| | Veröffentlicht am Montag, den 18. Juni, 2001 - 23:09: |
|
Hi F'(x)!
Danke! Danke! Danke!!!
Wolfgang |
|
