Seja
um inteiro positivo. Qual é o máximo divisor comum de
e
?
Passo 1
O enunciado pede
onde
é inteiro positivo. O conteúdo principal é algorítmo de Euclides para máximo divisor comum (MDC). Vamos aplicar essa técnica para simplificar o problema.
Passo 2
Pelo algorítmo de Euclides, temos
Isto reduz o cálculo do MDC de
ao de
.
Passo 3
Agora avaliamos
. Existem dois casos, conforme a paridade de
:
- Se
for par, então divide e . - Se
for ímpar, então não divide e .