provar que dois números são primos entre si

[Walter R]

Gostaria de obter ajuda para resolver o seguinte problema:

Seja \(x_{n}= \frac{p_{n}}{q_{n}}\), com \(p_{n}\) e \(q_{n}\) definidos recursivamente por:

\(p_{1}= q_{1}= 1\), \(p_{n+1}= p_{n}^{2}+2q_{n}^{2}\), \(q_{n+1}=2p_{n}q_{n}\).

Mostre que para todo \(n\in \mathbb{N}\), \(p_{n}\) e \(q_{n}\) são primos entre si.

[Rui Carpentier]

Sugestão:

Prove primeiro por indução que \(p_n\) é sempre ímpar. Logo que fator comum entre \(p_n\) e \(q_n\) terá que também ser ímpar.

Depois é utilizar o método de descida infinita*: se \(p_{n+1}\) e \(q_{n+1}\) não são primos entre si então \(p_{n}\) e \(q_{n}\) também não são primos entre si (sugestão: se um primo \(p\not=2\) divide \(p_{n+1}\) e \(q_{n+1}\) então também divide \(p_{n}\) e \(q_{n}\)).

* não é mais que o método de indução por contra-recíproco.

[Walter R]

Boa noite, Rui.

Vejamos. Temos que \(p_{2}=1^2+2(1^2)\), que é ímpar. Então a expressão vale para n=1. Agora, vamos supor que ela também vale para algum \(n\in \mathbb{N}\). Devemos provar que ela vale também para n+1. Se \(p_{n}\) é ímpar ( hipótese indutiva), então \(p_{n}^2\) é ímpar. Como \(2q_{n}^2\) é par, temos que \(p_{n}^2 + 2q_{n}^2\) é ímpar. Logo, \(p_{n+1}\) é sempre ímpar. Se \(p_{n+1}\) é sempre ímpar, então \(p_{n+1}\) não tem um fator par.

Isto me garante que \(p_{n+1}\) não é divisível por 2 ( que é um dos fatores de \(q_{n+1}\)). Mas quem me garante que não haja em \(q_{n}\) ou em \(p_{n}\) um fator ímpar que divida numerador e denominador? Recordemos que \(x_{n+1}= \frac{p_{n+1}}{q_{n+1}}=\frac{p_{n}^{2}+2q_{n}^{2}}{2p_{n}q_{n}}\).

[Rui Carpentier]

Chegou a ler a 2ª parte da mensagem?

Depois é utilizar o método de descida infinita*: se \(p_{n+1}\) e \(q_{n+1}\) não são primos entre si então \(p_n\) e \(q_n\) também não são primos entre si (sugestão: se um primo \(p\not= 2\) divide \(p_{n+1}\) e \(q_{n+1}\) então \(p\) também divide \(p_{n}\) e \(q_{n}\)).

Note que se \(p\not= 2\) divide \(q_{n+1}=2p_n q_n\) então divide \(p_{n}\) ou \(q_{n}\). Se \(p\) divide \(p_{n}\) então, como também divide \(p_{n+1}=p_n^2+2q_n^2\), divide \(2q_n^2=p_{n+1}-p_n^2\), logo \(p\) divide \(p_n\) e \(q_n\). (O mesmo raciocínio se \(p\) divide \(q_{n}\)).

Fica provado então que se \(p_{n+1}\) e \(q_{n+1}\) não são primos entre si então \(p_{n}\) e \(q_{n}\) também não são primos entre si. Tal é logicamente equivalente a provar que se \(p_{n}\) e \(q_{n}\) são primos entre si então \(p_{n+1}\) e \(q_{n+1}\) também são primos entre si.

[Walter R]

Tal é logicamente equivalente a provar que se \(p_{n}\) e \(q_{n}\) são primos entre si então \(p_{n+1}\) e \(q_{n+1}\) também são primos entre si.

Este último esclarecimento resolveu a dúvida. Obrigado pela ajuda!