Eulersche Funktion?
Moinsen, das Grundprinzip habe ich eigentlich verstanden - ϕ(4) wäre 2, da nur die 1 und die 3 teilerfremd sind. ϕ(primzahl) = primzahl-1 ist auch soweit ok.
Wie gehe ich nun bei großen Zahlen vor?
sagen wir mal ϕ(81). Ich dachte erst mal gelesen zu haben dass ϕ(9) * ϕ(9) = ϕ(81) ist, aber ϕ(9) = 6, und 6*6 ist 36, ϕ(81) aber ist mehr
ϕ(3^3*3^3) wäre wahrscheinlich korrekter oder? wie würde ich das dann ausrechnen?
1 Antwort
Die Eulersche Phi-Funktion ist in dem Sinne multiplikativ, als dass für teilerfremde Zahlen a, b gilt:
Weiter gilt für Primzahlen p, dass
ist. Den Beweis dazu kannst du auf hier auf Wikipedia nachlesen.
Es ist also:
Wie würde ich in diesem Fall ein phi(98) berechnen? 98 lässt sich per Primfaktorzerlegung aufteilen in 7*7*2, aber wenn ich die phi werte multipliziere erhalte ich 6*6*1 = 36, aber laut Liste ist phi(98) = 42
Liegt es daran, dass ich 2x die 7 dabei habe? Wie gehe ich hier vor? :P
Wie berechne ich denn dann z.B. ein Phi(42)? In der Primfaktorzerlegung wäre es dann phi(2*3*7) da diese Zahlen alle teilerfremd sind, gilt dann bei drei teilerfremden zahlen immer phi(a)*phi(b)*phi(c)? = 1*2*6 = 12?
So ist es.
Wie würde ich in diesem Fall ein phi(98) berechnen? 98 lässt sich per Primfaktorzerlegung aufteilen in 7*7*2, aber wenn ich die phi werte multipliziere erhalte ich 6*6*1 = 36, aber laut Liste ist phi(98) = 42
Liegt es daran, dass ich 2x die 7 dabei habe? Wie gehe ich hier vor? :P
Genau, 7 und 7 sind nicht teilerfremd. Es lässt sich aber wieder die zweite Formel anwenden, denn es ist:
Durch Primfaktorzerlegung, Anwenden der Multiplikativität und dann Anwenden der Primfaktorformel auf jeden Faktor kommst du immer schnell zu einem Ergebnis.
Wie berechne ich denn dann z.B. ein Phi(42)? In der Primfaktorzerlegung wäre es dann phi(2*3*7)
da diese Zahlen alle teilerfremd sind, gilt dann bei drei teilerfremden zahlen immer phi(a)*phi(b)*phi(c)? = 1*2*6 = 12?