$(a_{n})_{n=1}^{\infty}$ is an integer sequence, $a_{1}=1$, $a_{2}=2$ and for $n\geq{1}$, $a_{n+2}=a_{n+1}^{2}+(n+2)a_{n+1}-a_{n}^{2}-na_{n}$. $a)$ Prove that the set of primes that divides at least one term of the sequence can not be finite. $b)$ Find 3 different prime numbers that do not divide any terms of this sequence.
Problem
Source: Turkey TST 2019 Day 1 P2
Tags: number theory, Sequence, prime numbers
26.03.2019 21:34
Let $b_n={a_n}^2+na_n$ $a_{n+2}-a_{n+1}=b_{n+1}-b{n}$ $\sum_{i=1}^{n-1}a_{n+2}-a_{n+1}=\sum_{i=1}^{n-1}b_{n+1}-b{n}$ $a_{n+1}=b_n={a_n}^2+na_n$ Let $\mathbb{P}$ be set of primes that divide at least one term of the sequence. Assume that $\mathbb{P}$ is finite and $\mathbb{P}=\{p_1, p_2, \cdots p_k\}$. We know that $a_n|a_{n+1}$ so there exist a $N$ such that for all $n>N$ and for all $i\in \{1,2, \cdots, k\}$, $p_i|a_n$. There exist a sufficient large $t$ such that $tp_1p_2\cdots p_k+1>N$. For $n= tp_1p_2\cdots p_k+1$, $a_n+n$ is relatively prime with all $p_i$ so there is a prime that not in $\mathbb{P}$ and divide $a_{n+1}$. Contradiction. $\mathbb{P}$ is not finite.
28.03.2019 03:25
For b) one can show that the primes $3,5,19$ work by computing the first terms and noticing that the sequence will be periodic.
28.03.2019 20:05
pablock wrote: For b) one can show that the primes $3,5,17$ work by computing the first terms and noticing that the sequence will be periodic. No, actually it is not true for 17. But 19 satisfies the condition. We use this fact for prove this: If $a_n=a_m(modk)$ and $n=m(modk)$ then the sequence will be $(m-n)$ $periodic$ in module $k$
28.03.2019 22:13
How to find the third prime without guessing?
29.03.2019 00:21
ISE wrote: pablock wrote: For b) one can show that the primes $3,5,17$ work by computing the first terms and noticing that the sequence will be periodic. No, actually it is not true for 17. But 19 satisfies the condition. We use this fact for provide this: If $a_n=a_m(modk)$ and $n=m(modk)$ then the sequence will be $(m-n)$ $periodic$ in module $k$ Sorry; corrected
29.03.2019 19:33
rmtf1111 wrote: How to find the third prime without guessing? I have tried it until I can find. Otherwise, if there is an easier way, it would not be 2nd question though, in my opinion. If there is an easier solution, I don't know and could not find. Also the term divisible by $p$ is not so far for $p=7,11,13,17$ and this makes it triable enough. (last edit for @grupyorum)
31.05.2021 02:51
any solution?