Divisionsalgoritmen

Från Wikipedia
Hoppa till navigering Hoppa till sök

Inom algebra och talteori är divisionsalgoritmen 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

.[1]

Talet kallas (heltals)kvot (även principal kvot) och talet kallas (principal) rest. Förfarandet kallas division med rest (även euklidisk division).

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

.[2][3]

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

Divisionsalgoritmer 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.[2]

Divisionsalgoritmen är, namnet till trots, en matematisk sats och skall inte förväxlas med algoritmer för beräkning av kvoter (som exempelvis "lång division" - vilken förvisso bygger på upprepad tillämpning av divisionsalgoritmen...).

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.

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ Juliusz Brzezinski, Delbarhet och primtal, sid. 4 och 24.
  2. ^ [a b] Petter Brändén, 2018, Polynom och gaussiska heltal[död länk].
  3. ^ Lars-Åke Lindahl, 2012, Elementär talteori, sid. 39.
  4. ^ Mikael Forsberg, 2014, Komplexa tal och polynom - en introduktion, sid. 33.