Nível 2 - Fase 3

Problema 1:

a) Considere todos os números formados usando os quatro algarismos $1$, $2$, $3$ e $4$. Formamos a seguinte expressão numérica $S_4 = 4321-4312+4231-4213+...+1243-1234$, na qual os números são listados da esquerda para a direita do maior para o menor, e os sinais $+$ e $-$ alternam-se até o final. Calcule o valor de $S_4$.

b) De modo análogo, tomamos todos os números de nove algarismos distintos e não nulos e formamos a expressão numérica $S_9 = 987654321-987654312+987654231-...-123456789$, na qual os números são listados da esquerda para a direita do maior para o menor, e os sinais $+$ e $-$ alternam-se até o final. Calcule o valor de $S_9$.

Solução:

Para calcularmos o valor da expressão em ambas situações vamos utilizar o fato que entre dois números consecutivos (com um sinal negativo entre eles) a única diferença é a permutação dos dois últimos algarismos, que possibilita a menor diferença possível (alterar as centenas, por exemplo, não seria a melhor opção se ainda podemos alterar apenas as dezenas e unidades, que possibilitam um menor acréscimo) requerida para a ordenação dos números.

Defina $S_n$ da mesma forma que $S_4$ e $S_9$, sendo $n$ natural e menor ou igual a $9$.

Analisando esse fato veja que o valor total de $S_n$ é justamente dado por essas diferenças, logo ao contá-las encontramos a resposta do problema. Vamos fixar os dígitos não permutados e analisar apenas os dois últimos dígitos: suponha que o menor seja $a$ e o maior $a+j$, então ao trocarmos ambos de lugar, a única diferença entre os números será justamente a diferença resultante da permutação, pois o resto vai “se anular”, assim basta calcularmos:

$[10 \cdot (a+j) + a]- [10 \cdot a + (a+j)] = 10 \cdot j - j = 9 \cdot j$

Se a diferença entre os dígitos permutados for $j$, então acrescentamos $9j$ ao valor total, porém, veja que fixando os algarismos não permutados, a quantidade $k$ de vezes que isso acontece é justamente $n-j$:

Permutação dos dígitos cuja diferença é $j$: $1$ e $j+1$, $2$ e $j+2$, ... , $k$ e $j+k$, mas $n$ é o maior dígito possível, logo $j+k = n \Rightarrow k = n-j$, justamente o que queremos provar.

Por fim, basta "acrescentarmos" a quantidade de vezes que cada pequena diferença, resultante da permutação dos dois últimos dígitos, ocorre: $(n-2)!$, de fato, esse valor resulta da quantidade de maneiras existentes de permutar os $(n-2)$ primeiros dígitos, que durante nossos cálculos estavam fixos.

Assim:

$S_n = (n-2)!\cdot[(n-1) \times (9 \cdot 1) + (n-2) \times (9 \cdot 2) + (n-3) \times (9 \cdot 3) + ... + (n-(n-1)) \times (9 \cdot (n-1))]$.

O que nos possibilita encontrar a resposta de ambos itens:

(a) $S_4 = 2! \cdot [(4-1) \times (9 \cdot 1) + (4-2) \times (9 \cdot 2) + (4-3) \times (9 \cdot 3)] = 2! \cdot 90 = 180$.

(b) $S_9 = 7! \cdot [(9-1) \times (9 \cdot 1) + (9-2) \times (9 \cdot 2) + ... + (1) \times (9 \cdot 8)] = 7! \cdot[72 + 126 + 162 + 180 + 180 + 162 + 126 + 72] = 7! \cdot 1080 = 5443200$.

Problema 2:

As bissetrizes internas dos ângulos $A\hat{B}C$ e $A\hat{C}B$ do triângulo $ABC$ se encontram no ponto $I$. A reta paralela a $BI$ que passa pelo ponto $A$ encontra a reta $CI$ no ponto $D$. A reta paralela a $CI$ por $A$ encontra a reta $BI$ no ponto $E$. As retas $BD$ e $CE$ se encontram no ponto $F$. Mostre que $F$, $A$ e $I$ são colineares se, e somente se, $AB = AC$.

Solução:

Se $AB = AC$, então o triângulo $ABC$ é isósceles de base $BC$. Por construção, $BE$ e $CD$ são as bissetrizes dos ângulos $A\hat{B}C$ e $A\hat{C}B$, respectivamente. Chame $A\hat{B}C = A\hat{C}B = 2 \theta$. Como $AD // BE$ e $A\hat{B}E = \theta$ então $B\hat{A}D = \theta$ (alternos internos), mas $A\hat{C}B = 2 \theta$ e $CD$ é bissetriz, assim $B\hat{C}D$ também é igual a $\theta$ e o quadrilátero $ADBC$ será inscritível ($B\hat{A}D = B\hat{C}D = 2 \theta$). Da mesma forma, podemos afirmar que $C\hat{A}E = C\hat{B}E = \theta$, já que $AE // CD$ e $BE$ é bissetriz de $A\hat{B}C$, assim o quadrilátero $AECB$ também será inscritível e como três pontos formam uma circunferência única (neste caso, $A,B,C$) temos que $A,B,C,D,E$ são concíclicos.

Por fim, pela última informação $D\hat{B}E = D\hat{C}E$, mas $E\hat{B}C = D\hat{C}B = \theta$ por definição, logo:

$D\hat{B}E = D\hat{C}E \Rightarrow D\hat{B}E + E\hat{B}C = D\hat{C}E + D\hat{C}B \Rightarrow D\hat{B}C = E\hat{C}B \Rightarrow F\hat{B}C = F\hat{C}B$.

Provamos que o triângulo $FBC$ é isósceles de base $BC$, logo $F$ está na mediatriz de $BC$, que também é a bissetriz de $ABC$, já que este triângulo também é isósceles. Logo, $F$,$A$ e $I$ são colineares.

Agora resta mostrar que se $F$, $A$ e $I$ são colineares, então, $AB = AC$.

Observe o triângulo $FIC$, como $IC // AE$, pelo Teorema de Tales:

$\dfrac{FA}{AI} = \dfrac{FE}{EC}$

Agora observe o triângulo $FIB$, como $IB // AD$, novamente pelo Teorema de Tales:

$\dfrac{FA}{AI} = \dfrac{FD}{DB}$

Por fim, chame de $N$ o ponto que $AI$ corta $BC$ e utilize o teorema de Ceva no triângulo $FBC$:

$\dfrac{BN}{NC} \cdot \dfrac{EC}{FE} \cdot \dfrac{FD}{DB} = 1$

Pelos resultados anteriormente encontrados:

$\dfrac{BN}{NC} \cdot \dfrac{AI}{FA} \cdot \dfrac{FA}{AI} = 1 \Rightarrow \dfrac{BN}{NC} = 1 \Rightarrow BN = NC$

O ponto $N$ será ponto médio de $BC$. Para finalizar o problema basta aplicarmos o teorema da Bissetriz Interna relativa ao lado $BC$:

$\dfrac{AB}{AC} = \dfrac{BN}{NC}$

Mas $\dfrac{BN}{NC} = 1 \Rightarrow AB = AC$.

Como queríamos demonstrar! 

Problema 3:

Os números reais $a$, $b$, $r$ e $s$ são tais que as raízes da equação $x^2-ax+b=0$ são $\dfrac{1}{r}$ e $\dfrac{1}{s}$ e as raízes da equação $x^2-rx+s=0$ são $a$ e $b$. Sabendo que $a>0$, encontre o seu valor.

Solução:

Pelas relações de Girrard:

$a=\dfrac{1}{r}+\dfrac{1}{s}$ (1)

$b=\dfrac{1}{r}\cdot\dfrac{1}{s}$ (2)

$r=a+b$ (3)

$s=a\cdot b$ (4)

Substituindo (1) e (2) em (3) temos:

$r=\dfrac{1}{r}+\dfrac{1}{s}+\dfrac{1}{rs}$

$r=\dfrac{r+s+1}{rs}$

$r^2s=r+s+1$

$r^2s-r-(s+1)=0$

Calculando por Bháskara as raízes vemos que:

$r=\dfrac{1\pm\sqrt{1+4s(s+1)}}{2s}$

$r=\dfrac{1\pm\sqrt{4s^2+4s+1)}}{2s}$

$r=\dfrac{1\pm\sqrt{(2s+1)^2}}{2s}$

$r=\dfrac{1\pm (2s+1)}{2s}$ Logo $r=\dfrac{1-2s-1}{2s}=-1$ ou $r=\dfrac{1+2s+1}{2s}=\dfrac{s+1}{s}$

Caso 1: Se $r=-1$, pelo enunciado sabemos que $a>0$, logo de (1):

$a=\dfrac{1}{r}+\dfrac{1}{s}>0$

Como $r=-1$:

$-1+\dfrac{1}{s}>0$ $\dfrac{1}{s}>1>0$

Portanto $\dfrac{1}{s}>0 \Rightarrow s>0$, mas de (4) temos $b=\dfrac{s}{a}$, como $a>0$ e $s>0$, então $b>0$, mas de (3) temos $b=\dfrac{1}{rs} \Rightarrow b=-\dfrac{1}{s}$, logo $b<0$ pois $s>0$, mas $0>b>0$ nos implica um absurdo, logo este caso não possui solução.

Caso 2: Se $r=\dfrac{s+1}{s}$, de (2) temos:

$b=\dfrac{1}{r}\cdot\dfrac{1}{s}$

$b=\dfrac{s}{s+1}\cdot\dfrac{1}{s}$

$b=\dfrac{1}{s+1}$

Aplicando em (4) temos:

$s=a\cdot b$

$s=a\cdot \dfrac{1}{s+1}$

$s(s+1)=a$ (5)

Substituindo $r$ em (1):

$a=\dfrac{1}{r}+\dfrac{1}{s}$

$a=\dfrac{s}{s+1}+\dfrac{1}{s}$

$a=\dfrac{s^2+s+1}{s(s+1)}$

$a=\dfrac{s(s+1)+1}{s(s+1)}$

Mas substituindo por (5) temos:

$a=\dfrac{a+1}{a}$

$a^2=a+1$

$a^2-a-1=0$

Esta equação muito conhecida nos dá como raízes:

$a=\dfrac{1\pm\sqrt{5}}{2}$

Porém do enunciado $a>0$, logo $a=\phi=\dfrac{1+\sqrt{5}}{2}$.

Problema 4:

Considere um triângulo escaleno $ABC$ com $AB < AC < BC$. A mediatriz do lado $AB$ corta o lado $BC$ no ponto $K$ e o prolongamento de $AC$ no ponto $U$. A mediatriz do lado $AC$ corta o lado $BC$ no ponto $O$ e o prolongamento do lado $AB$ no ponto $G$. Prove que o quadrilátero $GOKU$ é cíclico, ou seja, que seus quatro vértices estão em uma mesma circunferência.

Solução:

Chame de $M$ o ponto médio de $AB$ e $N$ o ponto médio de $AC$. Por definição, $MN$ é base média do triângulo $ABC$, assim: $MN // BC \Rightarrow MN // OK$. Voltando ao problema, como $MU$ é mediatriz de $AB$, então $A\hat{M}U$ é ângulo reto. Analogamente, como $NG$ é mediatriz de $AC$, então $A\hat{N}G$ é ângulo reto. Por $A\hat{M}U = A\hat{N}G$ o quadrilátero $GNMU$ é inscritível.

Para provarmos que o quadrilátero $GOKU$ é inscritível, basta mostramos que seus ângulos opostos somam $180$, mas isso, de fato, acontece:

$U\hat{G}O + U\hat{K}O = 180 \Rightarrow U\hat{G}O + U\hat{M}N = 180$

Veja que $U\hat{K}O = U\hat{M}N$, já que $MN // OK$.

Como já tínhamos provado que o quadrilátero $GNMU$ é inscritível, então $U\hat{G}O + U\hat{M}N = 180$ e $GOKU$ também é inscritível.

Problema 5:

Uma permutação $(a_1, a_2, a_3,..., a_{n?1}, a_{n})$ dos números do conjunto ${1,2,3,...,n}$ é legal se não existem dois termos consecutivos cuja soma é um múltiplo de $3$ e se os dois vizinhos de um termo qualquer não diferem por um múltiplo de $3$. Por exemplo, $(4,6,2,5,3,1)$ é uma permutação legal dos números do conjunto ${1,2,3,4,5,6}$. Entretanto, $(1,2,5,3,4,6)$ não é uma permutação legal do mesmo conjunto, pois os números $1$ e $2$ são vizinhos e sua soma é um múltiplo de $3$. Além disso, outra razão para ela não ser legal, é que os vizinhos do número $4$, que são o $3$ e o $6$, diferem por um múltiplo de $3$.

a) Determine o número de permutações legais do conjunto ${1,2,3,4,5,6}$.

b) Determine o número de permutações legais do conjunto ${1,2,3,...,2016}$

 Observação: Uma permutação de um conjunto é uma sequência ordenada contendo cada um de seus elementos uma única vez.

Solução:

Para resolvermos o problema vamos utilizar somente os resíduos dos números do conjunto na divisão por $3$. Mostraremos que é possível determinar com base nos resíduos a quantidade de permutações legais:

Se dispomos do dígito $0$, então o próximo dígito pode ser $1$ ou $2$, mas essa será a única escolha possível que poderemos fazer, de fato, determinado o segundo dígito a sequência está definida:

Se $1$: o próximo dígito não pode ser $2$, já que a soma resultará num múltiplo de $3$, também não pode ser $0$, já que a diferença de dois vizinhos de um termo também não pode ser divisível por $3$, logo só pode ser novamente $1$ e o processo se repete. Da mesma forma se escolhermos o $2$.  Isso acontece, pois suponha que tenhamos determinado os dois últimos dígitos da sequência e esses sejam $a$ e $b$, então o próximo dígito não pode ser $3-b$ (somado com $b$ resulta num múltiplo de $3$) nem $a$ (difere zero de $a$, ou seja, temos uma diferença divisível por $3$), logo há dois casos a considerar:

 - $a$ diferente de $3-b$, então não temos escolha e o número está determinado, como queremos demonstrar!

 - $a$ igual a $3-b$, o que é um absurdo! Note que $a$ e $b$ já são termos definidos da sequência então sua soma não pode ser um múltiplo de $3$, exatamente o que acontece quando $a=3-b$.

Concluímos que escolhidos os dois primeiros dígitos só existe uma forma fixa de termos uma permutação legal, como só estamos analisando os resíduos na divisão por $3$ até agora, então existem seis formas de escolhermos os dois primeiros dígitos (não podemos escolhê-los somando um múltiplo de $3$, o que elimina as escolhas $0 - 0$, $1 - 2$, $2 - 1$) e consequentemente seis permutações legais possíveis (olhando os restos módulo $3$).

Para determinar as permutações legais com base nos números do conjunto basta analisarmos a permutação dos números com mesmo resíduo na divisão por $3$. A nossa análise anterior garantiu por meio da marcação dos resíduos como determinar se uma permutação é legal, a partir disso podemos determinar a quantidade total de permutações contando as possibilidades de trocarmos todos números com resíduo $1$ de “lugar”, assim como os de resíduo $2$ e $3$, supondo que a quantidade de números do conjunto seja $3k$ a quantidade de permutações dentro das posições de um mesmo resíduo será $k!$, logo determinada uma permutação legal com base nos resíduos há $(k!)^3$ formas de preenchê-la com os números do conjunto, como há seis permutações legais possíveis dos resíduos, então um conjunto com $3k$ elementos tem um total de $6 \times (k!)^3$ permutações legais.

A partir disso resolvemos ambos itens:

(a) ${1,2,3,4,5,6}$ tem $6$ elementos, logo $6 \times (2!)^3 = 48$ permutações legais.

(b) ${1,2,3,...,2016}$ tem $2016$ elementos, logo $6 \times (672)^3$ permutações legais.

Problema 6

Seja $a_0=a>1$ um inteiro e, para $n\ge0$, 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:

Vamos supor que o conjunto dos divisores primos é finito, e seja este $S={p_1,p_2,...,p_{k}}$, colocaremos cada subconjunto de $S$ como sendo a definição de uma “casa”, basicamente colocaremos nesta “casa” todos os termos da sequência formados pelos primos deste subconjunto, por exemplo, escolha o subconjunto $S$ ${p_1,p_2,p_5}$, e então faremos uma “casa” com todos os termos da sequência que possuem somente $p_1,p_2,p_5$ em sua fatoração. Como os termos da sequência são infinitos, então pelo Princípio da Casa dos Pombos, alguma de nossas “casas” terá infinitos termos, escolha esta “casa”, seja esta formada pelos primos $p_1,p_2,...p_i$, então existem infinitos termos da nossa sequência formados por somente todos estes primos, tentaremos provar que existem dois termos de nossa sequência tais que um divide o outro. Agora enunciaremos o seguinte algoritimo:

