Prove that there exists an infinite sequence of positive integers $a_1,a_2,a_3,\dots$ such that for any positive integer $k$, $a_k^2+a_k+2023$ has at least $k$ distinct positive divisors.
Problem
Source: 2023 Thailand MO Day 2 P9
Tags: number theory, factorization
12.05.2023 10:34
Let $P(x)=x^2+x+2023$. If there are only finitely many primes that divide $P(x)$ for positive integers x then their density will be exponential and density of $P(x)$ will be quadratic so it isn't possible. Then use CRT to find suitable $a_k$
12.05.2023 11:33
Consider sequence $b_1,b_2,…$ which $b_1 = 1$ , $b_{k+1}^2=b_k^2+2b_k+2023$ for all positive integer $k$ , $b_{k+1}^2+b_{k+1}+2023 \equiv (b_k^2+2b_k+2023)^2+(b_k^2+2b_k+2023)+2023 \equiv$ 0 (mod $b_k^2+b_k+2023$) Thus, $b_k^2+b_k+2023 \mid b_{k+1}^2+b_{k+1}+2023$ and we observed that $b_k^2+b_k+2023 < b_{k+1}^2+b_{k+1}+2023$ Hence by induction, we kill the problem. (way too easy for P9 )
12.05.2023 11:45
Basically the same as USAMO 2008 P1.
13.05.2023 12:26
Here is an intersting solution. Lemma: For all prime numbers $p\equiv 1\pmod{899}$, $\exists 1\leq n\leq 899$ satisfying $$p\mid (n^2+n+2023).$$Lemma prove: $\Leftrightarrow p\mid 4(n^2+n+2023)=(2n+1)^2+8091\Leftrightarrow\left(\frac{-8091}p\right)=1.$ $$\begin{aligned} \left(\frac{-8091}p\right) &=\left(\frac{-1}p\right)\left(\frac{3}p\right)^2\left(\frac{29}p\right)\left(\frac{31}p\right)\\ &=(-1)^{\frac{p-1}{2}}\cdot (-1)^{\frac{(29-1)(p-1)}4}\left(\frac{p}{29}\right)(-1)^{\frac{(31-1)(p-1)}4}\left(\frac{p}{31}\right)\\ &=(-1)^{p-1}\left(\frac{p}{29}\right)\left(\frac{p}{31}\right)\\ &=\left(\frac{1}{29}\right)\left(\frac{1}{31}\right)\\ &=1.\blacksquare \end{aligned}$$Back to the problem, as there are infinite primes satisfying $p\equiv 1\pmod{899}$, use CRT and we are done.
13.05.2023 18:48
Why does the problem have to ask for a sequence $a_1,a_2,a_3,\dots$? Isn't it just: For any positive integer $k$, prove that there is a positive integer $a$ such that $a^2+a+2023$ has at least $k$ distinct positive divisors.
13.05.2023 18:48
just use P(P(x)+x)=P(x)P(x+1) with P(x) = x^2+bx+c with whatever b,c