Algoritmo estendido de euclides

Prévia do material em texto

O máximo divisor comum, mdc, de dois números inteiros é um tema que reaparece sempre em Matemática, 
tanto em nível básico quanto em assuntos mais avançados, e por essa razão já foi tratado diversas vezes na 
RPM (ver [2], [4] e [5]). 
Infelizmente, algumas abordagens do mdc no ensino fundamental omitem um fato notável a respeito do 
máximo divisor comum de dois inteiros: o de que é possível expressá-lo como uma combinação linear 
desses dois números, ou seja: se m for o mdc de a e b, então é possível determinar inteiros s e t tais 
que m = sa + tb. 
Essa propriedade do mdc é tão importante em Aritmética, que alguns autores a chamam de Teorema 
Fundamental da Teoria dos Números, mais usualmente conhecido como Teorema de Bézout (ver [1]). 
Para ilustrar a força desse teorema, podemos mencionar, por exemplo, que dele decorre imediatamente que 
dois inteiros a e b serão primos entre si se, e somente se, existirem inteiros s e t tais que . 
Um exercício interessante para o leitor é provar, a partir daí, o fato básico da Aritmética: se um inteiro for 
divisor de um produto de dois inteiros e for primo com um dos fatores, então será divisor do outro fator. 
Além disso, o artigo da RPM em [4] mostra como esse teorema é utilizado para resolver diversos 
problemas práticos de Aritmética. 
Alguns colegas talvez estranhem que se esteja falando em coisas tão importantes, mas que não constam dos 
programas usuais do ensino fundamental e médio, ainda que sejam muito mais simples do que outros 
tópicos de utilidade mais duvidosa que lá figuram. Bem, esperamos que essa situação mude, e isso só pode 
ser feito por nós, professores de Matemática. Ouçamos o que diz o prof. Miguel de Guzmán [3], atual 
presidente do Comitê Internacional de Ensino da Matemática: 
A Matemática dos séculos XIX e XX tem sido predominantemente a Matemática do contínuo... 
[mas] ... o advento dos computadores, com suas ... possibilidades para a modelização sem passar pela 
formulação matemática de feitio clássico, abriu uma multidão de campos diversos, com origem já 
não mais na Física, como os desenvolvimentos dos séculos anteriores, mas em muitas outras ciências, 
como a Economia, as ciências da organização, ... A predominância dos algoritmos discretos, usados 
nas ciências da computação e na informática, ... deu lugar a um deslocamento da ênfase da 
Matemática atual na direção da Matemática discreta, que apresenta alguns conteúdos suficientemente 
elementares para poderem figurar com sucesso em um programa inicial de Matemática. ... A teoria 
elementar dos números, que nunca chegou a desaparecer dos programas de alguns países, poderia ser 
uma delas. 
 
 
José Paulo Q. Carneiro 
USU −−−− Rio de Janeiro, RJ 
 Introdução 
Bom, em primeiro lugar, é claro, é preciso calcular o mdc dos números dados. Os métodos mais populares 
para isso são: a decomposição dos números em fatores primos e o algoritmo de Euclides. Qual é o mais 
indicado? Nesse caso, a experiência com números pequenos é enganadora, e pode dar a impressão (que já 
colhi de alguns professores) de que a decomposição em fatores primos é mais rápida ou mais prática. Isso 
só funciona bem para aqueles números que nós preparamos de antemão para nossos alunos (são sempre os 
mesmos, cheios de divisores e com fatores primos baixos: 360, 840, etc.). É só experimentar números um 
pouco maiores, com poucos fatores primos, para ver que o algoritmo de Euclides é muito mais eficiente (ver 
[2]). E, principalmente, o algoritmo de Euclides depende apenas de algo bastante elementar, a saber, 
divisões sucessivas com resto, e não −
 como o outro processo − de uma lista dada de números 
primos, o que pode ser simples para números pequenos, mas que pode representar um 
problema insolúvel para números grandes. De fato, dado um natural n, não é conhecido 
um método direto e eficiente para conhecer todos os primos que se deve testar como 
possíveis divisores de n. 
 Como calcular os coeficientes s e t da referida combinação linear? 
Dispositivo Prático para Expressar o MDC... 
��
 
 
 
