O máximo divisor comum e o mínimo múltiplo comum

Vista aérea de Königsberg (atual Kaliningrado) e suas pontes - mapa elaborado por Georg Braun & Frans Hogenberg, 1582

Pouco se sabe sobre o nascimento, vida e morte de Euclides, exceto que trabalhou no Museu de Alexandria durante o reinado de Ptolomeu I, no período compreendido entre 323 e 283 a.C. e que sua obra-prima, Elementos, foi o tratado matemático mais influente de todos os tempos, servindo como material de referência no ensino, principalmente de geometria, desde a época de sua publicação até o início do século XX de nossa era, e ainda hoje influencia qualquer autor que escreva sobre esse assunto, no mínimo ao lhe fazer menção. Mesmo levando-se em consideração que muitos dos resultados apresentados na obra Elementos tenham sido elaborados por matemáticos que o antecederam, o mérito de Euclides reside no fato de demonstrá-los de um modo simples e logicamente coerente, facilitando o entendimento e o seu uso, o que inclui um rigoroso sistema de provas matemáticas que subsistiram como a base da matemática por 23 séculos. Apesar de mais conhecido pela abordagem geométrica, o Elementos também lida com a teoria dos números, e de maior interesse neste capítulo, com o máximo divisor comum, também chamado “algoritmo de Euclides”. Este algoritmo é apresentado no livro VII (proposições 1 e 2), formulado para números inteiros, e no livro X (proposições 2 e 3), formulado para magnitudes de segmentos de reta. Para entender como funciona o algoritmo, façamos a seguinte operação aritmética: 748 ÷ 85, onde o objetivo é encontrar um número que divida, sem gerar resto, tanto o 748 quanto o 85, ou seja, achar o máximo divisor comum entre os dois números. O resultado inicial dessa divisão é:



Até aqui, sem novidades: o dividendo 748, dividido por 85, resulta 8. O produto 8 × 85 = 680, que subtraído de 748 gera como resto: 68. Como a divisão não foi exata, o algoritmo entra agora em operação, transformando o divisor 85 em dividendo, e o resto 68 em divisor. Repetindo a divisão, temos:



Mais uma vez, a divisão não resultou exata; então, o divisor 68 vira dividendo e o resto 17 fica como divisor. Dividindo, obtemos:

Agora, o resultado da divisão foi exato, ou seja, sem resto. Logo, o divisor 17 é o máximo divisor comum entre 748 e 85. Veja que: 748 ÷ 17 = 44 (sem resto) e 85 ÷ 17 = 5 (sem resto). Perceba que o máximo divisor comum não funciona se tanto o dividendo quanto o divisor forem primos entre si, porque neste caso o máximo divisor comum desses números é o 1. Já na versão geométrica grega visava-se, com o algoritmo de Euclides, a comensurabilidade entre dois segmentos; diz-se que dois segmentos AB e CD são comensuráveis quando existe um terceiro segmento EF que cabe um número exato de vezes tanto em AB quanto em CD. Por exemplo, suponha que temos um segmento AB de magnitude 35 e outro segmento, CD, de magnitude 20. Qual é a magnitude de um terceiro segmento EF que caiba um número exato de vezes tanto em AB quanto em CD? Primeiro, desenhamos os segmentos de reta AB e CD com suas respectivas magnitudes:



Para encontrarmos a maior medida comum entre esses dois segmentos, subtraímos o menor (CD) tantas vezes quanto possível do maior (AB). Do exemplo, só é possível retirar CD uma vez de AB, restando um segmento de reta PQ de magnitude 15 (35 – 20) dessa subtração, conforme abaixo:



Como há um resto, repetimos o processo, retirando-se PQ tantas vezes quanto possível de CD. Da figura abaixo, observa-se que o segmento PQ só cabe uma única vez dentro do segmento CD, restando um novo segmento EF, de magnitude 5 (20 – 15):



