Ich würde so an diese Aufgabe herangehen:
Gegeben:
1) n = p * q = 4660883 mit p, q Primzahlen
2) φ ( n ) = φ ( p * q ) = φ ( 4660883 ) = 465480
Aus dem Aufgabenzusammenhang kann vermutet werden, dass φ ( n ) die Eulersche Phi-Funktion ist. Diese ordnet jeder natürlichen Zahl n ≥ 1 die Anzahl der zu n teilerfremden Zahlen zu, die nicht größer als n sind.
φ ist eine multiplikative zahlentheoretische Funktion, also gilt für teilerfremde p und q :
A) φ ( p * q ) = φ ( p ) * φ ( q )
Außerdem gilt, falls p eine Primzahl ist:
B) φ ( p ) = p - 1
Da p und q vorliegend Primzahlen sein sollen, sind sie teilerfremd, sodass die beiden Aussagen A) und B) gelten.
Daraus ergibt sich:
φ ( n ) = φ ( p * q ) = φ ( p ) * φ ( q )
= ( p - 1 ) * ( q - 1 )
= p * q - p - q + 1
= 4660883 - p - q + 1 = 465480
<=> p + q = 4660883 - 465480 + 1 = 4195404
Man hat also folgendes Gleichungssystem:
p * q = 4660883
p + q = 4195404
Dieses Gleichungssystem hat allerdings keine natürlichzahlige Lösung, und da ich in meinen Berechnungen keinen Fehler entdecken kann, muss ich also annehmen, dass die gegebenen Werte nicht stimmen ...
