Euklides algoritm

Euklides algoritm är en algoritm för att bestämma största gemensamma delare till två heltal. Det är en av de äldsta kända algoritmerna och beskrivs i Euklides Elementa. Algoritmen kräver inte att man kan dela upp talen i faktorer.

Algoritmen kan beskrivas på följande sätt:

1. Två heltal a och b, där a > b är givna.
2. Om b = 0 är algoritmen klar och svaret är a.
3. I annat fall beräknas c, resten när man delat a med b.
4. sätt a = b, b = c och börja om från steg 2 igen, (a får det värde b har och b får det värde c har).

Exempel 1

Finn den största gemensamma delaren till 1071 och 1029.

<math>

\begin{array}{l|ccc|l} \textrm{steg} & a & b & c & \textrm{kommentar} \\ \hline 1,2 & 1071 & 1029 & - &\\ 3 & 1071 & 1029 & 42 & 1071 = 1 \cdot 1029 + 42\\ 4,2 & 1029 & 42 & - & b \neq 0 \\ 3 & 1029 & 42 & 21 & 1029 = 24 \cdot 42 + 21 \\ 4,2 & 42 & 21 & - & b \neq 0 \\ 3 & 42 & 21 & 0 & 42 = 2 \cdot 21 \\ 4,2 & 21 & 0 & - & b = 0 \\ \end{array} </math> Den största gemensamma delaren är alltså 21.

Kortare skrivet:

1071 = 1 · 1029 + 42

1029 = 24 · 42 + 21

42 = 2 · 21 + 0, så svaret är 21.

En snabb kontroll bekräftar att 1071 = 51 · 21 och 1029 = 49 · 21.

En följd av Euklides algoritm är Bézouts identitet, som säger att den största gemensamma delaren till två tal a,b kan skrivas som en linjärkombination av talen ax+by (x,y heltal). Genom att lösa ut resterna och köra algoritmen baklänges bestämmer man x och y. I exemplet ovan:

<math>21 = 1029 - 24 \cdot 42</math>

<math>42 = 1071 - 1 \cdot 1029 </math>

<math>\Rightarrow 21 = 1029 - 24 \cdot 42 = 1029 - 24 \cdot (1071 - 1 \cdot 1029) = 1029 \cdot 25 - 1071 \cdot 24</math>

Detta kan användas vid lösning av den diofantiska ekvationen ax + by = c.

Exempel 2

Nedan följer en alternativ metod som fungerar lika bra som ovan. Med funktionen frac menas decimaldelen av talet. Om <math>\!x=1.5</math> så är <math>\mbox{frac}\left(x\right)=0.5</math> och om <math>x\in\mathbb{Z}</math>, så är decimaldelen noll, det vill säga <math>\mbox{frac}\left(x\right)=0</math>.

<math>a=1071</math>

<math>b=1029</math>

<math>c=1029\cdot \mbox{frac}\left(\frac{1071}{1029}\right)=42</math>

<math>a=b=1029</math>

<math>b=c=42</math>

<math>c=42\cdot\mbox{frac}\left(\frac{1029}{42}\right)=21</math>

<math>a=b=42</math>

<math>b=c=21</math>

<math>c=21\cdot\mbox{frac}\left(\frac{42}{21}\right)=0</math>

<math>a=b=21</math>

<math>b=c=0</math>

Bevis för Euklides algoritm

Euklides använde sig av ett så kallat motsägelsebevis. Han utgick från att det finns ett tal c som delar b och r, men inte a. Och att divisionen <math> {\frac a b} </math> blir <math> a=bq+r </math>

<math>\ c|b </math>

<math>\ c|r </math>

<math>\ c|bq </math>

<math>\ c|bq+r </math>

Då måste alltså alla tal som delar r och b dela a

<math>\ c|a </math>

Så sgd(a, b)=sgd(b, r)

Generalisering av Euklides algoritm

Euklides algoritm kan utvidgas till att operera på andra ringar än heltalen, som ovan. Ringar i vilka Euklides algoritm kan användas kallas Euklidiska ringar. Exempel på Euklidiska ringar är de Gaussiska heltalen och vissa polynomringar.

Externa länkar

• Fil:Commons-logo.svg Wikimedia Commons har media som rör Euklides algoritm.
  Bilder & media