Let $ a, b, c$ be integers and $ p$ an odd prime number. Prove that if $ f(x) = ax^2 + bx + c$ is a perfect square for $ 2p - 1$ consecutive integer values of $ x,$ then $ p$ divides $ b^2 - 4ac.$
Problem
Source: IMO ShortList 1991, Problem 14 (POL 3)
Tags: modular arithmetic, number theory, quadratics, Perfect Square, Discriminant, IMO Shortlist
12.11.2008 22:35
To simplify the notation, we use $ \equiv$ for equality in modulo $ p$. Denote $ A$ the set of all modulo of perfect squares. We know $ |A|=\frac{p+1}2$. Case 1) $ a\equiv0$ $ ax^2+bx+c\equiv bx+c$. If $ b\not\equiv0$, we notice $ bx+c$ will go through all the modulo for $ 2p-1$ consecutive $ x$. But those $ ax^2+bx+c$ are perfect squares. We get contradiction with $ |A|=\frac{p+1}2$. Hence, $ b\equiv0$ and $ b^2-4ac\equiv0$. Case 2) $ a\not\equiv0$, $ b\not\equiv0$. Since $ 2a$ and $ p$ are coprimes, we can always find $ d$ such that $ 2ad+b\equiv0$. $ f(x+d)=a(x+d)^2+b(x+d)+c=ax^2+b^*x+c^*$, where $ b^*=2ad+b$ and $ c^*=ad^2+bd+c$. It is easy to see that $ b^*^2-4ac^*=b^2-4ac$. Hence, we can always assume $ b\equiv0$ without loss of generality. Case 3) $ a\not\equiv0$, $ b\equiv0$, $ p>3$. We claim there exists $ u$ such that $ a\equiv u^2$. When $ x\equiv0$, $ c\equiv ax^2+c\equiv f(x)\equiv t^2$ for some $ t$. Assume $ t$ to be even by replacing $ t$ with $ t+p$ when necessary. i) $ c\equiv t^2\not\equiv 4$. Find $ x$ such that $ ax^2+c\equiv (1+\frac{t^2}4)^2$. or $ ax^2\equiv (1+\frac{t^2}4)^2-c\equiv (1+\frac{t^2}4)^2-t^2\equiv (1-\frac{t^2}4)^2\not\equiv0$. Hence $ x\not\equiv0$ and the claim holds. ii) $ c\equiv4$, $ p>5$. Find $ x$ such that $ ax^2+c\equiv (\frac{(1+p)^2}4+4)^2$, or $ ax^2\equiv (\frac{(1+p)^2}4+4)^2-c\equiv (\frac{(1+p)^2}4+4)^2-(2+2p)^2=(\frac{(1+p)^2}4-4)^2$. Notice $ =(\frac{(1+p)^2}4-4)^2\not\equiv0$ when $ p>5$. Again $ x\not\equiv0$ and the claim holds. iii) $ c\equiv4$, $ p=5$. Find $ x$ such that $ ax^2+c\equiv0$. $ ax^2\equiv-c\equiv-4\equiv1$. The claim holds. Now $ f(x)\equiv ax^2+c\equiv (ux)^2+c$. Obviously $ f(x)$ goes through $ A+c$. We know $ f(x)$ goes through $ A$ and $ c\in A$. So $ 2c$ has to be in $ A$, so do $ 3c$, $ 4c$, etc. The only way to make sure $ |A|=\frac{p+1}2$ is to let $ c\equiv0$. Hence, $ b^2-4ac\equiv0$. Case 4) $ a\not\equiv0$, $ b\equiv0$, $ p=3$. Using similar argument above, $ b^2-4ac\equiv0$ holds if $ a\equiv1$. Now consider $ a\equiv-1$. We either have $ c\equiv0$ or $ c\equiv1$. For $ c\equiv0$, we get $ ax^2+c\equiv-1$ when $ x\equiv1$, which contradicts with $ -1\not\in A$. Now consider $ a\equiv-1$, $ b\equiv0$, and $ c\equiv1$. We can look at all possible combination of (a,b,c) with modulo 9 and prove there is no way to find 5 consecutive numbers to give $ f(x)$ whose modulo with 9 all falls into $ \{0,1,4,7\}$. I wish someone gives a more efficient proof.
14.12.2009 13:57
the case $ a \equiv 0 \pmod{p}$ is easy to check. now suppose that $ p \nmid b^2-4ac$ then see here...
09.01.2016 14:16
Dear xxp2000, I think we can prove there exists $u$ such that $a \equiv u^2$ by proving that there exist $d$ such that $p \mid bd+c$. Hence, $ad^2 \equiv f(d) \equiv t^2$.
22.10.2021 21:24
let the variables of x be element of {k,k+1,....k+2p-2} S= [(ax^2+bx+c)/p] ( let [ ] be the lagrange symbol) it's clear that S=2p-1. for an integer a coprime to p it's well known (MONT page 220) that for x is elements of residue class modulo p [(ax^2+bx+c)/p]= (p-1) [a/p] for p|b^2-4ac -[a/p] otherwise it's clear that {k,k+1,....k+2p-2,k+2p-1} contains all residues modulo p twice. Situation 1 : if p and a coprime then other hand S=2( -[a/p]) +1, 2( -[a/p]) -1, 2(p-1) [a/p] +1 ,2(p-1) [a/p] -1. But for p>3 only solution S=2p-1= 2(p-1) [a/p] +1 where [a/p]=1 so p|b^2-4ac. Situation 2 : if p|a then S= [(ax^2+bx+c)/p]= [(bx+c)/p] then if p|b p|b^2-4ac so assume that p and b coprime.then for value of x bx+c will be residues modulo p and we know the number of quadratic rresidues in modulo p is (p-1/2) so S =2(p-1/2)+1 or 2(p-1/2)-1 contridiction . QED.