Let $q$ be an odd prime number. Prove that it is impossible for all $(q-1)$ numbers \[1^2+1+q, 2^2+2+q, \dots, (q-1)^2+(q-1)+q\]to be products of two primes (not necessarily distinct).
Problem
Source: 2023 Grosman MO, P4
Tags: quadratics, number theory, prime numbers
22.11.2023 15:18
\[ (q-1)^2+(q-1)+q=q^2\] Excuse me?
22.11.2023 15:36
The problem wants us to show that it is impossible for all numbers, not just one.
22.11.2023 20:19
We can manually check that this is impossible for $q \leq 13$, so assume $q \geq 17$ now. Let $q+2=p_1p_2$ and $q+6=p_3p_4$, where $p_1 \leq p_2$ and $p_3 \leq p_4$ are primes. Since the gcd of $q+2$ and $q+6$ divides $4$, and $q$ is odd, it must be $0$. Thus $p_1 \neq p_3$. Now, the only two squares which differ by $4$ are $0$ and $4$, hence $q+2$ and $q+6$ cannot simultaneously be square. If $q+2$ is square, then $p_1 \leq \sqrt{q+2}$. Otherwise, $p_1 \neq p_2 \implies p_2 \geq p_1+2$; in this case I claim that $p_1 \leq \sqrt{q-1}$. Indeed, if not we have $p_1 \geq \sqrt{q+2}$ since $\sqrt{q}$ is not an integer, and $\sqrt{q+1}$ isn't either since then we could factor $q$ as a difference of squares (here we use $q \geq 5$), but then $q+2>(\sqrt{q+2})^2$ which is a contradiction. Analogously, if $q+6$ is square, then $p_3 \leq \sqrt{q+6}$. Otherwise, we get $p_3 \leq \sqrt{q-1}$ or $p_3 \geq \sqrt{q+2}$. In the latter case, $q+6 \geq \sqrt{q+2}(\sqrt{q+2}+2)=q+2+2\sqrt{q+2}$, but for $q \geq 3$ this is also false. Thus it follows that $p_1p_3 \leq \sqrt{(q-1)(q+6)}=\sqrt{q^2+5q-6} \implies p_1p_3 \leq q+2$. Call a residue class $r$ modulo $p_1p_3$ good if it satisfies $r \in \{1,-2\} \pmod{p_1}$ and $r \in \{2,-3\} \pmod{p_3}$. If $r$ is a good residue, then $p_1p_3 \mid r^2+r+q$. Call a positive integer good if it's in a good residue class. Suppose $p_1 \neq 3$ and $p_3 \neq 5$; then by CRT there are exactly four good residues. On the other hand, since none of these residue classes are zero, at least two good integers must fall into $[1,q-1]$, so there exist distinct integers $i,j \in [1,q-1]$ such that $i^2+i+q=p_1p_3=j^2+j+q$: absurd. If $p_1=3$ and $p_3 \neq 5$ then we get $p_1p_3 \leq 3\sqrt{q+6} \leq q$. By CRT, there are exactly two good residues, and since these are again nonzero they have members in $[1,q-1]$, so the same argument finishes. If $p_1=3$ and $p_3=5$, then $q \equiv 4 \pmod{15}$, so it's either $19$ or at least $34$. $q=19$ fails since $7^2+7+19=75$, and otherwise we have $p_1p_3 \leq q/2$. Thus there exists a (nonzero) good residue in $[1,q/2)$, hence there are two good integers in $[1,q-1]$ again: one in $[1,q)$ and another in $(q,q-1]$, and the same argument finishes. $\blacksquare$