WisFaq!

Produktformule van Euler

De volgende stelling moet ik gebruiken om fi (60) te berekenen. (Ik weet niet hoe ik het symbool van fi kan invoeren)

De produkt voor de fi-functie van Euler.
Zij mÎZ, m2, met priemontbinding
m = n
Õp(i) ^a(i) waarbij a(i) 0 voor
i=1

alle i. Dan geldt:

fi(m) = n
Õ p(i)^a(i0-1 · (p(i) -1)
i=1

Ik begrijp de tekens in de priemontbinding niet (oa Õ), wat wordt er bedoeld en hoe kan ik dit gebruiken?

BVD

Tjen
14-11-2005

Antwoord

Dag Tjen,
die notatie met een Õ betekent het product van een aantal factoren net zoals de notatie met een å een som van een aantal termen betekent. Zo is
Õ⁶_i=1i=1*2*3*4*5*6=720(=6!).
Zoals je weet kun je ieder geheel getal groter dan 1 op een unieke manier schrijven als een product van priemfactoren. Zo is 720=2⁴*3²*5¹.
De eerste notatie hierboven is daar een kortschrift voor: in het geval van n=720 geldt dus p(1)=2 en a(1)=4, p(2)=3 en a(2)=2, p(3)=5 en a(3)=1.
De getallen p(i) hoeven geen opvolgende priemgetallen te zijn. Bijvoorbeeld 56=2³*7¹. In dit geval is p(1)=2 en p(2)=7.

De tweede formule vertelt dan hoe je de j-functie van Euler kunt berekenen als je de priemontbinding hebt gevonden. Voor iedere priemfactor p(i) verlaag je de exponent met 1 en vermenigvuldigt met p(i)-1.
Voor n=720=2⁴*3²*5¹ geldt dus j(720)=2^4-1*(2-1)*3^2-1*(3-1)*5^1-1*(5-1)=2³*1*3¹*(2)*5⁰*(4)=192.

Bij jouw opgave: bereken j(60), moet je dus eerst een priemontbinding van 60 maken: 60=2²*3*5.
Dus j(60)=2*(2-1)*(3-1)*(5-1)=2*2*4=16.
Dat klopt want er zijn precies 16 getallen kleiner dan 60 die relatief priem zijn t.o.v. 60 (als je 1 meetelt):
1,7,11,13,17,19,23,29,31,37,41,43,47,49!!!!,53,59.

hk
14-11-2005