Página 1 de 5RPM 37 - Dispositivo prático para expressar o MDC...
28/10/2009file://D:\37\6.htm
O algoritmo de Euclides é realmente o método mais rápido e conceitualmente mais rico dentre os 
conhecidos até hoje para calcular o mdc de dois números inteiros. E é admirável que seja o algoritmo mais 
antigo da história da Matemática. 
Pois bem, aqui está mais uma vantagem do algoritmo de Euclides: o melhor método para escrever o mdc de 
dois inteiros como combinação linear deles consiste em eliminar os restos nas equações lineares que surgem 
durante o algoritmo de Euclides. 
Exemplo: Tomemos e . Primeiramente, aplicamos o clássico algoritmo 
de Euclides. 
 
 
 
De fato: , que é o mdc de a e b. 
É possível perceber, ao trabalhar com exemplos, que as expressões de s e t só dependem dos quocientes 
obtidos durante o processo (no caso: 2, 13, 1, 2 e 6). Mas a experiência em sala de aula mostra que, quando 
se faz essa eliminação com números concretos – como fizemos aqui –, o iniciante se atrapalha, realizando 
indevidamente contas parciais, onde desaparecem os valores que não deveriam ser eliminados. 
Esse é mais um exemplo interessante em que as vezes, contrariamente ao que pode parecer regra geral, é 
mais fácil resolver um problema em sua versão literal do que com números concretos. 
Por outro lado, a expressão literal explícita dos coeficientes s e t em função dos quocientes não tem aspecto 
agradável. No entanto, uma lei de formação bem simples para os coeficientes permite produzir uma fórmula 
de recorrência e um dispositivo prático para aplicar essa fórmula. 
 
Antes de deduzir o dispositivo prático, vamos vê-lo funcionando no exemplo citado. Forma-se uma matriz 
com duas colunas, intituladas “q” e “s, t”. Primeiramente, preenche-se a coluna “q” com os quocientes 
obtidos no algoritmo de Euclides (desprezando o último, correspondente ao resto zero), na ordem contrária 
ao de seu aparecimento no algoritmo, e deixando em branco a primeira linha. 
A partir daí, cada valor seguinte da coluna “s, t” vai sendo obtido de acordo com o seguinte esquema auto-
 
As divisões efetuadas acarretam : 
 
 
 
 , 
 , 
 , , 
 e . 
Para expressar agora o mdc em função de a e b, 
despreza-se a última igualdade e eliminam-se os 
restos nas outras equações, começando de baixo 
para cima. Assim: 
 
3 = 27 2 x 12 = 27 2 x (363 13 x 27) = 
 
Ou seja, e . 
 Dispositivo prático 
Na coluna “s, t”, coloca-se o número 1 na primeira 
linha (é sempre 1 mesmo), e na segunda linha 
repete-se o valor do quociente que aparece ao seu 
lado na primeira coluna. No nosso exemplo, fica: 
 
Página 2 de 5RPM 37 - Dispositivo prático para expressar o MDC...
28/10/2009file://D:\37\6.htm
explicativo: 
Há a questão dos sinais, isto é, o esquema só fornece os valores absolutos de s e t. Para decidir sobre os 
sinais, aplica-se a seguinte regra: se o número de quocientes aproveitados (ou seja, o número de linhas 
preenchidas na coluna “q”) for ímpar, então s é positivo e t negativo; se for par, ocorrerá justamente o 
contrário: s é negativo e t é positivo. Deve ser notado que se pode também, em vez de decorar mais uma 
regra, experimentar, comparando os valores de e . No exemplo, e 
 , ficando claro que, para obter o mdc 3, é necessário fazer 
 e . 
Outro exemplo: e . 
 
 
Formando então a matriz: 
 
