De stelling zegt het volgende;
|
|
Als twee getallen a en
b geen enkele gemeenschappelijke
priemfactor hebben
Dan zijn er gehele getallen x en y te
vinden zodat ax - by = 1 |
|
|
Bekijk de volgende rij
getallen: a, 2a,
3a, ... , (b - 1)•a
Daar staan b - 1 getallen.
Bekijk nu de rest van deze getallen bij delen door b.
Rest 0 komt niet voor want a en b hadden geen
gemeenschappelijke priemfactoren.
Rest b kan uiteraard ook niet voorkomen.
Stel dat rest 1 ook niet voorkomt.
Dan zijn er nog maar b
- 2 mogelijke
resten voor deze b - 1 getallen.
Dus twee getallen uit de rij hebben dezelfde
rest (pigeonhole), ofwel pa = qa (mod b)
Maar dan is pa - qa = (p
- q)a
een veelvoud van b
Omdat a geen veelvoud van b
kan zijn moet p - q dat wel zijn
Maar dat kan niet, want p en q zijn
beiden kleiner dan b
Een tegenspraak!
Conclusie: rest 1 moet wel voorkomen, en
er is een x zodat xa = 1 (mod b) dus ax
- by = 1
|