Algoritmo de Euclides

Para determinar o MDC de dois números, usaremos um método chamado algoritmo de Euclides: (Não vamos demonstrar a validade desse algortimo, apenas admitiremos que ele funciona)

Eis o princípio: Dadas dois inteiros positivos $a$ e $b$ , começa-se por testar $b$ é nulo. Se for, então o MCD é igual à $a$ . Se não for, calcula-se $r$ , o resto da divisão de $a$ por $b$ . Substitui-se $a$ por $b$ , e $b$ por $r$ , e recomeça-se o método.
Calcular, por exemplo, o MDC de 2160 e 888 por este algoritmo se dará nas seguintes etapas:

$$\begin{array}{ccc} a & b & r\\ 2160 & 888 & 384 \\ 888 & 38... ...\ 384 & 120 & 24 \\ 120 & 24 & 0 \\ 24 & 0 & \\ \end{array}$$

O MDC de 2160 e 888 é 24. Ele é o maior número inteiro que divide aqueles dois outros.
(De fato 2160 = 24 x 90 e 888 = 24 x 37)
O MDC é com efeito o último resto não nulo.