Novamente, há um resto, e repetimos o processo, retirando-se EF tantas vezes quanto possível de PQ. Da figura a seguir, nota-se que o segmento EF cabe 3 vezes exatas dentro de PQ, sem resto:



Logo, o segmento EF, de magnitude 5, é a maior medida comum entre os segmentos AB e CD. De fato, o segmento EF cabe 7 vezes exatas dentro do segmento AB (35 ÷ 5 = 7) e cabe 4 vezes exatas dentro do segmento CD (20 ÷ 5 = 4).

Representação artísitica de Euclides - pintura a óleo de Antônio Cifrondi (séc. XVII). Coleção da Fondazione Cariplo, Milão

É interessante o fato de que o algoritmo de Euclides foi desenvolvido de forma independente na Índia pelo matemático e astrônomo hindu Aryabhata, que viveu entre 473 e 550 d.C., portanto, durante a dinastia Gupta. Aryabhata escreveu ao menos dois livros: o Aryabhatasiddhanta (Soluções de Aryabhata), conhecido apenas por referências de outros autores, e o Aryabathiya, este um tratado contendo teorias matemáticas e astronômicas, entre as quais uma em que a Terra é apresentada como girando em seu próprio eixo e as órbitas dos planetas sendo tomadas em relação ao Sol. Entre as teorias matemáticas abordadas nessa obra, há a descrição de um algoritmo relacionado com a astronomia e a elaboração de calendários precisos, que Aryabhata denominava kuttaka, cujo significado é “pulverizador”, devido à sua eficácia na resolução dos problemas abordados, e que nada mais é que o próprio algoritmo de Euclides. Também na China esse algoritmo desenvolveu-se de forma independente, aparecendo em sua forma completa na obra Shu shu Jiu zhang (Tratado matemático em nove partes) em 1.247 d.C., de autoria do matemático chinês Quin Jiushao.

Página do Shushu Jiuzhang, na edição de 1.782 d.C.

Curiosamente, foi Jiushao quem também introduziu o símbolo zero na matemática chinesa. Por outro lado, na Europa renascentista, o algoritmo de Euclides aparece pela primeira vez somente em 1.624, na obra Problèmes plaisants et délectables (ou "Problemas aprazíveis e deleitáveis"), de autoria do teólogo e matemático francês Bachet de Méziriac, onde questiona em sua proposição XVIII:

"Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d’iceux, surpassant de l’unité un multiple de l’autre"

Cuja tradução seria:

"Dados dois números primos entre si, encontrar o mínimo múltiplo comum entre ambos, superando de uma unidade um múltiplo do outro".

Veremos mais adiante neste capítulo que o mínimo múltiplo comum nada mais é que um desdobramento do máximo divisor comum. Existe uma técnica de extração do máximo divisor comum entre dois números inteiros não primos entre si, que é comumente ensinada na escola, que faz uso da decomposição em fatores primos. Vejamos um exemplo desta técnica, procurando o máximo divisor comum entre 348 e 156. Primeiro, vamos decompor o número 348 através de sucessivas divisões em seus fatores primos até que a divisão resulte 1, começando a divisão por 2 em ordem crescente, pois 2 é primo e 348 é múltiplo de 2:



A divisão correu bem até chegarmos a 87, que não é múltiplo de 2;  porém, este número é múltiplo de 3, pois a soma de seus algarismos resulta num número múltiplo de 3 (veja que 8 + 7 = 15 e 15 é múltiplo de 3). Então, prosseguimos com a divisão, assim:



Veja que o número 29 é primo. Logo, ele só é divisível por ele mesmo e por 1; sendo dividido por ele mesmo, o resultado das divisões sucessivas resulta em 1, encerrando o processo de decomposição do número 348 por seus fatores primos. Faremos o mesmo procedimento para o número 156, começando sua divisão por 2, já que 156 é um número par:



