WisFaq!

Theorie van Euler

Waarom geldt: $\phi$(n) = (p-1)·(q-1) altijd?

Rick
28-9-2007

Antwoord

Dat geldt niet voor iedere n, maar wel voor getallen n die een product zijn van precies 2 priemgetallen p en q.

In het algemeen is j(n) gelijk aan het aantal getallen kleiner dan n die geen factoren gemeen hebben met n (1 telt in dit geval mee).
Nemen we als voorbeeld n=6 dan hebben 1 en 5 geen factoren gemeen met 6.
Dus j(6)=2.
De priemfactoren van 6 zijn 2 en 3. (2-1)·(3-1)=1·2=2.

Nog een voorbeeld: n=15.
Getallen die geen factoren gemeen hebben met 15 zijn 1,2,4,7,8,11,13,14. Totaal 8 stuks.
15=3·5. (3-1)·(5-1)=2·4=8.

Bij n=12 krijgen we: 1,5,7,11, Dus j(n)=4.
12=2·2·3.
Er geldt nu j(12)=(2-1)·2·(3-1)=2·2=4.

I.h.a. als n=priem1ⁿ¹·priem2ⁿ²·priem3ⁿ³...., dan is
j(n)=(priem1-1)·priem1^(n1-1)·(priem2-1)·priem2^(n2-1)·(priem3-1)·priem3^(n3-1).....

Voor meer informatie over Eulers totient functie j zie Totient function

hk
30-9-2007