WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Re: Modulorekenen ivm Eulers totientfunctie

Dit is een reactie op vraag 23675

Wel, Joeri zijn vermoedens zijn juist. Kortweg gezegd moet hij maar denken dat een congruentie modulo n opgelost is, als je de congruentie kent voor elke priemfactor (denk aan de Chinese reststelling).

Nu meer concreet over de gestelde vermoedens.
Ontbind n als x.y, waarbij y alle priemfactoren p^a van n bevat waarvoor ggd(a,p)=p; en y alle andere priemfactoren van n, dus ggd(a,y)=1.

Nu weten we dat a^F(n)º1 mod y, wegens Euler want F(y) is een deler van F(n) en ggd(a,y)=1. Verder is ook a^F(n)º0 mod x (argumenteer dat F(n) steeds groter is dan de macht van p in n).
Bijgevolg is a^F(n)ºa^kF(n)º1 mod y en ook a^F(n)ºa^kF(n)º0 mod x... en de Chinese reststelling verzekert dat beide dingen dan ook gelijk zijn modulo n=x.y.

Wat vraag b betreft, kan je n op dezelfde manier ontbinden als x.y. De voorwaarde van Joeri over de ggd wil dan zeggen dat x een deler is van a. Nu is het duidelijk volgens dezelfde argumenten als hierboven dat steeds geldt dat a^F(n)+1º0 mod x en a^F(n)+1ºa mod y (**).

De pijl van links naar rechts verkrijg je door je gegeven te reduceren modulo x, je krijgt dan dat aº0 mod x of dus dat x een deler is van a.
De andere pijl dan. Nu weet je dat aº0 mod x en bijgevolg is wegens (**) a^F(n)+1º0ºa mod x. Dat dat ook geldt modulo y wisten we al (zie **), dus de Chinese reststelling zegt dan dat de congruentie geldt voor n=x.y.

Adriaa
Docent - woensdag 12 mei 2004

Antwoord

Goed gezegd, Adriaan.
Ik had dat uiteindelijk ook ongeveer zo gedacht, maar wilde het Joeri zelf laten afmaken.
In mijn notatie: als n bijvoorbeeld 3 factoren 7 heeft, en d geen, dan is d^f(n)-1 ook deelbaar door 7³.
Over en sluiten. Amen.

Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 12 mei 2004