Inom algebra och talteori utgör heltalsdivision med rest Bok "Förberedande kurs i matematik", Stockholms Universitet, år 2014, sida 10, euklidisk division eller divisionsalgoritmen Juliusz Brzezinski, Delbarhet och primtal, sid. 4 och 24. en division tillämpad på heltal. Dividend, divisor, kvot och rest är samtliga heltal.
Sats
Det finns en sats som säger att det till två heltal (kallat dividend) och (kallat divisor) finns två entydigt bestämda heltal och sådana att
.
Talet kallas (heltals)kvot (även principal kvot) och talet kallas (principal) rest. Denna sats kallas divisionsalgoritmen.Lars-Åke Lindahl, 2012, Elementär talteori, Uppsala, sid 2.
Bevis för heltal Beviset består av två delar. Först att och existerar och sedan att dessa båda är unika.
Existens Betrakta först fallet b < 0. Om vi sätter b' = −b och k' = −k kan ekvationen a = bk + r skrivas som a = b'k' + r och olikheten 0 ≤ r < |b| som 0 ≤ r < b vilket gör beviset för fallet b < 0 identiskt med beviset för b > 0.
På samma sätt kan vi, om a < 0 och b > 0, sätta a' = −a, k' = −k − 1 och r' = b − r varvid ekvationen a = bk + r kan skrivas a' = bk' + r''' och olikheten 0 ≤ r < b kan skrivas 0 ≤ r' < b. Sålunda reduceras existensbeviset till fallet a ≥ 0 och b > 0 varför vi endast behöver beakta detta fall.
Låt k1 ≥ 0 och r1 ≥ 0 uppfylla a = bk1 + r1, vilket exempelvis k1 = 0 och r1 = a gör. Om r1 < b är vi klara. Annars sätt k2 = k1 + 1 och r2 = r1 − b vilket ju självklart uppfyller a = bk2 + r2 och 0 ≤ r2 < r1. Genom att upprepa det här förfarandet kommer vi till sist att få ett kn = n och ett rn = a - nb sådana att a = bkn + rn och 0 ≤ rn < b.
Detta bevisar existensen (och ger även en ineffektiv metod att beräkna r och k).
Entydighet Antag att det finns k, k' , r och r' sådana att 0 ≤ r < |b|, 0 ≤ r' < |b|, a = bk + r och a = bk' + r. Om vi adderar de två olikheterna 0 < r ≤ |b| och -|b| ≤ -r' < 0 får vi -|b| < r - r' < |b|, det vill säga |r - r'| < |b|.
Om vi subtraherar de båda ekvationerna får vi b(q' - q) = (r - r'). Sålunda delar |b| |r - r'|. Om |r - r'| ≠ 0 medför detta att |b| ≤ |r - r'|, vilket motsäger föregående olikhet. Alltså har vi att r = r' och b(k' - k) = 0. Då b ≠ 0, medför detta att k = k' varigenom entydigheten bevisats.
Polynomdivision
Division med rest är även definierad för polynom: till två polynom och finns två entydigt bestämda polynom och sådana att
.Petter Brändén, 2018, Polynom och gaussiska heltal.Lars-Åke Lindahl, 2012, Elementär talteori, sid. 39.
Polynomet kallas kvotpolynom och kallas restpolynom.Mikael Forsberg, 2014, Komplexa tal och polynom - en introduktion , sid. 33. deg'' betecknar polynomets grad.
Andra former av division med rest
Division med rest kan också definieras för annat, exempelvis gaussiska heltal (se artikeln för definition). Den allmänna matematiska struktur som har en divisionsalgoritm är en euklidisk ring.
Se även Kort division (förenklad algoritm för manuell division i vissa fall) Liggande stolen eller trappan eller lång division (algoritm för manuell division med stora tal, även för tal med decimaltecken) Euklides algoritm (algoritm för att bestämma största gemensamma delare till två heltal) Polynomdivision
Referenser
Kategori:Aritmetik Kategori:Division Kategori:Satser inom talteori