onde mdc (a, b). Os quocientes já foram numerados de trás para frente, isto é, o último quociente 
(correspondente ao resto 0) é q0, o penúltimo é q1, etc., e o primeiro é qn, para manter coerência com o 
dispositivo prático. 
Desprezando, como se feznos exemplos, o último quociente q0, vê-se, da primeira equação, que r1 pode 
ser escrito como uma combinação linear de a e b, ou seja, . Substituindo esse valor na 
penúltima equação, vê-se que r2 também pode ser escrito como uma combinação linear de a e b, a 
saber, . E assim por diante, para todos os r. Em particular, calcula-se m =
n =sa+tb. 
Repare que acabamos de demonstrar o Teorema Fundamental da Teoria dos Números. Se o leitor não 
estiver satisfeito com o “e assim por diante”, pode formalizar a demonstração por indução. É realmente 
fácil. Basta observar que uma combinação linear de combinações lineares de a e b é também uma 
combinação linear de a e b. 
Mas para sentir como vão ser essas expressões dos r em função de a e b, o leitor é convidado a fazer 
experimentos (literais) com diversos valores crescentes de n, o número de restos não nulos. À medida que 
aumenta o número n de quocientes aproveitados, as expressões para os coeficientes da combinação linear 
 
Observa-se que os dois últimos valores obtidos na 
segunda coluna são, justamente, em valor absoluto, 
s =85e t =539. Isso não é coincidência. Na realidade, 
essa matriz resume as contas que precisam ser feitas 
com os números relevantes que figuram no processo. 
 
Como agora o número de quocientes aproveitados é par, toma-
se: s = 29 e t =549, de modo que 
( 29) x 1741 + (594) x 85 = 50 489 + 40 490 = 1 
 Justificativa do dispositivo prático 
Vamos agora justificar o dispositivo prático, por 
meio da formulação literal do problema. 
Supondo inteiros, aplica-se o algoritmo 
de Euclides, encontrando: 
 
Página 3 de 5RPM 37 - Dispositivo prático para expressar o MDC...
28/10/2009file://D:\37\6.htm
(vamos chamá-los de sn e tn ) vão-se complicando, e as primeiras são as seguintes (verifique!): 
 
Página 4 de 5RPM 37 - Dispositivo prático para expressar o MDC...
28/10/2009file://D:\37\6.htm
A lei de formação é clara (e pode ser verificada por indução): 
 
com os valores iniciais: s1 = 1 e t1 = q1 . 
 
Observando que cada s repete o t anterior, basta trabalhar com os t e notar que, ao final do processo, o 
último valor é o t procurado, enquanto o penúltimo é o s. Foi por isso que introduzimos a coluna “s, t” na 
matriz da nossa regra prática. Além disso, levando em conta a alternância dos sinais, é suficiente lidar com 
os valores absolutos de t, tomando o cuidado de, no final, fazer a correção de sinal conveniente, conforme 
n seja par ou ímpar. Com essas providências, a lei de formação fica: 
 , 
que é justamente o que se fez na regra prática. 
Alguém pode ainda perguntar: quando se escreve o máximo divisor comum de dois inteiros como uma 
combinação linear deles, essa representação é única? A resposta é não (ver [4], para maiores detalhes). 
Uma vez encontrados s e t tais que , basta tomar um inteiro qualquer u, e também será 
verdade que , onde e , como pode ser verificado diretamente por 
substituição. 
Em nosso primeiro exemplo, tomando , temos: 
s' =85 +1143 =1228, enquanto t' = 539 7248 = 7728. 
Verificando: s'a +t'b= 1228 x7248 +( 7787) x1143= 
8900544 8900541 =3. 
 
Referências Bibliográficas 
[1] Brucheimer, M. & Arcavi, A. A visual approach to some elementary Number Theory. Mathematical Gazette, 79, 
pág. 471, Nov. 1995. 
[2] Carvalho, J. B. Pitombeira de. Euclides, Fibonacci e Lamé. Revista do Professor de Matemática, 24, pág. 32, 1993. 
[3] Guzman, Miguel de. Tendencias inovadoras en Educación Matemática. Olimpiada Matematica Argentina, 1992. 
[4] La Roque, Gilda & Pitombeira, J. B.. Uma equação diofantina e suas resoluções. Revista do Professor de 
Matemática, 19, pág. 39, 1991. 
[5] Oliveira, Z. C. Uma interpretação geométrica do mdc. Revista do Professor de Matemática, 29, pág. 24, 1995. 
[6] Ore, Oystein. Number Theory and its History. Mc-Graw-Hill, 1948. 
 
n s t 
1 1 
2 
 
3 
 
4 
 
... ... ... 
Página 5 de 5RPM 37 - Dispositivo prático para expressar o MDC...
28/10/2009file://D:\37\6.htm