OBM 2016 - Nível 2 - P6

Problema 6.

Seja $a_0=a>1$, um inteiro e, para $n\geq 0$, defina $a_{n+1}=2^{a_n}-1$. Mostre que o conjunto dos divisores primos dos termos da sequência $a_n$ é infinito.

Solução:

Lema: $mdc(2^a-1, 2^b-1)=2^{(mdc(a, b))}-1$.

Prova: Seja $d=mdc(a, b)$, note que $2^d-1|2^a-1$ e $2^d-1|2^b-1\Rightarrow 2^d-1|mdc(2^a-1, 2^b-1)$. Se $mdc(2^a-1, 2^b-1)=k\Rightarrow 2^a\equiv 1(mod. k)$ e $2^b\equiv 1(mod. k)$, por Bézout há inteiros $x, y$ tais que $ax+by=d\Rightarrow 2^{ax+by} \equiv 2^d \equiv 1 (mod. k)$, logo $k|2^d-1$ e como $2^d-1|k$, temos $k=2^d-1$.

Suponha, por absurdo, que seja finito. Sejam $p_1, p_2, p_3,...., p_k$ tais primos e $p_k$ é o maior deles; seja $a_m$ tal que $p_k|a_m\Rightarrow 2^{p_k}-1|2^{a_m}-1=a_{m+1}$, seja $q$ um primo dividindo $2^{p_k}-1$, assim devemos ter $ord_q(2)=p_k$, e consequentemente $p_k|\varphi{(q)}=q-1\Rightarrow q>p_k$ e $q|a_{m+1}$, com isso temos um absurdo. Logo temos infinitos primos.

Observação: É possível resolver esse problema, usando teoremas mais avançados, por exemplo o Teorema de Kobayashi, mas não é recomendado usar numa prova de olimpíada.