Dispositivo Prático para Expressar o MDC de Dois Números como Combinação Linear Deles José Paulo Q. Carneiro USU - Rio de Janeiro, RJ      Introdução 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.        Como  calcular os coeficientes  s e t   da referida combinação linear?   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. 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.     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  .   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.         Dispositivo prático   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.   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:   A partir daí, cada valor seguinte da coluna  “s, t”  vai sendo obtido de acordo com o seguinte esquema auto-explicativo:   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. 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:   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:              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 fez nos 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 (vamos chamá-los de  sn  e  tn ) vão-se complicando, e as primeiras são as seguintes (verifique!):