S-3.28 Calcule mdc(n+1, n^2+1), para n in Z.

Passo 1

O enunciado pede gcd(n+1,;n^2+1) para ninZ. Vamos usar o algoritmo de Euclides, que nos diz que
gcd(a,b)=gcdl(a,,b - q,ar)
para qualquer inteiro q.

Passo 2

Aplicando o algoritmo de Euclides com a = n+1 e b = n^2+1, escolhemos q = n-1 porque
(n^2 +1) - (n-1),(n+1) = n^2+1 - (n^2 -1) = 2
Logo
gcd(n+1,;n^2+1) = gcdl(n+1,;2r)

Passo 3

Agora basta observar que é ímpar},\ 1, & se é par. \end{cases}]

Resposta

gcd(n+1,;n^2+1)= 2, & nequiv1pmod2, 1, & nequiv0pmod2

Exercícios relacionados