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 pa van n bevat waarvoor ggd(a,p)=p; en y alle andere priemfactoren van n, dus ggd(a,y)=1.
Nu weten we dat aF(n)º1 mod y, wegens Euler want F(y) is een deler van F(n) en ggd(a,y)=1. Verder is ook aF(n)º0 mod x (argumenteer dat F(n) steeds groter is dan de macht van p in n). Bijgevolg is aF(n)ºakF(n)º1 mod y en ook aF(n)ºakF(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 aF(n)+1º0 mod x en aF(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 (**) aF(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 df(n)-1 ook deelbaar door 73. Over en sluiten. Amen.
Dit is een reactie op vraag 23675 
