Algoritmo de Euclides 
Se \( a = b+c\), qual é a relação entre os divisores comuns de \(a\) e \(b\) e os divisores comuns de \(b\) e \(c\)?
Vamos então ver o
que acontece se \(a=b+c\).
Se \(d\)
é um divisor comum de \(b\)
e \(c\),
existem \(k\)
tal que \(b=kd\)
e \(l\)
tal que \(c=ld\).
Então: \[a=kd+ld=(k+l)d,\] portanto, \(d\)
é um divisor de \(a\)
(e, portanto, é um divisor comum de \(a\)
e \(b\),
pois \(d\)
já era divisor de \(b\)).
Então, os divisores
comuns de \(b\)
e \(c\)
são todos divisores comuns de \(a\)
e \(b\).
O que é que se passa
se \(d\)
é um divisor comum de \(a\)
e \(b\)?
Se \(a=kd\)
e \(b=ld\),
então \(kd=ld+c\)
(porque \(a=b+c\)),
portanto \(c=(k-l)d\),
isto é, \(d\)
é um divisor de \(c\)
(e, portanto, divisor comum de \(b\)
e \(c\)).
Conclusão: os divisores comuns de \(a\) e \(b\) são exactamente os divisores comuns de \(b\) e \(c\) (e, portanto, em particular o máximo divisor comum de \(a\) e \(b\) é o máximo divisor comum de \(b\) e \(c\) ).
