Quando há muito a fazer, é preciso ser eficiente

Máximo divisor comum (mdc) de modo rápido, com Euclides

---

Nos Ensinos Fundamental e Médio, aprendemos a calcular o máximo divisor comum $\mbox{mdc}$ entre dois números Naturais.
Por exemplo,
\[\mbox{mdc}( 912 , 78) = 6\]
A explicação usualmente dada é que as fatorações em primos desses números são
\[\begin{cases} 7 8 = \underbrace{2\cdot 3}\cdot 13 \\\\
9 1 2 = 2\cdot 2 \cdot 2 \cdot\underbrace{ 2 \cdot 3} \cdot 19\end{cases}\]
e mostram o divisor comum $6$ (destacado) como o maior possível.
Para obter a primeira fatoração, foi preciso fazer $3$ divisões; a segunda fatoração exigiu mais $6$ divisões. E ainda foi preciso o conhecimento prévio dos números primos até $19$.
Neste post vamos:
i) explicar um modo muito mais rápido de calcular o $\mbox{mdc}$, chamado de algoritmo de Euclides (c. 300 A.C. ), e que não exige conhecer os primos. No exemplo acima, o algorimo precisa de apenas $4$ divisões.
ii) vamos implementar o algoritmo em uma hipercalculadora, que mostra cada etapa de divisão.

---