Given are the integers $a , b , c, \alpha, \beta$ and the sequence $(u_n)$ is defined by $u_1=\alpha, u_2=\beta, u_{n+2}=au_{n+1}+bu_n+c$ for all $n \geq 1$. a) Prove that if $a = 3 , b= -2 , c = -1$ then there are infinitely many pairs of integers $(\alpha ; \beta)$ so that $u_{2023}=2^{2022}$. b) Prove that there exists a positive integer $n_0$ such that only one of the following two statements is true: i) There are infinitely many positive integers $m$, such that $u_{n_0}u_{n_0+1}\ldots u_{n_0+m}$ is divisible by $7^{2023}$ or $17^{2023}$ ii) There are infinitely many positive integers $k$ so that $u_{n_0}u_{n_0+1}\ldots u_{n_0+k}-1$ is divisible by $2023$
Problem
Source: VMO 2023 day 1 P2
Tags: number theory
24.02.2023 21:33
a) We can see that adding a constant $c$ to all $u_n$ does not change the formula for $u_n$, so if we consider all pairs $\alpha = 0$ and $\beta = r$, $r \geq 0$, then considering the sequence shifted by a constant $c = 2^{2022} - u_{2023}$, we get $u_{2023} = 2^{2022}$. b) Suppose that some element is divisible by $p = 7$ or $p = 17$. Considering residue $u_n$ modulo $p$ we get that it must be sequence must repeat, but by backward induction we get that the cycle must contain $0$, so there are infinitely many elements divisible by $p$, now just take any $n_0$ and big enough $M$ such that in $u_{n_0}, u_{n_0 + 1}, \ldots, u_{n_0+M}$ there are at least $2023$ numbers divisible by $p$, then for every $m \geq M$ $u_{n_0}u_{n_0+1}\ldots u_{n_0+m}$ is divisible by $p^{2023}$. Also we can't have that ii) is true because $p ~ | ~ 2023 = 7\cdot17^2$. Suppose now that none of $u_n$ are divisible by $7$ or $17$, then again we have that the sequence is in a cycle mod $2023$, let the smallest cycle be $u_{n_0}, u_{n_0}, u_{n_0 + 1}, \ldots, u_{n_0+T}$, and let $u_{n_0}u_{n_0 + 1}\ldots u_{n_0+M} = A \not\equiv 0 \pmod {2023}$. We can see that $A^{\varphi(2023)} \equiv 1 \pmod{2023}$, so letting $k = M\varphi(2023)t = 1632Mt$ for $t \geq1$, we have $u_{n_0}u_{n_0+1}\ldots u_{n_0+k} \equiv A^{1632t} \equiv 1 \pmod {2023}$. The i) can't be true because no elements are divisible by $7$ or $13$.