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$$$