Heltalsdivision med rest

Inom algebra och talteori utgör heltalsdivision med rest , euklidisk division eller divisionsalgoritmen 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 $a$ (kallat dividend) och $b\neq 0$ (kallat divisor) finns två entydigt bestämda heltal $k$ och $r$ sådana att

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

Talet $k$ kallas (heltals)kvot (även principal kvot) och talet $r$ kallas (principal) rest. Denna sats kallas divisionsalgoritmen.

Bevis för heltal

Beviset består av två delar. Först att $k$ och $r$ 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 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).

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 $p(x)$ och $q(x)\neq 0$ finns två entydigt bestämda polynom $k(x)$ och $r(x)$ sådana att

$p(x)=q(x)\cdot k(x)+r(x)\,,\quad deg(r(x))<deg(q(x))$.

Polynomet $k(x)$ kallas kvotpolynom och $r(x)$ kallas restpolynom. 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