Determine o
para todo número natural
.
Passo 1
O enunciado pede o valor de
para todo número natural
.
Informações dadas:
- Temos dois inteiros dependentes de
: e . - Queremos encontrar o maior divisor comum desses dois inteiros, isto é,
, para cada .
Passo 2
Primeiro, uma ideia bem útil (e que sempre salva em prova): o algoritmo de Euclides e a propriedade básica dos mdc’s.
A propriedade é: para inteiros e qualquer inteiro
,
A propriedade é: para inteiros
Isto é, subtrair múltiplos de um número do outro não altera o mdc. É a base do algoritmo de Euclides.
Vamos aplicar essa propriedade ao nosso par
. Subtraindo
cópia de
de
obtemos:
Logo, usando a propriedade,
Passo 3
Continuamos o processo: subtraindo
cópia de
de
(ou vice-versa) para simplificar:
Portanto
Passo 4
Agora reduzo
em função de
. Observe que
, então
Pelo mesmo motivo (subtrair múltiplos não altera o mdc),
Assim chegamos a uma forma muito simples:
Passo 5
Agora fica fácil: os divisores de
são
. O valor de
depende apenas do resto de
módulo
, isto é, do resto de
módulo
.
Analisando os casos (todo cálculo é simples verificação de restos mod
):
- Se
então , logo . - Se
então , logo . - Se
então , logo . - Se
então , logo .
Podemos conferir com exemplos rápidos:
-
: . -
: . -
: .
Passo 6
Conclusão final: o mdc depende do resto de
modulo
conforme listado acima.
Resposta
Se
então
.
Se então
.
Se ou
então
.
Se
Se