Number theoryDifficulty 7.0National Olympiad, round 2Prove itUnited States
For an integer n>0, denote by F(n) the set of integers m>0 for which the polynomial p(x)=x2+mx+n has an integer root.
a. Let S denote the set of integers n>0 for which F(n) contains two consecutive integers. Show that S is infinite but n∈S∑n1≤1.
b. Prove that there are infinitely many positive integers n such that F(n) contains three consecutive integers.
Solution
We prove the following. Claim. The set S is given explicitly by S={x(x+1)y(y+1)∣x,y>0}. Proof. Note that m,m+1∈F(n) if and only if there exist integers q>p≥0 such that m2−4n=p2(m+1)2−4n=q2. Subtraction gives 2m+1=q2−p2, so p and q are different parities. We can thus let q−p=2x+1, q+p=2y+1, where y≥x≥0 are integers. It follows that 4n⟹n=m2−p2=(2q2−p2−1)2−p2=(2q2−p2−1−p)(2q2−p2−1+p)=2q2−(p2+2p+1)⋅2q2−(p2−2p+1)=41(q−p−1)(q−p+1)(q+p−1)(q+p+1)=41(2x)(2x+2)(2y)(2y+2)=x(x+1)y(y+1). Since n>0 we require x,y>0. Conversely, if n=x(x+1)y(y+1) for positive x and y then m=p2+4n=(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). Thus we conclude the main claim. □
From this, part (a) follows as n∈S∑n−1≤(x≥1∑x(x+1)1)(y≥1∑y(y+1)1)=1⋅1=1.
As for (b), retain the notation in the proof of the claim. Now m+2∈S if and only if (m+2)2−4n is a square, say r2. Writing in terms of p and q as parameters we find r2⟺2q2+2=(m+2)2−4n=m2−4n+4m+4=p2+2+2(2m+1)=p2+2(q2−p2)+2=2q2−p2+2=p2+r2(†)
with q>p of different parity and n=161(q−p−1)(q−p+1)(q+p−1)(q+p+1). Note that (by taking modulo 8) we have q≡p≡r(mod2), and so there are no parity issues and we will always assume p<q<r in (†). Now, for every q, the equation (†) has a canonical solution (p,r)=(q−1,q+1), but this leaves n=0. Thus we want to show for infinitely many q there is a third way to write 2q2+2 as a sum of squares, which will give the desired p. To do this, choose large integers q such that q2+1 is divisible by at least three distinct 1mod4 primes. Since each such prime can be written as a sum of two squares, using Lagrange identity, we can deduce that 2q2+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.