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.




Cursos

Aulas

01 Máximo divisor comum (mdc) de modo rápido, com Euclides
02 Frações e mínimo múltiplo comum (mmc) no Egito Antigo
03 Os noves fora dos antigos e a aritmética do jovem Gauss
04 A raiz quadrada irracional e suas aproximações
05 Infinitas triplas de Pitágoras e nenhuma de Fermat
06 Complexos no plano de Argand e Gauss
07 Questões resolvidas de Vestibulares
08 Transformar problemas práticos em Matemática
09 Raízes e fatorações de polinômios
10 Discriminante e raízes duplas de equações cúbicas
11 Questões analisadas de Vestibulares
12 Intersecção de retas e planos e sistemas lineares
13 Escalonamento em sistemas de equações lineares, segundo Gauss
14 Diversas operações com matrizes
15 Determinantes de matrizes, com ou sem a Regra de Sarrus
16 Cálculo de determinantes de modo rápido
17 Mais questões resolvidas de Vestibulares
18 Da passagem de Tales pelo Egito
19 Leis de senos e cossenos e as paredes fora de esquadro
20 Seno e cosseno de somas com um pouco de Geometria
21 Geometria das pirâmides truncadas, segundo os Egípcios
22 Retas por dois pontos, coeficiente angular e além
23 Retas tangentes às parábolas, segundo Descartes
24 Geometria analítica, de Descartes a Groebner
25 Questões selecionadas de Vestibulares
26 Progressões aritméticas e geométricas
27 As medidas do círculo e da elipse
28 Resolução de questões de Vestibulares
29 Mirífico logaritmo
30 Raiz quadrada e cálculo de logaritmos, segundo Briggs
31 Aplicações de logaritmos e exponenciais nas Ciências
32 Questões compiladas de Vestibulares
33 Primeiras idéias combinatórias
34 Combinações, binômios e triângulos, segundo Pascal e Newton
35 Grafos planares e a necessidade de viadutos, segundo Kuratowski
36 Seguidores, fofoqueiros e grafos orientados
37 Praticar com questões de Vestibulares
38 Reta tangente e velocidade instantânea, segundo Newton
39 Derivada e reta tangente de um gráfico
40 Derivar é quase sempre um processo mecânico
41 Questões escolhidas de Vestibulares
42 Postulados como regras de um jogo e a Geometria de Poincaré
43 Postulado Euclidiano da paralela e a Geometria de Poincaré
44 Matemática das projeções, segundo Desargues e Poncelet
45 Referências

Tópicos