Maths Olympiad Prep

Library / /5 of 8

Algebra Difficulty 7.0 National olympiad Prove it Vietnam

Let a,b,c,α,βa, b, c, \alpha, \beta be the given integers and the sequence (un)(u_n) is defined by u1=α,u2=β,un+2=aun+1+bun+cu_1 = \alpha, u_2 = \beta, u_{n+2} = a u_{n+1} + b u_n + c for all n1n \ge 1.

a) Prove that if a=3,b=2,c=1a = 3, b = -2, c = -1 then there are infinitely many pairs of integers (α;β)(\alpha; \beta) so that u2023=22022u_{2023} = 2^{2022}.

b) Prove that there exists a positive integer n0n_0 such that exactly one of the following two statements is true:

i) There are infinitely many positive integers mm, such that un0un0+1un0+mu_{n_0}u_{n_0+1}\dots u_{n_0+m} is divisible by 720237^{2023} or 17202317^{2023};

ii) There are infinitely many positive integers kk so that un0un0+1un0+k1u_{n_0}u_{n_0+1}\dots u_{n_0+k} - 1 is divisible by 2023.

Solution

a) For a=3,b=2,c=1a = 3, b = -2, c = -1, we have un+2=3un+12un1,n1u_{n+2} = 3u_{n+1} - 2u_n - 1, \forall n \ge 1. By induction, one can prove
un=2αβ+(βα1)2n1+n u_n = 2\alpha - \beta + (\beta - \alpha - 1) \cdot 2^{n-1} + n
for all n1n \ge 1. Then u2023=2αβ+(βα1)22022+2023u_{2023} = 2\alpha - \beta + (\beta - \alpha - 1)2^{2022} + 2023.
For any tZt \in \mathbb{Z}, choose α=(220221)t2021\alpha = (2^{2022} - 1)t - 2021 and β=tα2\beta = t - \alpha - 2. In other words, 2β+α=t2 - \beta + \alpha = t and α+2021+(122022)t=0\alpha + 2021 + (1 - 2^{2022})t = 0, so we have
2αβ+(βα1)22022+2023=α+(2β+α)+2021+(βα2)2202222022=α+t+2021t22022+22022=α+2021+(122022)t+22022=22022. \begin{aligned} & 2\alpha - \beta + (\beta - \alpha - 1)2^{2022} + 2023 \\ &= \alpha + (2 - \beta + \alpha) + 2021 + (\beta - \alpha - 2)2^{2022} - 2^{2022} \\ &= \alpha + t + 2021 - t \cdot 2^{2022} + 2^{2022} \\ &= \alpha + 2021 + (1 - 2^{2022})t + 2^{2022} = 2^{2022}. \end{aligned}
This implies that there exist infinitely many pairs of (α,β)(\alpha, \beta) for u2023=22022u_{2023} = 2^{2022}.

b) Note that 2023=7×1722023 = 7 \times 17^2. Let (rn)(r_n) be the remainder of (un)(u_n) when divided by 2023. Then it is easy to check that (rn)(r_n) is the periodic sequence with some period, denote by T>0T > 0. We consider the following cases:

* If there exists n0Nn_0 \in \mathbb{N}^* such that 7un07 \mid u_{n_0} or 17un017 \mid u_{n_0}. Let consider the first case while the other case does the same. Since 720237 \mid 2023,
i=0mun0+i1(mod2023),m1. \prod_{i=0}^{m} u_{n_0 + i} \neq 1 \pmod{2023}, \forall m \ge 1.
Hence proposition ii) is not satisfied. For all lNl \in \mathbb{N}^*, choose m=(2023l1)Tm = (2023l - 1)T. Because un0+nTun0(mod2023)u_{n_0+nT} \equiv u_{n_0} \pmod{2023}, and 720237 \mid 2023 so un0+nTun00(mod7)u_{n_0+nT} \equiv u_{n_0} \equiv 0 \pmod{7} for all nNn \in \mathbb{N}^*.
Thus the sequence un0,un0+1,,un0+(2023l1)Tu_{n_0}, u_{n_0+1}, \dots, u_{n_0+(2023l-1)T} contains at least 2023 terms which are divisible by 7. Hence,
i=0mun0+i is divisible by 72023. \prod_{i=0}^{m} u_{n_0+i} \text{ is divisible by } 7^{2023}.
Therefore, proposition i) is satisfied.

* If 7un,17un7 \nmid u_n, 17 \nmid u_n for all nNn \in \mathbb{N}^*, choose n0=1n_0 = 1, obviously proposition i) is not satisfied. Otherwise, gcd(un,2023)=1\gcd(u_n, 2023) = 1, so by Euler's theorem,
unφ(2023)1(mod2023),nN. u_n^{\varphi(2023)} \equiv 1 \pmod{2023}, \quad \forall n \in \mathbb{N}^*.
Set a=φ(2023)a = \varphi(2023), for all lNl \in \mathbb{N}^*, then choose k=laTk = laT. We will prove that 2023i=0ku1+i12023 \mid \prod_{i=0}^{k} u_{1+i} - 1. Indeed, we have
u1u1+Tu1+(la1)T(mod2023) u_1 \equiv u_{1+T} \equiv \cdots \equiv u_{1+(la-1)T} \pmod{2023}
u2u2+Tu2+(la1)T(mod2023)u_2 \equiv u_{2+T} \equiv \cdots \equiv u_{2+(la-1)T} \pmod{2023}
......
uTu2TulaT(mod2023).u_T \equiv u_{2T} \equiv \cdots \equiv u_{laT} \pmod{2023}.
Hence uiui+Tui+(la1)Tuia1(mod2023)u_i u_{i+T} \cdots u_{i+(la-1)T} \equiv u_i^a \equiv 1 \pmod{2023} for all i=1,Ti = \overline{1,T}. From this we conclude that i=0ku1+i1(mod2023)\prod_{i=0}^{k} u_{1+i} \equiv 1 \pmod{2023} or 2023i=0ku1+i12023 \mid \prod_{i=0}^{k} u_{1+i} - 1. So proposition ii) is true. \square

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.