Inom algebra och talteori utgör heltalsdivision med rest [1], euklidisk division eller divisionsalgoritmen [2] en division tillämpad på heltal. Dividend, divisor, kvot och rest är samtliga heltal.
Sats redigera
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.[3][4]
Bevis för heltal redigera
Beviset består av två delar. Först att och existerar och sedan att dessa båda är unika.
Existens redigera
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 redigera
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 redigera
Division med rest är även definierad för polynom: till två polynom och finns två entydigt bestämda polynom och sådana att
Polynomet kallas kvotpolynom och kallas restpolynom.[7] deg betecknar polynomets grad.
Andra former av division med rest redigera
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.[5]
Se även redigera
- 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 redigera
- ^ Bok "Förberedande kurs i matematik", Stockholms Universitet, år 2014, sida 10
- ^ Juliusz Brzezinski, Delbarhet och primtal, sid. 4 och 24.
- ^ Lars-Åke Lindahl, 2012, Elementär talteori, Uppsala, sid 2.
- ^ Mikael Hindgren, 2020, Något om polynom, Högskolan i Halmstad, sid. 5.
- ^ [a b] Petter Brändén, 2018, Polynom och gaussiska heltal[död länk].
- ^ Lars-Åke Lindahl, 2012, Elementär talteori, sid. 39.
- ^ Mikael Forsberg, 2014, Komplexa tal och polynom - en introduktion, sid. 33.