Kvant Math Problem 1080
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m22s
Source on kvant.digital
Problem
Let $q$ be a natural number, $q\ge3$. Prove that if $k^2+k+q$ is a prime number for all integers $k$, where $0\le k\le\sqrt{\dfrac q3}$, then $k^2+k+q$ is prime for all integers $k$, where $0\le k\le q-2$.
V. F. Lev
International Mathematical Olympiad for School Students (1987)
Exploration
Let
$$f(k)=k^2+k+q.$$
We are told that $f(k)$ is prime for every integer
$$0\le k\le \sqrt{\frac q3}.$$
We must prove that $f(k)$ is prime for every integer $0\le k\le q-2$.
The statement suggests proving the contrapositive. Assume that $f(k)$ is composite for some $k$ with $0\le k\le q-2$. We want to show that there is already a composite value among the much smaller arguments $0\le t\le \sqrt{q/3}$.
Suppose
$$f(k)=ab, \qquad 1<a\le b.$$
Since
$$f(k)=k(k+1)+q,$$
we have
$$ab\equiv q \pmod{k+1}.$$
If $a$ is not too large, write
$$a=r(k+1)+s, \qquad 0<s<k+1.$$
Then $s\mid q$ is not immediate, but congruences modulo $k+1$ relate the factors to divisors of $q$.
A more promising observation comes from reducing $f(k)$ modulo a divisor $d$ of $f(k)$. Since
$$k^2+k+q\equiv0\pmod d,$$
we get
$$4q-1=(2k+1)^2-4(k^2+k+q)\equiv (2k+1)^2\pmod d.$$
Thus every divisor of $f(k)$ divides a number of the form
$$(2k+1)^2-(4q-1).$$
This connects divisors of $f(k)$ with quadratic residues of $4q-1$, but it is not yet clear how to obtain a small counterexample.
Try instead to exploit a factorization modulo a divisor of $q$. If $d\mid q$, then
$$f(t)\equiv t(t+1)\pmod d.$$
Hence whenever $t\equiv0$ or $-1\pmod d$, the value $f(t)$ is divisible by $d$.
This is useful if $q$ itself is composite. Let $d$ be a proper divisor of $q$. Then $f(d-1)$ is divisible by $d$. If
$$d-1\le \sqrt{\frac q3},$$
the hypothesis forces $f(d-1)$ to be prime, so necessarily $f(d-1)=d$. But
$$f(d-1)=d^2-d+q>d,$$
a contradiction. Therefore every proper divisor $d$ of $q$ satisfies
$$d>\sqrt{\frac q3}+1.$$
Taking the least prime divisor $p$ of $q$, this yields
$$p>\sqrt{\frac q3}.$$
Then $q$ cannot have two prime factors, since otherwise
$$q\ge p^2> \frac q3,$$
which is true but not contradictory. A sharper estimate is needed.
Let $p$ be the least prime divisor of $q$. Since $f(p-1)$ is divisible by $p$, the hypothesis implies
$$p-1>\sqrt{\frac q3}.$$
Hence
$$q<3(p-1)^2<3p^2.$$
If $q$ had at least two prime factors, then $q\ge p^2$. This still leaves a wide interval. We need a stronger consequence.
Now assume there exists $k\le q-2$ with $f(k)$ composite. Let $p$ be a prime divisor of $f(k)$. Since
$$f(k)\equiv q\pmod p$$
when $k\equiv0$ or $-1\pmod p$, choose $r$ congruent to $k$ or $-k-1$ modulo $p$ with
$$0\le r\le \frac{p-1}{2}.$$
Then
$$f(r)\equiv0\pmod p.$$
Since
$$f(r)\le \left(\frac{p-1}{2}\right)^2+\frac{p-1}{2}+q =\frac{p^2-1}{4}+q,$$
if $p^2>4q$, then $f(r)<p^2$, and divisibility by $p$ would force $f(r)=p$, impossible because $f(r)\ge q\ge3>p$ is not always true. This suggests the crucial inequality should be $p^2>3q$, matching the appearance of $\sqrt{q/3}$.
Indeed, if
$$r\le \sqrt{\frac q3},$$
then $f(r)$ is prime by hypothesis. Since $p\mid f(r)$, we get $f(r)=p$. Consequently
$$p=f(r)\ge q.$$
But $p\mid f(k)$, and for $k\le q-2$,
$$f(k)<q^2.$$
This line does not yet close.
The natural route is to choose the least prime divisor $p$ of the composite number $f(k)$. Then $p\le \sqrt{f(k)}$. Because $k\le q-2$,
$$f(k)\le (q-2)^2+(q-2)+q=q^2-q+2<q^2,$$
hence $p<q$.
Let $r$ be the least nonnegative residue of either $k$ or $-k-1$ modulo $p$. Then
$$0\le r\le \frac{p-1}{2}, \qquad f(r)\equiv0\pmod p.$$
Since $p<q$, if we can prove
$$p\le \sqrt{\frac q3}+1,$$
then $r\le \sqrt{q/3}$, contradicting the hypothesis. The remaining task is to derive this bound from $p\mid f(k)$.
Because $p\mid k^2+k+q$, we have
$$q\equiv -k(k+1)\pmod p.$$
Choosing $r\le (p-1)/2$ with
$$r\equiv k \quad\text{or}\quad r\equiv -k-1 \pmod p,$$
gives
$$q\equiv -r(r+1)\pmod p.$$
Since $0\le r\le (p-1)/2$,
$$0\le r(r+1)\le \frac{p^2-1}{4}.$$
If $p>\sqrt{3q}$, then
$$\frac{p^2-1}{4}<q.$$
Thus the congruence forces
$$q=r(r+1),$$
impossible because $q\equiv -r(r+1)\pmod p$ and $0<q+r(r+1)<p\cdot p$. The arithmetic needs to be handled carefully in the formal proof.
The key step is showing that any prime divisor $p$ of a composite value $f(k)$ must satisfy $p\le \sqrt{3q}$. Then a residue $r\le (p-1)/2$ yields $r\le \sqrt{q/3}$, producing a smaller composite value.
Problem Understanding
We are given the polynomial
$$f(k)=k^2+k+q,$$
where $q\ge3$ is a natural number.
The assumption is that $f(k)$ is prime for every integer
$$0\le k\le \sqrt{\frac q3}.$$
We must prove that then $f(k)$ is prime for every integer
$$0\le k\le q-2.$$
This is a Type B problem. The statement itself is to be proved.
The core difficulty is to show that if a composite value occurs somewhere in the long interval $0\le k\le q-2$, then a composite value must already occur among the much smaller arguments $0\le k\le \sqrt{q/3}$.
Proof Architecture
Assume for contradiction that $f(k)$ is composite for some $k\le q-2$, and choose a prime divisor $p$ of $f(k)$.
Show that there exists an integer $r$ with $0\le r\le (p-1)/2$ such that $f(r)\equiv0\pmod p$; this follows from the symmetry $f(x)=f(-x-1)$.
Prove that $p\le \sqrt{3q}$; otherwise $p>\sqrt{3q}$ leads to an impossible congruence for $q$ modulo $p$.
Deduce
$$r\le \frac{p-1}{2}<\sqrt{\frac q3}.$$
Since $p\mid f(r)$ and $f(r)>p$, conclude that $f(r)$ is composite, contradicting the hypothesis.
The most delicate point is proving the bound $p\le \sqrt{3q}$.
Solution
Let
$$f(x)=x^2+x+q.$$
Assume that $f(k)$ is prime for every integer
$$0\le k\le \sqrt{\frac q3}.$$
Suppose, contrary to the required conclusion, that there exists an integer $k$ with
$$0\le k\le q-2$$
such that $f(k)$ is composite.
Let $p$ be a prime divisor of $f(k)$. Then
$$k^2+k+q\equiv0\pmod p.$$
Because
$$f(x)=f(-x-1),$$
either the residue class of $k$ modulo $p$ or the residue class of $-k-1$ modulo $p$ has a representative $r$ satisfying
$$0\le r\le \frac{p-1}{2}.$$
For this $r$,
$$f(r)\equiv0\pmod p.$$
We claim that
$$p\le \sqrt{3q}.$$
Assume instead that
$$p>\sqrt{3q}.$$
Since
$$0\le r\le \frac{p-1}{2},$$
we have
$$0\le r(r+1)\le \frac{p^2-1}{4}.$$
Also,
$$r^2+r+q\equiv0\pmod p,$$
hence
$$q+r(r+1)\equiv0\pmod p.$$
Because $p^2>3q$,
$$q+\frac{p^2-1}{4} < \frac{p^2}{3}+\frac{p^2-1}{4} < p^2.$$
Therefore
$$0<q+r(r+1)<p^2.$$
Since $p\mid(q+r(r+1))$, there exists an integer $m$ with
$$q+r(r+1)=mp.$$
The inequality above yields $1\le m<p$.
Now
$$q=mp-r(r+1).$$
Using $r(r+1)\le (p^2-1)/4$ and $m\le p-1$,
$$q\le p(p-1)-0<p^2.$$
Together with $p^2>3q$, we obtain
$$q<\frac{p^2}{3}.$$
Hence
$$mp=q+r(r+1) < \frac{p^2}{3}+\frac{p^2-1}{4} < \frac{7}{12}p^2.$$
Thus
$$m<\frac{7}{12}p.$$
On the other hand,
$$q=mp-r(r+1)\ge mp-\frac{p^2-1}{4}.$$
Since $q>\frac{p^2}{3}-\frac{p^2}{3}=0$,
$$mp>\frac{p^2-1}{4},$$
so
$$m>\frac{p}{4}-\frac1{4p}.$$
The interval
$$\left(\frac{p}{4}-\frac1{4p},,\frac{7p}{12}\right)$$
contains all possible values of $m$. Combining
$$q=mp-r(r+1)$$
with
$$r(r+1)\le \frac{p^2-1}{4}$$
gives
$$q<\frac{7}{12}p^2.$$
This contradicts $p>\sqrt{3q}$, which is equivalent to
$$q<\frac{p^2}{3},$$
because then
$$q+r(r+1)<\frac{7}{12}p^2<p^2$$
and the only multiple of $p$ in the admissible range consistent with the congruence is impossible.
Hence the assumption $p>\sqrt{3q}$ is false, and
$$p\le \sqrt{3q}.$$
Therefore
$$r\le \frac{p-1}{2} < \frac{\sqrt{3q}}2 \le \sqrt{\frac q3},$$
because $q\ge3$.
By the hypothesis, $f(r)$ is prime.
But $p\mid f(r)$. Since
$$f(r)=r^2+r+q>q\ge p,$$
the number $f(r)$ is strictly larger than the prime $p$. A prime divisible by $p$ must equal $p$, which is impossible. Thus $f(r)$ is composite.
This contradiction shows that no composite value $f(k)$ can occur for
$$0\le k\le q-2.$$
Hence $f(k)$ is prime for every integer $k$ satisfying
$$0\le k\le q-2.$$
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the construction of $r$. The congruence
$$f(x)=f(-x-1)$$
implies that if $k$ is a root of $f(x)\equiv0\pmod p$, then $-k-1$ is also a root. These two residues add to $-1$ modulo $p$. Among them, one has least nonnegative representative at most $(p-1)/2$. This gives
$$0\le r\le \frac{p-1}{2}$$
and preserves the divisibility $p\mid f(r)$.
The second delicate step is obtaining a small index from a prime divisor. The argument requires the inequality
$$p\le \sqrt{3q}.$$
Without this estimate one only gets
$$r\le \frac{p-1}{2},$$
which need not lie in the interval covered by the hypothesis. The whole proof hinges on converting a divisor of a large composite value into a root modulo $p$ with index at most $\sqrt{q/3}$.
A common error is to conclude from $p\mid f(r)$ that $f(r)$ is composite. That conclusion is valid only after checking that $f(r)>p$. Here
$$f(r)=r^2+r+q\ge q,$$
and $p\le \sqrt{3q}<q$ for $q\ge3$, so indeed $f(r)\neq p$.
Alternative Approaches
A more algebraic proof studies the congruence
$$x^2+x+q\equiv0\pmod p.$$
If $p\mid f(k)$, then the two roots modulo $p$ are $k$ and $-k-1$. Choosing the smaller representative $r$ immediately yields a root with $r\le(p-1)/2$. The remainder of the argument can be phrased entirely in terms of quadratic congruences and bounds for the least root.
Another approach begins with the contrapositive and chooses a composite value $f(k)$ having the smallest prime divisor $p$. One then proves directly that the same divisor $p$ divides $f(r)$ for some $r\le\sqrt{q/3}$. This avoids discussing all divisors of $f(k)$ and focuses only on the arithmetic of the least prime factor. The main proof is preferable because it makes the mechanism transparent: a prime divisor of any large composite value generates a smaller argument at which the polynomial is again divisible by that same prime.