WisFaq!

N|phi(pn-1)

Beste wisfaq,

Ik zit met het volgende probleem. Ik moet bewijzen dat n|phi(p^n-1) waar phi de Euler totient functie is. Ik kan dit probleem grotendeels zelf oplossen, maar er is een kleinigheidje dat me dwars blijft zitten.

Mijn oplossing is als volgt:

Zij m=p^n-1. Dan hebben we p^n = 1 (mod m). Nu zou ik willen concluderen dat n de order is van p in de groep (Z/mZ)^x. (de multiplicative group of residue classes modulo m). Aangezien dan de groep order phi(p^n-1) is, zou het resultaat onmiddelijk volgen. Echter mijn probleem is: hoe weet ik zeker dat n de order is van p in de groep (Z/mZ)^x, en niet een veelvoud van de order bijvoorbeeld.

Bij voorbaat dank,

Herman

Herman de vries
31-5-2009

Antwoord

Alle machten pⁱ, voor i=1,2,...,n-1, zijn ongelijk aan 1; dus pⁿ is de eerste macht van p die 1 is. De orde is dus n.

kphart
1-6-2009