Já tratei da decomposição de um número natural em fatores primos. Isso certamente é suficiente para obter o mdc entre dois ou vários números naturais. No entanto, para obter o mdc entre dois números naturais muito grandes isso fica complicado porque a decomposição pode não ser imediata.
O método a seguir é baseado no livro sétimo dos Elementos de Euclides. Apesar de existirem evidências históricas que este método seja anterior a este livro... O Algoritmo de Euclides para a obtenção do máximo divisor comum entre dois números naturais é um processo bem simples. Não desista ao ler a explicação pelo roteiro, mas acompanhe o roteiro juntamente com os exemplos numéricos que virão a seguir - vai ficar bem mais fácil.
Roteiro
Obtendo o mdc entre dois números naturais `X` e `Y` onde `X > Y`.
1) Divida `X` por `Y` e obtenha o resto `R_1`. Se `R_1` for zero, o mdc entre `X` e `Y` é `Y`.
2) Se `R_1` não for zero, divida `Y` por `R_1` e obtenha o resto `R_2`. Se `R_2` for zero, o mdc entre `X` e `Y` é `R_1`.
3) Se `R_2` não for zero, divida `R_1` por `R_2` e obtenha o resto `R_3`. Se `R_3` for zero, o mdc entre `X` e `Y` é `R_2`.
...
Se `R_n` não for zero, divida `R_{n-1}` por `R_n` e obtenha o resto `R_{n+1}`. Se `R_{n+1}` for zero, o mdc entre `X` e `Y` é `R_n`.
Calcule o MDC
Resolver Equação Diofantina `ax + by = c`
Uma equação diofantina é uma equação linear da forma `ax + by = c`, onde `a`, `b` e `c` são inteiros, e buscamos soluções inteiras para `x` e `y`. Usamos o Algoritmo de Euclides Estendido para encontrar `x_0` e `y_0` tais que `ax_0 + by_0 = \text{mdc}(a,b)`. A equação tem solução se `c` for divisível por `\text{mdc}(a,b)`. As soluções gerais são:
`x = x_0 * (\frac{c}{\text{mdc}(a,b)} + (\frac{b}{\text{mdc}(a,b)} ) * k`
`y = y_0 * (\frac{c}{\text{mdc}(a,b)}) - (\frac{a}{\text{mdc}(a,b)}) * k`
onde `k` é qualquer inteiro.
Exemplo 1
Obter, pelo Algoritmo de Euclides, o mdc entre 10 e 15.
Resolução
Dividimos 15 por 10 (porque 15 é maior que 10).
| 15 | 10 |
| 5 | 1 |
Como o resto é 5 (não vale zero), devemos dividir o divisor 10 por 5:
| 10 | 5 |
| 0 | 2 |
O resto é zero, portanto o mdc entre 15 e 10 é 5 (o divisor da divisão cujo resto é zero).
→ Confira com uma calculadora de mmc ou de mdc entre dois números naturais clique aqui
Como o Algoritmo de Euclides Resolve Equações Diofantinas
Uma equação diofantina linear, como `ax + by = c`, onde `a`, `b` e `c` são inteiros, busca soluções inteiras para `x` e `y`. O Algoritmo de Euclides, especialmente em sua forma estendida, é uma ferramenta poderosa para resolver esse tipo de equação. Abaixo, explicamos passo a passo como ele funciona:
-
Calcular o MDC com o Algoritmo de Euclides
O primeiro passo é encontrar o máximo divisor comum (MDC) de `a` e `b`, denotado `\text{mdc}(a, b)`. O Algoritmo de Euclides faz isso por divisões sucessivas. Por exemplo, para `a = 6` e `b = 8`:- `6 = 0 * 8 + 6` (resto 6)
- `8 = 1 * 6 + 2` (resto 2)
- `6 = 3 * 2 + 0` (resto 0)
-
Verificar a Existência de Solução
A equação `ax + by = c` só tem solução inteira se `c` for divisível por `\text{mdc}(a, b)`. Isso ocorre porque qualquer combinação linear de `a` e `b` (ou seja, `ax + by`) é sempre um múltiplo do MDC. Para `6x + 8y = 22`, como `22 / 2 = 11` (inteiro), há solução. -
Usar o Algoritmo Estendido para Encontrar `x_0` e `y_0`
O Algoritmo de Euclides Estendido vai além do MDC: ele encontra inteiros `x_0` e `y_0` tais que `ax_0 + by_0 = \text{mdc}(a, b)`. Voltamos pelas divisões:- De `8 = 1 * 6 + 2`, temos `2 = 8 - 1 * 6`.
- Reescrevendo: `6 * (-1) + 8 * 1 = 2`.
-
Ajustar para o Valor de `c`
Com `x_0` e `y_0` encontrados, ajustamos para `c`. Se `c = 22` e `\text{mdc}(6, 8) = 2`, calculamos o fator `c / \text{mdc}(a, b) = 22 / 2 = 11`. Então:- `x = x_0 * (\frac{c}{\text{mdc}(a, b)}) = -1 * 11 = -11`
- `y = y_0 * (\frac{c}{\text{mdc}(a, b)}) = 1 * 11 = 11`
-
Determinar as Soluções Gerais
Todas as soluções da equação são dadas por:
`x = x_0 * (\frac{c}{\text{mdc}(a, b)}) + (\frac{b}{\text{mdc}(a, b)}) * k`
`y = y_0 * (\frac{c}{\text{mdc}(a, b)}) - (\frac{a}{\text{mdc}(a, b)}) * k`
onde `k` é qualquer inteiro. Para o exemplo:- `x = -11 + (8 / 2) * k = -11 + 4k`
- `y = 11 - (6 / 2) * k = 11 - 3k`
Portanto, o Algoritmo de Euclides Estendido não só calcula o MDC, mas também fornece uma combinação linear de `a` e `b` que pode ser ajustada para resolver `ax + by = c`, desde que `c` seja compatível com o MDC. Esse processo é essencial em teoria dos números e tem aplicações em criptografia, entre outros campos.
O Algoritmo de Euclides pode requerer muitas divisões sucessivas até que se chegue ao resto zero (sempre se chegará). Por conta disso, é melhor usar uma chave que aproveita melhor os resultados anteriores e deixa espaço para os próximos, caso sejam necessários.
Monte uma grade com, pelo menos, 3 colunas e exatamente 3 linhas (deixe espaço à direita):
Na grade, insira o 15 e o 10 (vou manter os números do exemplo) assim:
| 15 | 10 | ||
Sempre na primeira linha, sobre o último divisor usado, escreva o quociente da divisão atual. Na divisão de 15 por 10 o quociente é 1. Registre assim:
| 1 | |||
| 15 | 10 | ||
O resto da divisão atual é registrado abaixo do dividendo da divisão atual. Na divisão de 15 por 10 o resto é 5.
| 1 | |||
| 15 | 10 | ||
| 5 |
Como 5 não é zero, compiamos o 5 ao lado do 10, na próxima casa. Repete-se todo o processo anterior, pensando que a divisão de agora é de 10 por 5.
| 1 | |||
| 15 | 10 | 5 | |
| 5 |
Na divisão de 10 por 5 o quociente é 2. Registre assim:
| 1 | 2 | ||
| 15 | 10 | 5 | |
| 5 |
Na divisão de 10 por 5 o resto é 0.
| 1 | 2 | ||
| 15 | 10 | 5 | |
| 5 | 0 |
Como o resto é zero, o mdc entre 15 e 10 é o número 5.
Exemplo 2
Obter, pelo Algoritmo de Euclides, o mdc entre 1128 e 336.
Resolução
Após as divisões sucessivas e os registros dos resultados nos locais apropriados, chega-se em:
| 3 | 2 | 1 | 4 | |
| 1128 | 336 | 120 | 96 | 24 |
| 120 | 96 | 24 | 0 |
O mdc entre 1128 e 336 é 24.