Vierkant Kalender 1999

Oplossingen week 21 (24 t/m 30 mei)

De functie van Euler

Opmerking:De functie van euler wordt hier geschreven als phi(...) i.v.m. de beperkingen van HTML.

Maandag 24 mei:

96.

Dinsdag 25 mei:

24.

Woensdag 26 mei:

2^n-1.

Donderdag 27 mei:

(p-1)(q-1).

Vrijdag 28 mei:

Als ggd(n,k)=1, dan ook ggd(n,n-k)=1.

Bovendien geldt: als k tussen 1 en n ligt, en n groter of gelijk aan 3, dan zijn k en n-k twee verschillende getallen tussen 1 en n. De bijdrage aan phi(n) is dus steeds even.

Zaterdag 29 mei:

phi(2n) = 2n(1-1/2)(1-1/p)...(1-1/q) waarin p,...,q de verschillende priemdelers van n zijn. Dus phi(2n)=n(1 - 1/p)...(1 - 1/q), en dat is precies de formule voor phi(n).

Zondag 30 mei:

Zowel 2n als 3n bevatten de factor 2. Stel p,...,q zijn de priemdelers van n. Dan geldt: phi(2n) = 2n(1-1/2)(1-1/p)...(1-1/q) = n(1-1/p)...(1-1/q), en phi(3n)=3n(1-1/2)(1-1/3)(1-1/p)...(1-1/q) = n(1-1/p)...(1-1/q) Dus phi(2n)=phi(3n).