Algoritimo: Seja $a_r=p_1^{\theta_1}p_2^{\theta_2}...p_i^{\theta_i}$ um termo da sequência, fixe $\theta_1$, $\theta_2$, ... , $\theta_i$, agora pegue um termo da sequência qualquer formado por estes mesmos primos, se este numero é da forma $a_s=p_1^{\beta_1}p_2^{\beta_2}...p_i^{\beta_i}$ e $\beta_t<\theta_t$ para todo $t=1,2,...,i$ então $a_s$ divide $a_r$ e acabou, e se $\beta_t>\theta_t$ para todo $t=1,2,...,i$ então $a_r$ divide $a_s$ e acabou, logo resta analisar o caso em que para alguns valores de $t$ temos $\beta_t<\theta_t$ e para outros $\beta_t>\theta_t$, sejam $p_{b_1},p_{b_2},...,p_{b_j}$ os primos tais que $\beta_t<\theta_t$ para $t=b_1,b_2,...,b_j$ e sejam $p_{b_{j+1}},p_{b_{j+2}},...,p_{b_i}$ os primos tais que $\beta_t>\theta_t$ para $t=b_{j+1},b_{j+2},...,b_i$, então se $\theta_{b_h}$ é o expoente de $p_{b_h}$ para todo $h=1,2,...,i$ e $p_{b_h}$ seja $p_t$ para algum $t=1,2,...,i$. Então para todo termo da sequência que é formado pelos primos $p_1,p_2,...,p_i$ podemos separar duas partes deste termo, a parte "menor" formada por $p_{b_1},p_{b_2},...,p_{b_j}$ e seus expoentes e a parte "maior" formada por $p_{b_{j+1}},p_{b_{j+2}},...,p_{b_i}$ e seus expoentes, onde estas duas partes juntas formam o termo da sequência, vejamos que o número de partes "menores" é finito já que como $\beta_t<\theta_t$, existe um número finito de configurações de $\beta_t$ e como a quantidade de termos da sequência é infinito então em alguma desta partes "menores", suponha s.p.g. $p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_w}^{\theta_{c_w}}$ temos infinitos termos da sequência, então existem infinitas partes maiores tal qual os termos formados por estas possuem como parte menor $p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_w}^{\theta_{c_w}}$.

Sabemos agora que esta parte "maior" possui no máximo $i-1$ fatores primos, já que, caso todos fossem maiores, então entraríamos no caso de que $\beta_t>\theta_t$ para todo $t=1,2,...,i$, absurdo. Como existem infinitas partes "maiores", podemos fixar a parte "menor" $p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_w}^{\theta_{c_w}}$ e aplicar o algoritimo novamente na parte "maior" e assim estaremos fixando cada vez mais partes "menores", até que em algum momento teremos fixados exatamente $i-1$ fatores primos: $p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_{i-1}}^{\theta_{c_{i-1}}}$ e restará apenas um fator primo como sendo uma parte "maior", mas então pelo algoritimo partes "maiores" sempre possuem infinitos termos, logo existem infinitos termos que possuem $p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_{i-1}}^{\theta_{c_{i-1}}}$ como parte menor fixada e que possuem o último primo, ou seja, existem infinitos termos da forma: $p_{c_1}^{\theta_{c_1}}p_{c_2}^{\theta_{c_2}},...,p_{c_{i-1}}^{\theta_{c_{i-1}}}p_v^{\theta_v}$ onde $p_v$ é o último primo e $\theta_v$ é variável, logo pegue o menor número dentre todos os valores possíveis para $\theta_v$ e portanto este número divide infinitos outros termos da sequência e então teremos um termo que é divisível por este menor termo, e assim podemos iniciar nossa questão (leia atentamente o algoritimo caso não tenha entendido, sei que existem muitas letras mas isto é só questão de formalidade, recomendamos ao leitor que pegue exemplos pequenos para que possa acompanhar a ideia) . Sabendo que existem $i,j$ tais que $a_i$ divide $a_j$, então temos que:

$a_i \mid a_j$

$2^{a_{i-1}}-1 \mid 2^{a_{j-1}}-1$

Lema: $mdc(2^n-1,2^m-1)=2^{mdc(m,n)}-1$

Prova: se $d=mdc(2^n-1,2^m-1)$ então $2^n-1 \equiv 0 (mod \ d) \Rightarrow 2^n \equiv 1 (mod \ d)$ e $2^m-1 \equiv 0 (mod \ d) \Rightarrow 2^m \equiv 1 (mod \ d)$, portanto se $t$ é a ordem de $2$ módulo $d$, vale que $t \mid m$ e $t \mid n$, logo $t \mid mdc(m,n)$, e portanto $2^{mdc(m,n)} \equiv 1 (mod \ d) \Rightarrow 2^{mdc(m,n)}-1 \equiv 0 (mod \ d)$, então $d \mid 2^{mdc(m,n)}-1$, mas vejamos que se $d=2^{mdc(m,n)}-1$ então $d \mid 2^m-1$ e $d \mid 2^n-1$, logo $d=2^{mdc(m,n)}-1$.

