De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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}$0 en onderstel dat a$\in$$\mathbf{Z}$
Dan geldt:
af(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}$0 en onderstel dat a$\in$$\mathbf{Z}$
Dan geldt:
af(n)ºakf(n) mod n ; k$\in$$\mathbf{N}$0
(Dit dus zonder de voorwaarde van ggd.)

2) Neem n$\in$$\mathbf{N}$0 en onderstel dat a$\in$$\mathbf{Z}$
Dan geldt:
af(n)+1ºa mod n $\Leftrightarrow$ ggd(a,n/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
Student universiteit België - vrijdag 7 mei 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 Af(N)=1 (mod N), dus Af(N)=1+mN voor zekere m.
Dan af(N)=df(N)(1+mN), en ook af(n)=df(n)(1+mN)z=df(n)(1+jN) voor zekere j.
Dan akf(n)=dkf(n)(1+jN)k= dkf(n)(1+uN) voor zekere u.
Omdat Ndf(n) een veelvoud is van n, leidt men hieruit af:
af(n)+1=adf(n)(mod n) en
akf(n)=dkf(n)(mod n).
Uw vragen worden nu:
1) Onder welke voorwaarden is dkf(n)=df(n)(mod n)?
Ofwel:wanneer is n deler van dkf(n)-df(n)?
2) Onder welke voorwaarden is adf(n)=a (mod n)?
Ofwel: wanneer is n deler van a(df(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

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 12 mei 2004
 Re: Modulorekenen ivm Eulers totientfunctie 



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3