Mostre que:
dois números inteiros da forma \frac{n}{\varphi} e 2 n+1 são sempre primos entre si.

Passo 1

O enunciado dá dois números inteiros da forma \dfrac{n}{\varphi} e 2n+1. Para que \dfrac{n}{\varphi} seja inteiro, devo entender que \varphi é um divisor de n (ou seja, \varphi\in\mathbb{Z}_{>0} e \varphi\mid n). O que o problema pede é mostrar que esses dois inteiros são primos entre si, isto é, que o máximo divisor comum entre eles é 1.
Resumo das informações dadas:
  • n é um inteiro.
  • \varphi é um divisor de n, logo \dfrac{n}{\varphi} é inteiro.
  • Queremos provar que \gcd\!\Big(\dfrac{n}{\varphi},\,2n+1\Big)=1.

Passo 2

Recordando o que significa “primos entre si” e uma propriedade útil de divisores:
  • Dois inteiros a e b são primos entre si quando \gcd(a,b)=1.
  • Se um inteiro d divide a e divide b, então d divide qualquer combinação linear inteira de a e b; em particular, d divide ra+sb para quaisquer inteiros r,s. Em linguagem prática: qualquer divisor comum de a e b também divide a\pm b, ka etc.
Essa propriedade de combinações lineares (ou da diferença) é a ferramenta que vamos usar.

Passo 3

Seja
d=\gcd\!\Big(\dfrac{n}{\varphi},\,2n+1\Big).
Então, por definição, d divide \dfrac{n}{\varphi} e também divide 2n+1.
Como d divide \dfrac{n}{\varphi}, multiplicando por 2\varphi (que é um inteiro) vemos que d também divide
2\varphi\cdot\frac{n}{\varphi}=2n.
Portanto d divide simultaneamente 2n e 2n+1.

Passo 4

Se d divide 2n e d divide 2n+1, então d divide a diferença entre esses dois números:
(2n+1)-2n = 1.
Logo d divide 1. O único divisor positivo de 1 é 1 próprio. Assim d=1.

Passo 5

Concluímos que \gcd\!\Big(\dfrac{n}{\varphi},\,2n+1\Big)=1, ou seja, os dois inteiros são primos entre si.
Exemplo numérico pequeno para fixar a ideia: tome n=12 e \varphi=3 (de fato \varphi\mid n). Então \dfrac{n}{\varphi}=4 e 2n+1=25. Qualquer divisor comum teria de dividir 2\cdot 12=24 e 25; portanto dividiria 25-24=1, logo o máximo divisor comum é 1.

Resposta

\displaystyle \gcd\!\Big(\dfrac{n}{\varphi},\,2n+1\Big)=1

Exercícios relacionados