L'algorisme d'Euclides

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

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 $mcd(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 $mcd(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 $mcd(a,b)=r_n$ (És a dir, el del pas anterior!). A més, també es compleix que: $mcd(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: $$mcd(10,5)=s_1 \cdot 10 + t_1 \cdot 5= 0 \cdot 10 +1 \cdot 5=0$$