Bézout e algoritmo de Euclides
O algoritmo de Euclides serve para encontrar o MDC de dois números sem listar todos os divisores. A ideia é substituir o par original por divisões sucessivas: o MDC não muda quando trocamos o número maior pelo resto da divisão.
Por exemplo, para comparar 18 e 12, fazemos 18 = 12 · 1 + 6. Como o resto é 6, agora basta calcular mdc(12,6), que é 6.
A identidade de Bézout aprofunda essa ideia: ela diz que o MDC pode ser escrito como combinação linear dos dois números. Combinação linear significa uma soma do tipo ax + by, com coeficientes inteiros.
Use Euclides quando precisar calcular MDC rapidamente. Use Bézout quando precisar escrever esse MDC como combinação linear, especialmente em diofantinas e inverso modular.
Função phi de Euler
A função φ(n) conta quantos números de 1 até n são coprimos com n. Dois números são coprimos quando o MDC entre eles é 1.
Listar funciona para números pequenos, mas fica ruim para números grandes. Por isso usamos uma fórmula baseada na fatoração em primos.
A fórmula usa apenas os primos diferentes da fatoração. Os expoentes ajudam a montar n, mas os fatores da fórmula usam p1, p2, ..., pk.
A função phi não conta divisores de n. Ela conta números que não compartilham fatores com n.
Use φ(n) quando a pergunta envolver coprimos ou quando for aplicar o teorema de Euler.
Pequeno teorema de Fermat
O pequeno teorema de Fermat ajuda a reduzir potências grandes quando o módulo é primo. Módulo primo significa que estamos trabalhando com restos na divisão por um número primo, como 5, 7, 11 ou 13.
Em palavras: quando a base não é múltipla do primo p, a potência ap-1 deixa resto 1 na divisão por p.
Use Fermat quando o módulo for primo e a base não for múltipla desse primo.
Teorema de Euler
O teorema de Euler é uma versão mais geral do pequeno teorema de Fermat. Fermat funciona com módulo primo; Euler funciona com muitos módulos compostos, desde que mdc(a,n)=1.
Em palavras: se a e n não compartilham fatores, podemos reduzir potências usando φ(n).
Use Euler quando o módulo não precisa ser primo, mas a base deve ser coprima com o módulo.
Como usar esses teoremas
O ponto mais importante é escolher a ferramenta pelo formato do problema. Se a questão pede MDC, pense em Euclides. Se pede combinação inteira, pense em Bézout. Se pede potência grande módulo primo, pense em Fermat. Se o módulo é composto, verifique se Euler pode entrar.
| Ferramenta | Ideia simples | Quando usar |
|---|---|---|
| Euclides | calcula o MDC por divisões sucessivas | quando precisar calcular MDC sem listar divisores |
| Bézout | escreve o MDC como combinação linear | quando precisar escrever ax+by=mdc(a,b) |
| Phi de Euler | conta números coprimos com n | quando precisar contar coprimos ou preparar o teorema de Euler |
| Fermat | reduz potências grandes módulo primo | quando o módulo é primo e a base não é múltipla dele |
| Euler | reduz potências usando φ(n) | quando mdc(a,n)=1, mesmo que n seja composto |