WisFaq!

Modulorekenen ivm Eulers totientfunctie

In het vak 'structuren' leerden we heel wat over modulorekenen. De stelling van Euler kwam onder meer aan bod (ook de omgekeerde stelling geldt). De stelling luidde dus

Neem n$\in$$\mathbf{N}$₀ en onderstel dat a$\in$$\mathbf{Z}$
Dan geldt:
a^f(n)º1 mod n $\Leftrightarrow$ ggd(a,n)=1

(Een bewijs van de stelling was zeer eenvoudig, omdat we al heel wat over groepen, ringen, modulorekenen kenden. De doorgaande pijl is eenvoudig (zonder a uit L.L. af en de rest vormt een inverse voor a mod n, zodat ggd(a,n)=1 (andere stelling)). De terugkerende pijl: omdat ggd(a,n)=1 behoort a tot de verzameling eenheden van $\mathbf{Z}$_n en daarom (andere stelling) is de orde van a een deler van de orde van de verzameling eenheden (=f(n)) zodat de stelling zeker klopt.)

Nu komt mijn vraag:

Voor mezelf formuleerde ik ook 2 stellingen die gelijken op die van Euler. Ik vond nog geen tegenvoorbeeld, maar ook geen bewijs voor de stellingen. Indien iemand van jullie iets zou kunnen zeggen over het bewijzen / ontkrachten van één van de stellingen zou dat al heel tof zijn. De vermoedens zijn:

1) Neem n$\in$$\mathbf{N}$₀ en onderstel dat a$\in$$\mathbf{Z}$
Dan geldt:
a^f(n)ºa^kf(n) mod n ; k$\in$$\mathbf{N}$₀
(Dit dus zonder de voorwaarde van ggd.)

2) Neem n$\in$$\mathbf{N}$₀ en onderstel dat a$\in$$\mathbf{Z}$
Dan geldt:
a^f(n)+1ºa mod n $\Leftrightarrow$ ggd(a,ⁿ/_ggd(a,n))=1
(Als Euler geldt, geldt deze congruentie zeker ook. Inderdaad is deze voorwaarde voor ggd een zwakkere voorwaarde dan die voor Euler (ggd(a,n)=1).)

Joeri Verscheure
7-5-2004

Antwoord

Hallo, Joeri. Nu beter, hoewel er nog geen antwoord uit Nijmegen is gekomen.
Stel d=ggd(a,n), a=dA, n=dN, zodat ggd(A,N)=1.
Er geldt f(n) = f(N)z voor een geheel getal z.
Ook geldt A^f(N)=1 (mod N), dus A^f(N)=1+mN voor zekere m.
Dan a^f(N)=d^f(N)(1+mN), en ook a^f(n)=d^f(n)(1+mN)^z=d^f(n)(1+jN) voor zekere j.
Dan a^kf(n)=d^kf(n)(1+jN)^k= d^kf(n)(1+uN) voor zekere u.
Omdat Nd^f(n) een veelvoud is van n, leidt men hieruit af:
a^f(n)+1=ad^f(n)(mod n) en
a^kf(n)=d^kf(n)(mod n).
Uw vragen worden nu:
1) Onder welke voorwaarden is d^kf(n)=d^f(n)(mod n)?
Ofwel:wanneer is n deler van d^kf(n)-d^f(n)?
2) Onder welke voorwaarden is ad^f(n)=a (mod n)?
Ofwel: wanneer is n deler van a(d^f(n)-1)?
Ik hoop dat u hier al iets aan hebt. Maar misschien was u zelf al ongeveer zo ver gekomen.
Men kan nu verder naar de priemfactorontbindingen van a en n kijken, en daar bij onderscheiden:
de priemfactoren die alleen in a voorkomen, de priemfactoren die in a vaker voorkomen dan in n, de priemfactoren die in a en n even vaak voorkomen, de priemfactoren die in n vaker voorkomen als in a, en de priemfactoren die alleen in n voorkomen.
Succes. Stel gerust nadere vragen. Hennie

hr
12-5-2004