+1 Daumen
1,3k Aufrufe
Sie wissen, dass n= 4660
883 das Produkt zweier verschiedenen Primzahlen
p und q ist. Weiter kennen Sie φ(n) = 465480. Bestimmen Sie p und q.
Avatar von

n= 4660
883

Ist das eine Zahl?
Wofür steht das PHI von n?

2 Antworten

+1 Daumen
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 ...
Avatar von 32 k
0 Daumen

Wie JotEs richtig vermutete liegt hier eine

falsche Aufgabenstellung vor: EulerPhi( 4660883 ) = 465480 falsch!!!

Mit http://www.lamprechts.de/gerd/php/Carmichael-Zahl-Faktorisierer.php

kann man 4660883 leicht mit Typ F zerlegen.

Mit http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

kann man EulerPhi(x) { dort OEIS_A(10,y) } berechnen.

also entweder

§1: EulerPhi( 4660883 ) = 4645680

(p-1)*(q-1)=4645680,

p*q = 4660883

4660883+1-4645680=p+q,

p*q=4660883 ergibt 313 und 14891


Oder §2:

EulerPhi( 466883 ) = 465480

466883+1-465480=p+q,

p*q=466883

ergibt 541 und 863

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community