Kinesiska restsatsen

Sats. Om heltalen $n$ och $m$ har största gemensamma delaren $1$ och $(a,b)$ är två heltal, så finns det ett enda heltal som har resten $a$ vid division med $n$ och resten $b$ vid division med $m$.

Bevis. Bezouts identitet ger att det finns två heltal $(u,v)$ sådana att $nu+mv=1$. Kombinera detta par med paret $(a,b)$ för att skapa heltalet

    $x = amv+bnu$.

Detta tal har resten $a$ vid division med $n$, eftersom

    $mv=1-nu \implies x=a+(b-a)nu$,

och med liknande resonemang resten $b$ vid division med $m$.