euler'sche phifunktion
-
hallo, es gilt phi(p) = p-1, falls p eine Primzahl ist. Warum gilt das dann nicht:
phi(12) = phi(2*2*3) = phi(2) * phi(2) * phi(3) = 1 * 1 * 2 = 2, denn es gilt
phi(m*n) = phi(m) * phi(n)
phi(12) ist aber 4
Wie das?
-
phi(m*n) = phi(m) * phi(n)
Laut Wikipedia gilt das nur für n, m teilerfremd, also nicht für m=n=2.
-
phi12 schrieb:
Wie das?
Weil
phi(m*n) = phi(m) * phi(n)
nur gilt, wenn m und n teilerfremd sind.
edit: 20 Sekunden zu spät! Ich hätte im Kopf wissen müssen, was coprime auf deutsch heißt, anstatt es nachzuschlagen.
-
für n = p1e x p2^e2 x ... x pn^en (Primfaktorzerlegung) gilt
phi(n) = p1^(e1-1) x (p1-1) x p2^(e2-1) x (p2-1) x ... pn^(en-1) x (pn-1)
hier: n = 12 = 2^2 x 3^1 => phi(12) = 2^1 x (2-1) x 3^0 x (3-1) = 4
(nämlich teilerfremd zu 12 sind die 4 (=phi(12)) Zahlen 1,5,7,11)
