Dado
arbitrário. Calcule
.
Passo 1
O enunciado dá um inteiro arbitrário
e pede para calcular
.
Informações relevantes fornecidas:
Informações relevantes fornecidas:
- A única informação numérica é que os dois números considerados são
e . - O objetivo é encontrar o máximo divisor comum (mdc) desses dois inteiros.
Passo 2
Vamos lembrar o que significa
.
Definição: para inteiros e
(não ambos zero),
é o maior inteiro positivo
tal que
divide
e
divide
. Escrevemos "
divide
" como
.
Observação importante sobre sinais: , ou seja, o sinal não altera o valor do mdc (o mdc é sempre não negativo).
Definição: para inteiros
Observação importante sobre sinais:
Passo 3
Propriedade simples de divisibilidade que vamos usar: se
e
, então
. Isto é fácil de ver porque, se existem inteiros
tais que
e
, então
, logo
divide
.
Passo 4
Aplique a propriedade ao nosso caso. Seja
. Por definição
e
. Pela propriedade do Passo 3,
divide a diferença:
Logo
.
Passo 5
Os divisores inteiros de
são apenas
e
. Como
é definido como o maior divisor positivo comum, a única possibilidade para
é
. Portanto concluímos que
Passo 6
Comentário alternativo (mesma ideia, por outra via): pela propriedade do algoritmo de Euclides,
Como
, segue
. Isso bate com a prova por diferença acima. Exemplo rápido para fixar:
e
.