Primfaktorzerlegung von sehr großen Zahlen

Aufrufe: 431     Aktiv: 08.09.2021 um 15:57
1
Hallo,

ich habe folgende Aufgabe: Ich soll die PFZ von 626.257 bestimmen. Als Tipp steht ein Hinweis:  φ (626.257) = 624.640.

Der Hinweis sagt mir aus, dass es zu 626.257 insgesamt 624.640 teilerfremde Zahlen gibt, die nicht größer sind als 626.257. Wie komme ich aber anhand dieser Information auf die PFZ? Den Weg "zu Fuß" habe ich schon angefangen... komme aber nicht weit... 

Kann jemand helfen, ohne die Lösung vorzusagen?
Danke!
Diese Frage melden
gefragt

Punkte: 40

 
Kommentar schreiben
1 Antwort
1
Benutze den Satz: Wenn $p,q$ Primzahlen sind, so ist $\varphi(p\,q)=(p-1)(q-1)$.
Ich würde den Hinweis so verstehen, dass es damit geht. Die Primfaktorzerlegung von 624640 ist relativ einfach. Dann diese Zahl in zwei Faktoren zerlegen, so dass die rechte Seite aus dem Satz entsteht. Damit kommt man zum Ziel, etwas Probieren ist natürlich nötig.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.93K

 
Die PFZ von 624640 ist 2^11*5*61. Durch Probieren bin ich auf 624640 = (2^4)*(2^7*5*61) = 16*39040 = (17-1)*(39041-1) gekommen, wobei 17 und 39041 Primzahlen sind.

Leider weiß ich immer noch nicht, was mir das jetzt gebracht hat...   ─   einmaleins 08.09.2021 um 14:22
Nein, erfüllt es leider nicht. Denn:

Wir wissen ja φ (626.257) = 624.640. Somit ist φ (626.257) = 16*39040. Somit müsste 17*39041 eine PFZ von 626.257 sein, ist es aber nicht, denn 17*39041=663697.

Ich habe weiterprobiert: 624.640 = 976 * 640 = (977-1)*(641-1). 977 und 641 sind Primzahlen und ergeben beide im Produkt 626.257. Die Primfaktorzerlegung von 626.257 ist also 977*641.

Klingt das richtig?
   ─   einmaleins 08.09.2021 um 15:09

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.