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

Re: Bewijs van de stelling van Euler

 Dit is een reactie op vraag 33589 
In het bewijs van de stelling van Euler:
aj(m) 1 (mod m)
gebruiken ze de volgende stelling;

Is {x1, x2, ..., xj(m)} een gereduceerd restsysteem (mod m), dan is
{ax1, ax2, ..., axj(m)}
een gereduceerd restsysteem (mod m), mits ggd(a,m) = 1.

Maar ik heb geen flauw idee hoe ze hierop zouden kunnen komen, zou iemand me dat kunnen uitleggen?
Alvast bedankt; groet,

Paul
Leerling bovenbouw havo-vwo - vrijdag 11 februari 2005

Antwoord

Zoals al eerder opgemerkt: het is geen eenvoudige materie!

Volgens de definitie:
Een gereduceerd restsysteem mod m bestaat uit (1) j(m) getallen die (2) alle relatief priem zijn met m.

We geven het bewijs van de door jou geciteerde stelling, verwijzend met (1), (2) naar de bovenstaande definitie.

(2) De getallen axj zijn alle relatief priem met m, immers ggd(a,m) = 1 (gegeven) en (xj, m) = 1 (de xj's zijn elementen van een gereduceerd restsysteem).

(1) De getallen axj zijn ook alle verschillend (het zijn er in totaal dus precies j(m)).
Immers, gebruikend van ggd(a,m) = 1,
ALS
axi axj (mod m)
DAN
xi xj (mod m)
en dus (als elementen van het gereduceerde restsysteem)
xi = xj
Waarmee de stelling bewezen is.

Voorbeeld voor een restsysteem module 10.

Volledig restsysteem: {0, 1 2, 3, 4, 5, 6, 7, 8, 9}
Gereduceerd restsysteem: {1, 3, 7, 9}
Dit klopt, want j(10) = 4.
Nu moeten we een getal a kiezen met (a, 10) = 1.
Kies bijvoorbeeld a = 13.
De stelling zegt dan dat {13, 39, 91, 117} ook een reduceerd restsysteem mod 10 is.
Illustrerend:
{13, 39, 91, 117} {3, 9, 1, 7} (mod 10)

Het is dus eenvoudig onder woorden te brengen:
De elementen van een gereduceerd restsysteem mod 10 mogen met een getal a, waarbij ggd(a, 10) = 1, vermenigvuldigd worden.

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 11 februari 2005



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

©2001-2022 WisFaq - versie 3