Determine o \operatorname{mdc}(3 n+1,5 n+3) para todo número natural n.

Passo 1

O enunciado pede o valor de \operatorname{mdc}(3n+1,5n+3) para todo número natural n.
Informações dadas:
  • Temos dois inteiros dependentes de n: 3n+1 e 5n+3.
  • Queremos encontrar o maior divisor comum desses dois inteiros, isto é, \operatorname{mdc}\bigl(3n+1,5n+3\bigr), para cada n\in\mathbb{N}.

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 a,b e qualquer inteiro k,
\operatorname{mdc}(a,b)=\operatorname{mdc}(a,b-ka).
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 \bigl(3n+1,\,5n+3\bigr). Subtraindo 1 cópia de 3n+1 de 5n+3 obtemos:
(5n+3)-(3n+1)=2n+2.
Logo, usando a propriedade,
\operatorname{mdc}\bigl(3n+1,5n+3\bigr)=\operatorname{mdc}\bigl(3n+1,\,2n+2\bigr).

Passo 3

Continuamos o processo: subtraindo 1 cópia de 2n+2 de 3n+1 (ou vice-versa) para simplificar:
(3n+1)-(2n+2)=n-1.
Portanto
\operatorname{mdc}\bigl(3n+1,\,2n+2\bigr)=\operatorname{mdc}\bigl(n-1,\,2n+2\bigr).

Passo 4

Agora reduzo 2n+2 em função de n-1. Observe que 2\cdot(n-1)=2n-2, então
(2n+2)-2\cdot(n-1)=2n+2-(2n-2)=4.
Pelo mesmo motivo (subtrair múltiplos não altera o mdc),
\operatorname{mdc}\bigl(n-1,\,2n+2\bigr)=\operatorname{mdc}\bigl(n-1,\,4\bigr).
Assim chegamos a uma forma muito simples:
\operatorname{mdc}\bigl(3n+1,5n+3\bigr)=\operatorname{mdc}\bigl(n-1,4\bigr).

Passo 5

Agora fica fácil: os divisores de 4 são 1,2,4. O valor de \operatorname{mdc}\bigl(n-1,4\bigr) depende apenas do resto de n-1 módulo 4, isto é, do resto de n módulo 4.
Analisando os casos (todo cálculo é simples verificação de restos mod 4):
  • Se n\equiv1\pmod4 então n-1\equiv0\pmod4, logo \operatorname{mdc}(n-1,4)=4.
  • Se n\equiv3\pmod4 então n-1\equiv2\pmod4, logo \operatorname{mdc}(n-1,4)=2.
  • Se n\equiv0\pmod4 então n-1\equiv3\pmod4, logo \operatorname{mdc}(n-1,4)=1.
  • Se n\equiv2\pmod4 então n-1\equiv1\pmod4, logo \operatorname{mdc}(n-1,4)=1.
Podemos conferir com exemplos rápidos:
  • n=1: \operatorname{mdc}(4,8)=4.
  • n=3: \operatorname{mdc}(10,18)=2.
  • n=2: \operatorname{mdc}(7,13)=1.

Passo 6

Conclusão final: o mdc depende do resto de n modulo 4 conforme listado acima.

Resposta

Se n\equiv1\pmod4 então \operatorname{mdc}(3n+1,5n+3)=4.
Se n\equiv3\pmod4 então \operatorname{mdc}(3n+1,5n+3)=2.
Se n\equiv0\pmod4 ou n\equiv2\pmod4 então \operatorname{mdc}(3n+1,5n+3)=1.

Exercícios relacionados