Resolvendo combinacoes lineares com o teorema de bezout
Voc provavelmente encontrou isso numa disciplina de teoria dos numeros ou matematica discreta e achou confuso no começo. O teorema de bezout diz que dados dois inteiros a e b, existe um inteiro d igual ao mdc(a,b) que pode ser escrito como combinacao linear desses dois numeros. Em outras palavras, existem inteiros x e y tais que ax + by = d. Isso é tudo. Nao tem mistério.
Como usar o teorema de bezout na pratica
O metodo mais comum e usar o algoritmo de Euclides estendido. Voce divide, pega o resto, repete ate chegar a remainder zero, e entao volta fazendo substituicao reversa para expressar o mdc como combinacao linear. Funciona pra qualquer par de inteiros positivos. Deixa eu mostrar com um exemplo rapido. Pegue a = 252 e b = 105. O Euclides normal:
252 = 2 * 105 + 42 105 = 2 * 42 + 21
42 = 2 * 21 + 0 O mdc é 21. Agora a parte que as vezes as pessoas travam: voltar atrás. Da segunda equacao, isolamos 21 = 105 - 2 * 42. Da primeira, 42 = 252 - 2 * 105. Substituindo, chegamos a 21 = 3 * 105 - 1 * 252. Entao x = -1 e y = 3. Conferindo: -252 + 315 = 21. Fechou.
Na pratica, eu costumo fazer isso de forma organizada num caderno, escrevendo cada resto em função dos dois numeros originais conforme eu prossigo pelo algoritmo. Assim eu não preciso fazer a substituicao reversa de cabeça depois e reduz o risco de erro aritmético. E mais rápido também. Uma aplicação direta muito usada é resolver congruências lineares. Se voce precisa achar o inverso multiplicativo de a modulo m, onde mdc(a,m) = 1, o teorema de bezout garante que existe tal inverso e o algoritmo estendido te entrega o valor. Isso é fundamental em criptografia RSA, por exemplo. O inverso é o x que satisfaz ax 1 (mod m).
👉 Clique no botão abaixo para saber mais sobre o assunto!
O problema que eu encontrei e como resolvi
Num projeto pratico envolvendo criptografia, eu precisei calcular inversos modulares de numeros grandes em Python. O algoritmo de Euclides estendido funciona, mas quando os numeros entram na casa de centenas de digitos, fazer a substituicao reversa manualmente é inviável. Eu escrevi uma funcao recursiva que implementa o algoritmo estendido de forma iterativa, retornando (mdc, x, y). O código ficou mais ou menos assim:
def bezout(a, b):
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
quociente = old_r // r
old_r, r = r, old_r - quociente * r
old_s, s = s, old_s - quociente * s
old_t, t = t, old_t - quociente * t
return old_r, old_s, old_t
Isso retorna mdc, x e y. A vantagem é que funciona com numeros enormes sem depender de recursão profunda, que poderia estourar a pilha em Python. E rodando em testes com numeros de 512 bits, o tempo de execucao fica na casa dos microssegundos.
Coisas que os livros nao costumam enfatizar
A primeira é que os coeficientes x e y nao sao unicos. Se (x, y) é uma solucao, entao (x + k*b/d, y - k*a/d) também é para qualquer inteiro k. Isso importa quando voce precisa de uma solucao positiva ou dentro de certo intervalo, como em problemas de programacao competitiva. Voce calcula uma solucao com o algoritmo estendido e depois ajusta com esse parametro k. A segunda é que o teorema so se aplica a aneis euclidianos no sentido amplo. Em Z ele vale perfeitamente. Mas se voce sair dos inteiros e for para aneis como Z[i] ou polinomios sobre um corpo, a ideia se generaliza, embora o algoritmo tenha que ser adaptado. Nao adianta tentar aplicar a versao classica de forma cega fora de Z.
Outro ponto: se mdc(a,b) = d e d não divide c, entao a equacao ax + by = c nao tem solucao inteira. Isso e direto do teorema. Muita gente esquece de checar isso antes de gastar tempo tentando encontrar x e y.
Limitacoes e alternativas
O algoritmo de Euclides estendido é eficiente, mas tem seus problemas. O principal é que, em implementacoes ingenuas, a substituicao reversa recursiva pode causar estouro de pilha para numeros muito grandes. A versao iterativa que mostrei acima resolve isso. Outra limitacao é que o algoritmo opera em Z, entao se voce esta trabalhando com multipolos ou outros aneis, precisa de algo diferente, como o algoritmo de pseudo-divisao para polinomios. Para calculos praticos em Python, a funcao pow(a, -1, m) ja calcula inverso modular diretamente a partir da versao 3.8. Por tras dos panos, ela tambem usa uma variante do algoritmo de Euclides estendido, entao voces estão usando o teorema de bezout sem saber. Em C++ ou Java, voce normalmente implementa a versao iterativa e chama quando precisa.
Se voce ta lidando com numeros extremamente grandes e performance é crítica, existem otimizacoes como o algoritmo de Euclides rapido (binary GCD ou variantes com divisao subsequente), mas para a maioria dos casos o Euclides estendido classico é suficiente e bem compreensivel. O teorema de bezout é uma daquelas ferramentas basicas que parecem simples mas aparecem em lugares inesperados. A melhor maneira de dominar é realmente executar o algoritmo varias vezes com numeros pequenos ate o processo vir automatico, e depois aplicar em problemas reais como inversos modulares e resolucao de equacoes diofanticas lineares.
