Rick
Leerling bovenbouw havo-vwo - vrijdag 28 september 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=priem1n1·priem2n2·priem3n3...., 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