Pelo nosso lema, $mdc(2^{a_{i-1}}-1,2^{a_{j-1}}-1)=2^{mdc(a_{i-1},a_{j-1})}-1$, mas como $2^{a_{i-1}}-1 \mid 2^{a_{j-1}}-1$, então $mdc(a_{i-1},a_{j-1})=a_{i-1}$ e portanto temos que $a_{i-1} \mid a_{j-1}$. Indutivamente vemos que $a_{i-2} \mid a_{j-2}$,...,$a_{0} \mid a_{j-i}$. Chame $j-i=k$, então $a \mid a_k$, logo $a \mid 2^{a_{k-1}}-1$. Agora seja $p$ o menor primo divisor de $a$ (*), então vejamos que:

$2^{a_{k-1}}-1 \equiv 0 (mod \ p)$

$2^{a_{k-1}} \equiv 1 (mod \ p)$

Mas pelo pequeno Teorema de Fermat:

$2^{p-1} \equiv 1 (mod \ p)$

Logo, vale que (pelo lema):

$2^{mdc(a_{k-1},p-1)} \equiv 1 (mod \ p)$

Agora tome $q_{k-1}$ como um divisor primo do $mdc(a_{k-1},p-1)$ (note que isto só pode ocorrer se $mdc(a_{k-1},p-1)$ é diferente de $1$) (**), vejamos que $q_{k-1}\le p-1<p$ e $q_{k-1} \mid a_{k-1}$ e portanto $q_{k-1} \mid 2^{a_{k-2}}-1$, e de modo análogo teremos que:

$2^{mdc(a_{k-2},q_{k-1}-1)} \equiv 1 (mod \ q_{k-1})$

Agora tome $q_{k-2}$ como um divisor primo do $mdc(a_{k-2},q_{k-1}-1)$ (note que isto só pode ocorrer se $mdc(a_{k-2},q_{k-1}-1)$ é diferente de $1$) (**), vejamos que $q_{k-2}<q_{k-1}<p$ e $q_{k-2} \mid a_{k-2}$ e portanto $q_{k-2} \mid 2^{a_{k-3}}-1$. Indutivamente podemos definir a sequência de primos $q_{k-3}, q_{k-4}, ... , q_1, q_0$ da mesma forma, mas perceba que $q_0 \mid a$, mas $p>q_{k-1}>q_{k-2}>...>q_1>q_0$, logo achamos um primo menor que $p$ que divide $a$, absurdo por (*), já que $p$ é o menor primo que divide $a$. Porém vejamos que em algum momento poderíamos ter tido $mdc(a_{k-t-1},q_{k-t}-1=1$ por (**), o que nos impediria de montar a sequência de primos que nos levaria a um absurdo por (*), mas se $t$ é o menor número (***) tal que $mdc(a_{k-t-1},q_{k-t}-1)=1$ então:

$2^{mdc(a_{k-t-1},q_{k-t}-1)} \equiv 1 (mod \ q_{k-t})$ (já demonstramos isto pelo lema) $2^1 \equiv 1 (mod \ q_{k-t})$ $2 \equiv 1 (mod \ q_{k-t})$ $1 \equiv 0 (mod \ q_{k-t})$

Logo $q_{k-t}=1$, mas $q_{k-t}$ divide o $mdc(a_{k-t-2},q_{k-t-1}-1)$, logo se não existe $q_{k-t}$ primo que divide o $mdc(a_{k-t-2},q_{k-t-1}-1)$, então $mdc(a_{k-t-2},q_{k-t-1}-1)=1$, mas então por (***) temos um absurdo pois achamos um número menor que $t$ tal que $mdc(a_{k-r-1},q_{k-r}-1)=1$. Portanto o que supomos no início na verdade era falso e o conjuntos de primos que dividem os termos da sequência $a_n$ é infinito, como queríamos demonstrar.

Obs.: Gostaríamos de salientar que o problema ficaria mais fácil se pudéssemos usar teoremas um pouco mais avançados, como o Teorema de Zsigmondy, mas isto foge do nosso contexto olímpico já que este teorema é tão forte que o problema ficaria quase uma aplicação direta do mesmo, apenas restando prova-lo, porém sua prova é bem complicada e por isso achamos melhor esta resolução utilizando de argumentos relativamente mais simples.