Para todo inteiro n, prove que:
mdc(n-1, n^2+n+1)=1 ou 3
Resolução: Vamos supor mdc (n-1, n^2+n+1)=d>1 e seja p um divisor primo de d. Então p (n-1)^2 e p mid(n^2+n+1); daí p mid 3 n, pois (n^2+n+1)-(n-1)^2=3 n. Como p é primo, então p mid 3 ou p mid n. Se p mid n, como p mid(n^2+n+1), então p mid 1, o que nāo é possível. Logo p=3 (ou p=-3 ) e o único fator primo positivo de d é 3 . Provemos que o expoente de 3 em d é 1 , ou seja, que d=3. Se d=3^k(k>1), entāo 9 mid(n-1) e 9 mid(n^2+n+1); daí n=9 r+1 e n^2+n+1=9 s; logo, (9 r+1)^2+(9 r+1)+1=81 r^2+27 r+3=9(9 r^2+3 r)+3=9 s, do que resulta 3(9 r^2+3 r)+1=3 s. Absurdo. Donde, se d>1, entāo d=3.

Passo 1

O problema pede para todo inteiro n mostrar que
gcd(n-1,;n^2+n+1)=1ou3
Vamos usar que qualquer divisor comum de dois inteiros divide também qualquer combinação linear deles.

Passo 2

Seja d=gcd(n-1,n^2+n+1) e suponha d>1. Escolha um primo p que divide d. Então
pmid(n-1) e pmid(n^2+n+1)
Como também pmid(n-1)^2, segue
p;l|;l(n^2+n+1r)-l(n-1r)^2 ;=;3n

Passo 3

Do fato pmid3n, como p é primo, temos duas possibilidades:
  1. pmid3, ou
  2. pmid n.
    Se pmid n, então pmid(n^2+n+1) implica
p;l|;(n^2+n+1)-n(n+1) ;=;1,
impossível. Logo deve ser pmid3, ou seja, p=3. Assim o único primo que divide d é 3.

Passo 4

Resta ver que 3^2=9 não pode dividir d. Suponha, por absurdo, que 9mid(n-1) e 9mid(n^2+n+1). Escreva n=9r+1. Então
n^2+n+1 =(9r+1)^2+(9r+1)+1 =81r^2+27r+3 =9(9r^2+3r)+3,
de onde n^2+n+1equiv3pmod9, o que impede 9mid(n^2+n+1). Contradição.

Resposta

Portanto, os únicos valores possíveis de gcd(n-1,n^2+n+1) são 1 (quando não há divisor primo além de 1) ou 3 (quando 3 divide ambos). Logo
gcd(n-1,n^2+n+1)in1,3

Exercícios de Livros Relacionados