O mdc entre dois números naturais a e b pode ser facilmente calculado por meio do algoritmo de Euclides. Faça uma pesquisa e descubra como funciona esse algoritmo.

Passo 1

O enunciado pede para entender como o Algoritmo de Euclides calcula o maior divisor comum (mdc) de dois naturais a e b. Vamos estudar a ideia de usar divisões sucessivas e o fato de que o mdc não muda quando substituímos o par (a,b) por (b,r), onde r é o resto da divisão de a por b.

Passo 2

Começamos usando o Teorema da Divisão: dados a e b com b>0, existem inteiros únicos q (quociente) e r (resto) tais que
a = b,q + r, 0 <= r < b
Aqui r é o resto da divisão de a por b.

Passo 3

A chave do algoritmo é a propriedade
gcd(a,b) = gcd(b,r)
Isto ocorre porque qualquer divisor comum de a e b também divide a - b,q = r, e vice-versa.

Passo 4

Com essa propriedade, definimos o procedimento:
  1. Dados a e b, com a>= b>0, calculamos o resto r de a dividido por b.
  2. Se r=0, então gcd(a,b)=b e o algoritmo para.
  3. Caso contrário, substituímos (a,b) por (b,r) e repetimos o passo 1.

Passo 5

Em forma de pseudocódigo, fica assim:
whi<= bneq 0 do&: r & a bmod b, a & b, b & r;
Quando b=0, o valor de a é o gcd inicial.

Resposta

O Algoritmo de Euclides determina gcd(a,b) repetindo o cálculo do resto r=abmod b e trocando (a,b)(b,r) até que o novo b seja zero. Nesse ponto, o valor de a é justamente o maior divisor comum dos valores iniciais.

Exercícios de Livros Relacionados