O número 39 não é múltiplo de 2, mas é múltiplo de 3, pois a soma de seus algarismos (3 + 9 = 12) resulta num número múltiplo de 3. Prosseguimos, assim, com esta divisão:



Note que 13 também é um número primo; então, encerramos a decomposição do 156, reduzindo sua divisão a 1 com esta última decomposição. O resultado da decomposição, para ambos os números, é:

Como última etapa, selecionamos os fatores primos comuns a ambos os números. Neste caso, os fatores 2 × 2 × 3 são comuns tanto ao 348 quanto ao 156:



Logo, o máximo divisor comum entre eles é o produto destes fatores, ou seja: 2 × 2 × 3 = 12. Para que este método funcione de maneira adequada, é preciso lembrar-se dos critérios de divisibilidade, que estão formulados abaixo:

Critério de divisibilidade por 2:
Enunciado: Todo número par é múltiplo de 2.

Critério de divisibilidade por 3:

Enunciado: Um número é divisível por 3 se e somente se a soma dos seus algarismos é divisível por 3. Por exemplo, 432 é múltiplo de 3 pois: 4 + 3 + 2 = 9, e o número 9 é múltiplo de 3.

Critério de divisibilidade por 4:

Enunciado: Um número é divisível por 4 se os dois últimos algarismos do número for divisível por 4. Por exemplo, o número 1548 é múltiplo de 4, pois os dois últimos algarismos desse número (48) formam um número múltiplo de 4.

Critério de divisibilidade por 5:

Enunciado: Um número é múltiplo de 5 se e somente se ele termina em 0 ou 5. Por exemplo, o número 9775 é múltiplo de 5, pois termina em 5.

Critério de divisibilidade por 6:

Enunciado: Um número é múltiplo de 6 se for simultaneamente múltiplo de 2 e de 3. Por exemplo, o número 432 é múltiplo de 2 e de 3, portanto, também é múltiplo de 6.

Critério de divisibilidade por 7:

Enunciado: Um número é múltiplo de 7 se, ao multiplicar por 2 o último algarismo desse número, e subtrair este resultado do número inicial sem o último algarismo, resulta um múltiplo de 7. Por exemplo, o número 7203 é múltiplo de 7, pois, seguindo o critério, temos:

• Último algarismo: 3;
• Multiplicar o último algarismo por 2: 3 × 2 = 6;
• Subtrair este resultado do número inicial sem o último algarismo: 702 – 6 = 714. Repetir o processo para 714;
• Último algarismo: 4;
• Multiplicar o último algarismo por 2: 4 × 2 = 8;
• Subtrair este resultado do número inicial sem o último algarismo: 71 – 8 = 63.

Como 63 é múltiplo de 7 (pois 7 × 9 = 63), podemos finalizar a verificação.

Critério de divisibilidade por 8:

Enunciado: Um número é divisível por 8 se os três últimos algarismos do número for divisível por 4. Por exemplo, o número 3272 é múltiplo de 4, pois os três últimos algarismos desse número (272) formam um número múltiplo de 8.

Critério de divisibilidade por 9:

Enunciado: Um número é divisível por 9 se e somente se a soma dos seus algarismos é divisível por 9. Por exemplo, 891 é múltiplo de 9 pois: 8 + 9 + 1 = 18, e 18 é múltiplo de 9.

Critério de divisibilidade por 11:

Enunciado: Um número é divisível por 11 se – começando da esquerda para a direita – a soma dos algarismos de ordem par desse número, subtraídos da soma dos algarismos de ordem ímpar (ou vice-versa), for igual a zero ou igual a um número múltiplo de 11. Por exemplo, 2376 é múltiplo de 11, pois os algarismos de ordem par (da esquerda para a direita) são o 2 e o 7, cuja soma é 9, e a soma dos algarismos de ordem ímpar são o 3 e o 6, cuja soma também é 9. A subtração desses dois resultados é: 9 – 9 = 0. Logo, 2376 é múltiplo de 11.

