1 svar
185 visningar
Albiki 5320
Postad: 28 aug 2020 Redigerad: 28 aug 2020

Kinesiska restsatsen

Sats. Om heltalen nn och mm har största gemensamma delaren 11 och (a,b)(a,b) är två heltal, så finns det ett enda heltal som har resten aa vid division med nn och resten bb vid division med mm.

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

    x=amv+bnux = amv+bnu.

Detta tal har resten aa vid division med nn, eftersom

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

och med liknande resonemang resten bb vid division med mm.

Jättetrevligt men kanske nåt med analys istället?

Svara Avbryt
Close