WisFaq!

Modulo rekenen met restklassen

Ik kan bewijzen:
ALS ha = ka (mod p) (met p = priem, h en k tussen 0 en p, a willekeurig natuurlijk getal)
DAN h = k (mod p) en zelfs: h = k (omdat k nooit groter kan zijn dan p)

Maar ik moet bewijzen:
Restklassen van a,2a,3a,4a, .. , (p-1)a (met dus modulo p) GELIJK AAN restklassen 1,2,3,..,p-1 (modulo p). Nouja, die laatste restklassen zijn dus ook gelijk aan 1,2,3,..,p-1 want die zijn allemaal relatief priem met p.

Volgens mij is de link hiertussen heel eenvoudig, op verschillende websites werd dit als bewijs neergezet, maar ik zie het nog even niet. Waarom ALS geldt ha = ka (mod p) -- h=k (mod p) of h=k, DAN OOK die restklassen gelijk ??

Jop Schouten
19-1-2011

Antwoord

Het argument is een beetje subtiel.
Ten eerste: wat niet gevraagd wordt is te bewijzen dat de restklasse van ka precies de restklassen van k is.
Wat wel gevraagd wordt is te bewijzen dat de verzameling restklassen {a, 2a, 3a, ..., (p-1)a} gelijk is aan de verzameling restklassen {1, 2, 3, ..., p-1}.
Welnu, neem een k en neem de rest bij deling van ka door p, noem die l_k.
Dan is de restklassen van ka dezelfde als die van l_k en wat je bewezen hebt zegt dat verschillende k's verschillende l_k's opleveren.
De verzameling {l₁, l₂, l₃, ..., l_p-1} heeft dus p-1 elementen en is dus gelijk aan {1,2,3, ..., p-1}.

kphart
24-1-2011