Demonstrar que o mdc (n+k, k)=1 se e somente se o mdc ( n, k ) = 1 .

Passo 1

O enunciado pede para mostrar que
gcd(n+k,k)=1Long<=ftrightarrow gcd(n,k)=1
O conteúdo aqui é a propriedade de que qualquer divisor comum a dois números também divide qualquer combinação linear deles. Vamos usar que, se dmid a e dmid b, então dmid (apm b).

Passo 2

Mostramos primeiro que todo divisor comum a n e k também é divisor comum a n+k e k. Seja d tal que
dmid ne dmid k
Então, pela propriedade de combinações lineares,
dmid(n+k)e dmid k,
logo todo divisor comum de (n,k) é divisor comum de (n+k,k). Assim
gcd(n,k)<=gcd(n+k,k)

Passo 3

Agora o recíproco: todo divisor comum a n+k e k também divide n. Seja d tal que
dmid(n+k)e dmid k
Então, como n = (n+k)-k, temos
dmidl((n+k)-kr)=n
Portanto todo divisor comum de (n+k,k) é divisor comum de (n,k), e vale
gcd(n+k,k)<=gcd(n,k)

Passo 4

Das desigualdades
gcd(n,k)<=gcd(n+k,k)<=gcd(n,k)
concluímos que
gcd(n+k,k)=gcd(n,k)
Em particular, gcd(n+k,k)=1 se, e somente se, gcd(n,k)=1.

Resposta

Como mostramos que gcd(n+k,k)=gcd(n,k), segue imediatamente que
gcd(n+k,k)=1 Long<=ftrightarrow gcd(n,k)=1

Exercícios de Livros Relacionados