TEORIA DOS NÚMEROS - ALGORITMO DE EUCLIDES

ALGORITIMO DE EUCLIDES PARA OBTENÇÃO DO MÁXIMO DIVISOR COMUM (MDC)

Obtendo o mdc entre dois números naturais X e Y onde X > Y.

1. Divida X por Y e obtenha o resto R₁. Se R₁ for zero, o mdc entre X e Y é Y.
2. Se R₁ não for zero, divida Y por R₁ e obtenha o resto R₂. Se R₂ for zero, o mdc entre X e Y é R₁.
3. Se R₂ não for zero, divida R₁ por R₂ e obtenha o resto R₃. Se R₃ for zero, o mdc entre X e Y é R₂.
4. ...

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.

 

Exemplo - Obter, pelo Algoritmo de Euclides, o mdc entre 10 e 15.

Dividimos 15 por 10 (porque 15 é maior que 10). dividendo divisor 15 10 5 1 resto quociente Como o resto é 5 (não vale zero), devemos dividir o divisor 10 por 5, temos: dividendo divisor 10 5 0 2 resto quociente O resto é zero, portanto o mdc entre 15 e 10 é 5 (o divisor da divisão cujo resto é zero).

O Algoritmo de Euclides pode requistar 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 - Obter, pelo Algoritmo de Euclides, o mdc entre 12 e 15.

Vamos usar a grade prática. A primeira etapa fica assim: 1 15 12 3 A segunda etapa fica assim: 1 4 15 12 3 3 0 O mdc entre 12 e 15 é 3.

Exemplo - Obter, pelo Algoritmo de Euclides, o mdc entre 1128 e 336.

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.