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.

$\begin{array}{ccccc}\text{steg}& a& b& c& \text{kommentar}\\ 1,2& 1071& 1029& -& \\ 3& 1071& 1029& 42& 1071=1\cdot 1029+42\\ 4,2& 1029& 42& -& b\ne 0\\ 3& 1029& 42& 21& 1029=24\cdot 42+21\\ 4,2& 42& 21& -& b\ne 0\\ 3& 42& 21& 0& 42=2\cdot 21\\ 4,2& 21& 0& -& b=0\end{array}$

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:

$21=1029-24\cdot 42$

$42=1071-1\cdot 1029$

$\Rightarrow 21=1029-24\cdot 42=1029-24\cdot (1071-1\cdot 1029)=1029\cdot 25-1071\cdot 24$

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 $x=1.5$ så är $\text{frac}\left(x\right)=0.5$ och om $x\in \mathbb{Z}$, så är decimaldelen noll, det vill säga $\text{frac}\left(x\right)=0$.

$a=1071$

$b=1029$

$c=1029\cdot \text{frac}\left(\frac{1071}{1029}\right)=42$

$a=b=1029$

$b=c=42$

$c=42\cdot \text{frac}\left(\frac{1029}{42}\right)=21$

$a=b=42$

$b=c=21$

$c=21\cdot \text{frac}\left(\frac{42}{21}\right)=0$

$a=b=21$

$b=c=0$

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 $\frac{a}{b}$ blir $a=bq+r$

$c|b$

$c|r$

$c|bq$

$c|bq+r$

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

$c|a$

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

• Mall:Commonscat