Heltalsdivision med rest

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.

Det finns en sats som säger att det till två heltal ${\displaystyle a}$ (kallat dividend) och ${\displaystyle b\neq 0}$ (kallat divisor) finns två entydigt bestämda heltal ${\displaystyle k}$ och ${\displaystyle r}$ sådana att

${\displaystyle a=b\cdot k+r\,,\quad 0\leq r<|b|}$.

Talet ${\displaystyle k}$ kallas (heltals)kvot (även principal kvot) och talet ${\displaystyle r}$ kallas (principal) rest. Denna sats kallas divisionsalgoritmen.^[3][4]

Beviset består av två delar. Först att ${\displaystyle k}$ och ${\displaystyle r}$ existerar och sedan att dessa båda är unika.

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 k₁ ≥ 0 och r₁ ≥ 0 uppfylla a = bk₁ + r₁, vilket exempelvis k₁ = 0 och r₁ = a gör. Om r₁ < b är vi klara. Annars sätt k₂ = k₁ + 1 och r₂ = r₁ − b vilket ju självklart uppfyller a = bk₂ + r₂ och 0 ≤ r₂ < r₁. Genom att upprepa det här förfarandet kommer vi till sist att få ett k_n = n och ett r_n = a - nb sådana att a = bk_n + r_n och 0 ≤ r_n < b.

Detta bevisar existensen (och ger även en ineffektiv metod att beräkna r och k).

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.

Division med rest är även definierad för polynom: till två polynom ${\displaystyle p(x)}$ och ${\displaystyle q(x)\neq 0}$ finns två entydigt bestämda polynom ${\displaystyle k(x)}$ och ${\displaystyle r(x)}$ sådana att

${\displaystyle p(x)=q(x)\cdot k(x)+r(x)\,,\quad deg(r(x))<deg(q(x))}$.^[5][6]

Polynomet ${\displaystyle k(x)}$ kallas kvotpolynom och ${\displaystyle r(x)}$ kallas restpolynom.^[7] deg betecknar polynomets grad.

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]

• 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