Critério de divisibilidade por 12:

Enunciado: Um número é divisível por 12 se simultaneamente for divisível por 3 e por 4. Por exemplo, 3252 é múltiplo de 3, pois: 3 + 2 + 5 + 2  = 12; por outro lado, 52 é múltiplo de 4. Logo, 3252 é um número múltiplo de 12.

Critério de divisibilidade por 13:

Enunciado: Um número é divisível por 13 se, o quádruplo do último algarismo, somado ao restante dos algarismos, for um número múltiplo de 13. Por exemplo, o número 975 é múltiplo de 13, pois:

• 97 + (4 × 5) = 117; Repetindo o processo para o número resultante, temos:
• 11 + (4 × 7) = 39.

Como 39 é múltiplo de 13, logo 975 também é múltiplo de 13. O critério de divisibilidade por 10 não foi indicado por que a base de nosso sistema numérico é decimal, o que torna esse critério intuitivo, mas poderíamos enunciar que qualquer número maior que 10, que termine com um ou mais algarismos zero, é múltiplo de 10. Bom, foi dito anteriormente que o algoritmo euclidiano também fornece uma maneira de calcular o mínimo múltiplo comum; de fato, dados dois números inteiros, o mínimo múltiplo comum entre ambos é dado pelo produto desses números, dividido pelo máximo divisor comum entre eles. Como fórmula, temos:

$$ m.m.c.\left ( a,b \right )=\frac{a\times b}{m.d.c.\left ( a,b \right )} $$

Nada melhor que um exemplo para entender como isso funciona. Vamos calcular o mínimo múltiplo comum entre 21 e 6. Usando o algoritmo de Euclides para encontrar o máximo divisor comum entre eles, temos:



Como a divisão gerou resto, o divisor 6 passa a dividendo e o resto 3 passa a divisor. Obtemos:



Como agora não houve resto, temos que o divisor 3 é o máximo divisor comum entre 21 e 6. Para achar o mínimo múltiplo comum, basta multiplicarmos 21 por 6 e dividir o resultado pelo máximo divisor comum, segundo a fórmula:

$$ m.m.c.\left ( 21, 6 \right )=\frac{21\times 6}{3}=\frac{126}{3}=42 $$

Também é possível calcular o mínimo múltiplo comum entre dois ou mais números utilizando-se a decomposição por fatores primos. Vejamos como isso funciona com outro exemplo: calcule o m.m.c. entre 45, 75 e 120. Primeiro, devemos decompor cada um dos números em seus fatores primos:



A decomposição dos números 45, 75 e 120 resulta:



Agora, selecionamos a maior quantidade de cada fator primo existente nas decomposições. Observe que o fator primo 2 aparece em maior quantidade na decomposição do 120; o fator primo 3 aparece em maior quantidade na decomposição do 45 e finalmente o fator primo 5 aparece duas vezes na decomposição do 75:



Logo, o mínimo múltiplo comum entre 45, 75 e 120 é o produto dos fatores primos resultantes da decomposição, cuja ocorrência se dá em maior quantidade, ou seja: 2 × 2 × 2 × 3 × 3 × 5 × 5 = 1800. Agora que já sabemos calcular o m.d.c. e o m.m.c., podemos começar a falar de um assunto fascinante: as frações.

Referências bibliográficas:

[1]	Wikipedia “Algoritmo de Euclides”, acessado em Setembro de 2.015. Site: https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides
[2]	Euclides "Os Elementos", tradução e introdução de Irineu Bicudo, Editora Unesp, 2009. ISBN: 978-85-7139-935-8
[3]	Claude-Gaspard Bachet, ”Problèmes plaisans et délectables”, 1.621.

Nota:

Esta postagem é parte integrante do e-book gratuito Matemática: Uma abordagem histórica - Volume 2. Caso queira obter um exemplar, clique aqui.