Maths Olympiad Prep

Library / /21 of 34

Number theory Difficulty 7.0 National Olympiad, round 2 Prove it United States

For an integer n>0n > 0, denote by F(n)\mathcal{F}(n) the set of integers m>0m > 0 for which the polynomial p(x)=x2+mx+np(x) = x^2 + mx + n has an integer root.

a. Let SS denote the set of integers n>0n > 0 for which F(n)\mathcal{F}(n) contains two consecutive integers. Show that SS is infinite but
nS1n1. \sum_{n \in S} \frac{1}{n} \le 1.

b. Prove that there are infinitely many positive integers nn such that F(n)\mathcal{F}(n) contains three consecutive integers.

Solution

We prove the following.
Claim. The set SS is given explicitly by S={x(x+1)y(y+1)x,y>0}S = \{x(x+1)y(y+1) \mid x, y > 0\}.
Proof. Note that m,m+1F(n)m, m+1 \in \mathcal{F}(n) if and only if there exist integers q>p0q > p \ge 0 such that
m24n=p2(m+1)24n=q2. m^2 - 4n = p^2 \\ (m+1)^2 - 4n = q^2.
Subtraction gives 2m+1=q2p22m + 1 = q^2 - p^2, so pp and qq are different parities. We can thus let qp=2x+1q - p = 2x + 1, q+p=2y+1q + p = 2y + 1, where yx0y \ge x \ge 0 are integers. It follows that
4n=m2p2=(q2p212)2p2=(q2p212p)(q2p212+p)=q2(p2+2p+1)2q2(p22p+1)2=14(qp1)(qp+1)(q+p1)(q+p+1)=14(2x)(2x+2)(2y)(2y+2)    n=x(x+1)y(y+1). \begin{aligned} 4n &= m^2 - p^2 \\ &= \left( \frac{q^2 - p^2 - 1}{2} \right)^2 - p^2 \\ &= \left( \frac{q^2 - p^2 - 1}{2} - p \right) \left( \frac{q^2 - p^2 - 1}{2} + p \right) \\ &= \frac{q^2 - (p^2 + 2p + 1)}{2} \cdot \frac{q^2 - (p^2 - 2p + 1)}{2} \\ &= \frac{1}{4}(q - p - 1)(q - p + 1)(q + p - 1)(q + p + 1) \\ &= \frac{1}{4}(2x)(2x + 2)(2y)(2y + 2) \\ \implies n &= x(x + 1)y(y + 1). \end{aligned}
Since n>0n > 0 we require x,y>0x, y > 0. Conversely, if n=x(x+1)y(y+1)n = x(x+1)y(y+1) for positive xx and yy then m=p2+4n=(yx)2+4n=2xy+x+y=x(y+1)+(x+1)ym = \sqrt{p^2 + 4n} = \sqrt{(y-x)^2 + 4n} = 2xy + x + y = x(y+1) + (x+1)y and m+1=2xy+x+y+1=xy+(x+1)(y+1)m + 1 = 2xy + x + y + 1 = xy + (x+1)(y+1). Thus we conclude the main claim. \square

From this, part (a) follows as
nSn1(x11x(x+1))(y11y(y+1))=11=1. \sum_{n \in S} n^{-1} \le \left( \sum_{x \ge 1} \frac{1}{x(x+1)} \right) \left( \sum_{y \ge 1} \frac{1}{y(y+1)} \right) = 1 \cdot 1 = 1.

As for (b), retain the notation in the proof of the claim. Now m+2Sm + 2 \in S if and only if (m+2)24n(m+2)^2 - 4n is a square, say r2r^2. Writing in terms of pp and qq as parameters we find
r2=(m+2)24n=m24n+4m+4=p2+2+2(2m+1)=p2+2(q2p2)+2=2q2p2+2    2q2+2=p2+r2() \begin{aligned} r^2 &= (m+2)^2 - 4n = m^2 - 4n + 4m + 4 = p^2 + 2 + 2(2m+1) \\ &= p^2 + 2(q^2 - p^2) + 2 = 2q^2 - p^2 + 2 \\ \iff 2q^2 + 2 &= p^2 + r^2 \quad (\dagger) \end{aligned}

with q>pq > p of different parity and n=116(qp1)(qp+1)(q+p1)(q+p+1)n = \frac{1}{16}(q-p-1)(q-p+1)(q+p-1)(q+p+1).
Note that (by taking modulo 8) we have q≢pr(mod2)q \not\equiv p \equiv r \pmod 2, and so there are no parity issues and we will always assume p<q<rp < q < r in ()(\dagger). Now, for every qq, the equation ()(\dagger) has a canonical solution (p,r)=(q1,q+1)(p, r) = (q-1, q+1), but this leaves n=0n = 0. Thus we want to show for infinitely many qq there is a third way to write 2q2+22q^2 + 2 as a sum of squares, which will give the desired pp.
To do this, choose large integers qq such that q2+1q^2 + 1 is divisible by at least three distinct 1mod41 \bmod 4 primes. Since each such prime can be written as a sum of two squares, using Lagrange identity, we can deduce that 2q2+22q^2 + 2 can be written as a sum of two squares in at least three different ways, as desired.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.