L'algorisme d'Euclides

El màxim comú divisor entre dos nombres enters és el major nombre que divideix a tots dos.

Exemple

Per exemple, si es té el $20$ i el $16$ , el màxim comú divisor entre els dos és $4$ , ja que:

Els divisors de $20$ són: $1$ , $2$ , $4$ , $5$ , $10$ i $20$

Els divisors de $16$ són: $1$ , $2$ , $4$ i $16$

Els nombres que divideixen tant a $20$ com a $16$ són: $1, 2$ i $4$ , i clarament el major és $4$ . Així doncs, el màxim comú divisor entre $20$ i $16$ és $4$ , i s'escriu $m c d (20, 16) = 4$ .

No obstant això, calcular el màxim comú divisor entre dos nombres pot resultar molt complicat per nombres molt grans.

Per fer-ho, hi ha un mètode conegut pel nom de algorisme d'Euclides, que, encara que al principi pot semblar una mica estrany, quan s'agafa pràctica resulta molt més còmode i senzill que altres mètodes.

A més, per si fos poc, també serveix per a resoldre equacions diofàntiques

L'algorisme d'Euclides es basa en la definició de tres seqüències de nombres: la primera es dirà $r_{j}$ , la segona es dirà $s_{j}$ i la tercera $t_{j}$ .

L'algorisme d'Euclides consisteix a realitzar els següents passos:

S'agafen dos nombres: $a \geq 0$ , $b > 0$ . Es vol calcular $m c d (a, b)$ (el màxim comú divisor entre $a$ i $b$ ). Per exemple, es podria prendre $a = 10$ i $b = 5$ .
Es defineix: $\begin{array}{rclrcl} r_{0} & = & a, & r_{1} & = & b \\ s_{0} & = & 1, & s_{1} & = & 0 \\ t_{0} & = & 0, & t_{1} & = & 1 \end{array}$ Per exemple amb $a = 10$ i $b = 5$ , es tindria: : $\begin{array}{rclrcl} r_{0} & = & 10, & r_{1} & = & 5 \\ s_{0} & = & 1, & s_{1} & = & 0 \\ t_{0} & = & 0, & t_{1} & = & 1 \end{array}$
Per $j \geq 2$ , fem la divisió entera de $r_{j - a}$ entre $r_{j - 1}$ . Al resultat en diem $q_{j - 1}$ i al residu $r_{j}$ .

En l'exemple anterior, si volem calcular $r_{2}$ i $q_{1}$ (és a dir, $j = 2$ ) s'ha de fer la divisió entera entre $r_{0} = 10$ i $r_{1} = 5$ . Està clar que el resultat de la divisió és $2$ amb residu $0$ , i per tant escrivim $q_{1} = 2$ i $r_{2} = 0$ .

Ara, es defineix $\begin{array}{rcl} s_{j} & = & s_{j - 2} - s_{j - 1} \cdot q_{j - 1} \\ t_{j} & = & t_{j - 2} - t_{j - 1} \cdot q_{j - 1} \end{array}$ En l'exemple anterior es tindria: $\begin{array}{rcl} s_{2} & = & s_{0} - s_{1} \cdot q_{1} = 1 - 0 \cdot 1 = 1 \\ t_{2} & = & t_{0} - t_{1} \cdot q_{1} = 0 - 1 \cdot 2 = - 2 \end{array}$
Quan hi hagi un $r_{n + 1} = 0$ , llavors tenim que $m c d (a, b) = r_{n}$ (És a dir, el del pas anterior!). A més, també es compleix que: $m c d (a, b) = s_{n} \cdot a + t_{n} \cdot b$ ( $s_{n}$ i $t_{n}$ són també els del pas anterior).

Tornant a l'exemple que s'ha tractat en els passos previs, s'ha vist que per $j = 2$ ja es compleix que $r_{2} = 0$ . Per tant, el màxim comú divisor entre $10$ i $5$ és $r_{1}$ (el del pas anterior), és a dir $5$ .

A més l'última igualtat ens diu que: $m c d (10, 5) = s_{1} \cdot 10 + t_{1} \cdot 5 = 0 \cdot 10 + 1 \cdot 5 = 0$