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