WisFaq!

Re: Bewijs van de stelling van Euler

In het bewijs van de stelling van Euler:
a^j(m) º 1 (mod m)
gebruiken ze de volgende stelling;

Is {x₁, x₂, ..., x_j(m)} een gereduceerd restsysteem (mod m), dan is
{ax₁, ax₂, ..., ax_j(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
11-2-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 ax_j zijn alle relatief priem met m, immers ggd(a,m) = 1 (gegeven) en (x_j, m) = 1 (de x_j's zijn elementen van een gereduceerd restsysteem).

(1) De getallen ax_j zijn ook alle verschillend (het zijn er in totaal dus precies j(m)).
Immers, gebruikend van ggd(a,m) = 1,
ALS
ax_i º ax_j (mod m)
DAN
x_i º x_j (mod m)
en dus (als elementen van het gereduceerde restsysteem)
x_i = x_j
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.

dk
11-2-2005