Heltalsdivision med rest

Från Wikipedia
(Omdirigerad från Divisionsalgoritmen)
Hoppa till navigering Hoppa till sök

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 | redigera wikitext]

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 | redigera wikitext]

Beviset består av två delar. Först att och existerar och sedan att dessa båda är unika.

Existens[redigera | redigera wikitext]

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 | redigera wikitext]

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 | redigera wikitext]

Division med rest är även definierad för polynom: till två polynom och finns två entydigt bestämda polynom och sådana att

.[5][6]

Polynomet kallas kvotpolynom och kallas restpolynom.[7] deg betecknar polynomets grad.

Andra former av division med rest[redigera | redigera wikitext]

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 | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ Bok "Förberedande kurs i matematik", Stockholms Universitet, år 2014, sida 10
  2. ^ Juliusz Brzezinski, Delbarhet och primtal, sid. 4 och 24.
  3. ^ Lars-Åke Lindahl, 2012, Elementär talteori, Uppsala, sid 2.
  4. ^ Mikael Hindgren, 2020, Något om polynom, Högskolan i Halmstad, sid. 5.
  5. ^ [a b] Petter Brändén, 2018, Polynom och gaussiska heltal[död länk].
  6. ^ Lars-Åke Lindahl, 2012, Elementär talteori, sid. 39.
  7. ^ Mikael Forsberg, 2014, Komplexa tal och polynom - en introduktion, sid. 33.
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.