Frage zur Zahlentheorie. Wie berechne ich effizient phi(n)?

Question

Wie berechne ich effizient phi(40797527). Ich komme da einfach nicht weiter.

Vielen Dank

Answer 1

MathFox, 

die Aufgabe ist aus meiner Sicht z.B. für eine Klausur nicht geeignet, weil hier vermutlich der Aufgabensteller auf $$\varphi(p\cdot q)=(p-1)\cdot (q-1)$$ hinaus will, die Zahl jedoch zu groß ist. Die Lösung ist jedenfalls $$\varphi(40797527) = (5591-1)\cdot (7297-1)=5590\cdot 7296=40784640$$

Stelle gerne Rückfragen!

André, savest8

Answer 2

Du meintest bestimmt die Funktion EulerPhi(x) {Es gibt mindestens 3 Phi-Funktionen}

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

zeigt nicht nur die 3 Funktionen, sondern auch die beiden wichtigsten Gesetze zur Zahlenfolge A010 siehe Bild

wenn k=1, folgt: EulerPhi(Prime(x)) = Prime(x)-1

Es läuft also immer auf Primfaktorenzerlegung aus: