Olimpíadas ⇒ (Irlanda 2002) TFA e Congruência Tópico resolvido

[EsleyPires]

(Irlanda 2002) Encontre todas as soluções inteiras positivas de [tex3]p(p + 3) +q(q + 3) = n(n + 3)[/tex3], onde [tex3]p[/tex3], [tex3]q[/tex3] são primos.

Esse é mais um problema do POTI que está sem solução no arquivo em PDF que eles disponibilizam.
Eu consegui resolver parte da questão, mas falta encontrar as soluções para o caso em que [tex3]q=3[/tex3] e [tex3]p\not=3[/tex3] (ou o contrário).
Segue a minha resolução para os demais casos:

Resposta

---

Veja que, se [tex3]p\not=3[/tex3], [tex3]p[/tex3] deixa resto 1 ou 2 na divisão por 3 (se deixasse resto 0, [tex3]p[/tex3] não seria primo, pois seria igual a [tex3]3k[/tex3] para algum [tex3]k[/tex3]).

Mas perceba que, se [tex3]p\not=3[/tex3] e é primo, [tex3]p(p+3)\equiv1\ (\mod 3)[/tex3] (é fácil chegar a essa conclusão ao usar classes residuais).

Note que o caso é análogo para [tex3]q[/tex3], logo, se [tex3]q\not=3[/tex3], temos:
[tex3]\large q(q+3)\equiv 1 \ (mod \ 3)[/tex3]
Portanto, se [tex3]p,q\not=3[/tex3], devemos ter (representando os números pelos seus restos no módulo 3 por [tex3] \bar 1[/tex3] e [tex3]\bar 2[/tex3]) que:
[tex3]
\large \overline 1+ \overline1=\overline 2= n(n + 3)
[/tex3]
Porém, isso é impossível, pois independentemente do resto que [tex3]n[/tex3] deixar na divisão por 3, [tex3]n^2+3n[/tex3] não deixa resto 2 ao ser dividido por 3.

Concluímos que se [tex3]p,q[/tex3] são ambos diferentes de 3, não há solução para o problema.

Por verificação direta, se [tex3]p,q[/tex3] são ambos iguais a 3, temos:

[tex3]
\large 3\cdot(3 + 3) +
3\cdot (3 + 3) = 36=n(n + 3)
[/tex3]

Mas não existe [tex3]n[/tex3] inteiro positivo que seja solução para esse caso.

Resta analisarmos o caso em que apenas um entre [tex3]p[/tex3] e [tex3]q[/tex3] é igual a 3. Sem perda de generalidade, suponhamos que [tex3]q=3[/tex3].

Logo, temos:

[tex3]
\large p(p + 3) +
18 = n(n + 3)
[/tex3]

A partir daqui, eu não consegui estruturar mais a solução.

Alguns fatos que podem ajudar estão listados a seguir:

Resposta

---

• Dois casos particulares são [tex3]p=2,q=3,n=4[/tex3] e [tex3]p=7,q=3,n=8[/tex3].

• [tex3]n(n+3)=n^3+3n=(n-3)(n+6)[/tex3].

• [tex3]p(p+3)[/tex3] é par, logo ou [tex3]p(p+3)\equiv 0 \ (\mod 4)[/tex3] ou [tex3]p(p+3)\equiv 2 \ (\mod 4)[/tex3].

Qualquer solução (inteira ou apenas para o caso que resta) ou palpite já ajuda, bem como quaisquer correções acerca da minha solução ainda incompleta. Desde já, agradeço!

[FelipeMartinMOD]

ok [tex3]q=3[/tex3] e [tex3]p \neq 3[/tex3]:

[tex3]p(p+3) +3 \cdot 6 = n(n+3)[/tex3]
[tex3]p(p+3) = n^2+3n - 3^2 - 3 \cdot 3 = (n-3)(n+3)+3(n-3) = (n-3)(n+6)[/tex3]

o [tex3]MDC[/tex3] entre [tex3]n-3[/tex3] e [tex3]n+6[/tex3] divide [tex3]9[/tex3], então, pode ser [tex3]1,3,9[/tex3].

Notemos que sendo [tex3]p \neq 3[/tex3], temos [tex3]\MDC(p,p+3) = 1[/tex3].

Se [tex3]\mdc(n-3,n+6) =1[/tex3], então ou [tex3]p \vert n-3 \implies n+6 \vert p+3[/tex3] ou [tex3]p \vert n+6 \implies n-3 \vert p+3[/tex3].

Na primeira opção [tex3]p \leq n-3[/tex3] e [tex3]n+6 \leq p+3 \iff n+3 \leq p \leq n-3[/tex3] absurdo.

Na segunda opção [tex3]p \leq n+6[/tex3] e [tex3]n-3 \le p+3 \implies n-6 \le n+6[/tex3].

[tex3]\begin{cases}
n+6 = pa \\
p+3 =b(n-3)
\end{cases} \implies p+3+3b+6b = abp \implies p(ab-1) = 3(1+3b)[/tex3]

[tex3]p = \frac{3+9b}{ab-1}[/tex3]

primeiro vejamos que [tex3]\frac{3+9b}{ab-1} \leq4 \iff 3+9b \le 4ab-4 \iff a \ge \frac{7+9b}{4b} = \frac94 + \frac7{4b} [/tex3] logo, se [tex3]a \geq 4[/tex3], teremos [tex3]p =2[/tex3] mas [tex3]n(n+3) = 24[/tex3] não tem solução. Então, se [tex3]a=3[/tex3]:

[tex3]3b-1 \vert 3+9b \implies 3b-1 \vert 3+9b - 9b +3 \iff 3b-1 \vert 6 \implies b=1[/tex3] daí, [tex3]p = \frac{12}{2} = 6[/tex3] absurdo.

[tex3]a=2 \implies 2b-1 \vert 3+9b \implies 2b-1 \vert 6+18b \implies 2b-1 \vert 15[/tex3] daí, [tex3]b \in \{1,2,3,8\} \implies p \in\{12,7,6,5\}[/tex3]
Se [tex3]p=7, a=2, b=1 \implies n=8[/tex3] funciona! Mas [tex3]p=5[/tex3] não dá [tex3]n[/tex3] inteiro.

[tex3]a=1 \implies b-1 \vert 3+9b \implies b-1 \vert 12 \implies b \in \{2,3,4,5,7,13\} \implies p \in \{21,15,13,12,11,10 \}[/tex3] mas nem [tex3]p=11[/tex3] nem [tex3]p=13[/tex3] geram [tex3]n[/tex3]s inteiros.

Então, achamos uma única solução [tex3]p=7,n=8[/tex3] para o caso [tex3]\mdc (n-3,n+6)=1[/tex3].

Se [tex3]\mdc(n-3,n+6) = 3[/tex3], então, [tex3]n-3 = 3A[/tex3] e [tex3]n+6 = 3B[/tex3] com [tex3]\mdc (A,B) =1[/tex3]:

[tex3]p(p+3) = 9AB[/tex3] devemos ter [tex3]9 \vert p+3 \implies 9 \vert 3p+9 \implies 9 \vert 3p[/tex3] absurdo.

Analogamente, se [tex3]\mdc(n-3,n+6) = 9[/tex3], então, [tex3]81 \vert p+3 \implies 81 \vert 27p[/tex3] absurdo.

Então pra você só faltou a solução [tex3]p=7[/tex3] e [tex3]n=8[/tex3]

[EsleyPires]

Primeiramente, obrigado pela resposta! Gostaria de dizer que concordo com sua solução, e acredito que ela esteja realmente correta.
Porém, o único fragmento que acredito que não ficou claro para mim é o que segue abaixo:

primeiro vejamos que [tex3]\frac{3+9b}{ab-1} \leq4 \iff 3+9b \le 4ab-4 \iff a \ge \frac{7+9b}{4b} = \frac94 + \frac7{4b} [/tex3] logo, se [tex3]a \geq 4[/tex3], teremos [tex3]p =2[/tex3] mas [tex3]n(n+3) = 24[/tex3] não tem solução.

Talvez seja intuitivo ou esteja claro, mas eu não entendi o motivo de [tex3]\frac{3+9b}{ab-1} \leq4[/tex3] nem a relação disso com a implicância de que, se [tex3]a\ge 4[/tex3], temos que [tex3]p=2[/tex3].
Se possível, gostaria que a explicasse mais detalhadamente, e isto encerrará de vez esta questão para mim. Desde já, agradeço novamente.

Aliás, uma pequena correção é que, no fragmento abaixo, deveria ser [tex3]a=b=2[/tex3].

Se [tex3]p=7, a=2, b=1 \implies n=8[/tex3] funciona! Mas [tex3]p=5[/tex3] não dá [tex3]n[/tex3] inteiro.

[FelipeMartinMOD]

EsleyPires, você está correto quanto ao [tex3]b=2[/tex3], infelizmente, eu não posso mais editar minha resposta antiga.

Explicando o [tex3]a \ge 4[/tex3]:

Você viu que [tex3]p = \frac{3+9b}{ab-1}[/tex3]. Temos uma expressão com duas variáveis, [tex3]a[/tex3] e [tex3]b[/tex3]. Expressões assim são difíceis de analisar, então, procuramos um jeito esperto de restringir os valores absurdos de [tex3]a[/tex3] e [tex3]b[/tex3]. Via de regra [tex3]ab-1 >>> 3+9b[/tex3]: a expressão [tex3]10x -1000[/tex3] eventualmente fica maior que [tex3]9x+1000[/tex3]. Minha ideia foi usar esse fato para descartar valores de [tex3]a[/tex3] que gerariam [tex3]p \leq 4[/tex3] e, como [tex3]p[/tex3] é primo diferente de [tex3]3[/tex3], nesses casos só teríamos que buscar soluções para [tex3]p=2[/tex3].

Então eu analisei quando a expressão é menor ou igual a [tex3]4[/tex3] ([tex3]a[/tex3] e [tex3]b[/tex3] positivos maiores ou iguais a [tex3]1[/tex3]): [tex3]\frac{3+9b}{ab-1} \leq 4 \iff 3 + 9b \leq 4ab - 4 \iff \frac 7{4b} + \frac 94 \leq a[/tex3]. Observe que para [tex3]b \geq 1[/tex3], temos [tex3]\frac 7{4b} + \frac 94 \leq \frac74 + \frac 94 = 4[/tex3]. Então, se [tex3]a \geq 4 [/tex3], teremos [tex3]a \geq \frac 7{4b} + \frac 94 \implies 4ab -4 \geq 3+9b \iff 4 \geq \frac{3+9b}{ab-1} = p[/tex3]. Então, consegui descartar todos os pares [tex3](a,b)[/tex3] com [tex3]a \geq 4[/tex3]. Faltou analisar os casos: [tex3]a \in \{1,2,3\}[/tex3], que foi o que eu fiz em seguida.

[EsleyPires]

@FelipeMartinMOD, obrigado pela resposta, que ficou clara para mim. De fato, acredito estar correta.
Porém, outro pequeno detalhe que corroborou para a minha incompreensão na primeira leitura (e que me passou despercebido) foi o fato de que inferiste que:

teremos [tex3]p =2[/tex3] mas [tex3]n(n+3) = 24[/tex3] não tem solução.

Acredito que o equívoco está no fato de que, na verdade, [tex3]p=2[/tex3] implica que [tex3]n(n+3)=28[/tex3], pois de [tex3]p(p+3)=(n+6)(n-3)[/tex3], vemos que: se [tex3]p=2[/tex3], então [tex3]2\cdot (2+3)=10=(n+6)(n-3)[/tex3], e [tex3]n=4[/tex3] é solução. Ainda assim, acredito que isso não interfira na validade da afirmação abaixo:

Então eu analisei quando a expressão é menor ou igual a [tex3]4[/tex3] ([tex3]a[/tex3] e [tex3]b[/tex3] positivos maiores ou iguais a [tex3]1[/tex3]): [tex3]\frac{3+9b}{ab-1} \leq 4 \iff 3 + 9b \leq 4ab - 4 \iff \frac 7{4b} + \frac 94 \leq a[/tex3]. Observe que para [tex3]b \geq 1[/tex3], temos [tex3]\frac 7{4b} + \frac 94 \leq \frac74 + \frac 94 = 4[/tex3]. Então, se [tex3]a \geq 4 [/tex3], teremos [tex3]a \geq \frac 7{4b} + \frac 94 \implies 4ab -4 \geq 3+9b \iff 4 \geq \frac{3+9b}{ab-1} = p[/tex3]. Então, consegui descatar todos os pares [tex3](a,b)[/tex3] com [tex3]a \geq 4[/tex3]. Faltou analisar os casos: [tex3]a \in \{1,2,3\}[/tex3], que foi o que eu fiz em seguida.

Continuando ela verdadeira, mostraste que não existem mais casos possíveis para [tex3]p[/tex3] ao longo de ambas as respostas.
Dessa forma, se concordares, podemos concluir que as únicas duas soluções para esse problema são: [tex3](p=2,q=3,n=4)[/tex3] e [tex3](p=7,q=3,n=8)[/tex3].

[FelipeMartinMOD]

Isso, tens razão. Eu errei na conta, fiz [tex3]2(2+1)+18 = 24[/tex3], mas deveria ter feito [tex3]2 \cdot (2+3) + 18 = 28[/tex3]. Então as soluções são essas que disseste e as permutações de [tex3]p[/tex3] e [tex3]q[/tex3].