Let $a, b, c$ be integers and let $p$ be an odd prime with \[p \not\vert a \;\; \text{and}\;\; p \not\vert b^{2}-4ac.\] Show that \[\sum_{k=1}^{p}\left( \frac{ak^{2}+bk+c}{p}\right) =-\left( \frac{a}{p}\right).\]
Problem
Source:
Tags: algebra, polynomial, absolute value, Quadratic Residues, pen
25.05.2007 03:24
We start by evaluating the sum $\mod p$: $\left( \frac{a}{p}\right) \equiv a^\frac{p-1}{2}\mod p$. Write the polynomial $(ax^{2}+bx+c)^\frac{p-1}{2}= \sum_{k=0}^{p-1}a_{k}x^{k}$ with leading coefficient $a_{p-1}\equiv \left( \frac{a}{p}\right) \mod p$ and remember that $\sum_{x=1}^{p}x^{n}\equiv 0 \mod p$ for $0 \leq m < p-1$ by http://www.problem-solving.be/pen/viewtopic.php?t=676. We get: \[\sum_{x=1}^{p}\left( \frac{ax^{2}+bx+c}{p}\right) \equiv \sum_{x=1}^{p}\sum_{k=0}^{p-1}a_{k}x^{k}= \sum_{k=0}^{p-1}a_{k}\sum_{x=1}^{p}x^{k}\equiv a_{p-1}\sum_{x=1}^{p}x^{p-1}\equiv-\left( \frac{a}{p}\right) \mod p\] As the sum has definitely absolute value $\leq p$, we just have to exclude the case $\sum_{k=1}^{p}\left( \frac{ak^{2}+bk+c}{p}\right) = (p-1) \cdot \left( \frac{a}{p}\right)$. If this happens, all but one of the summands have to be the same, namely $1$ or $-1$. Thus there is exactly one residue class $r \mod p$ such that $ar^{2}+br+c \equiv 0 \mod p$. Dividing out $x-r$ from $ax^{2}+bx+c$, we are left with a linear term having no root $\not\equiv r$, thus we get $ax^{2}+bx+c \equiv a(x-r)^{2}\mod p$, thus the discriminant $b^{2}-4ac$ is $0 \mod p$, which we excluded.
02.10.2018 18:11
Similar, but I believe is shorter. Using the substitution, $ax^2+bx+c = a[(x+b/2a)^2 + (4ac-b^2)/4a^2]$, and letting $(x+b/2a)=k$, and $(4ac-b^2)/4a^2=m$, we need to prove that, $$ \sum_{k=1}^p \left(\frac{a(k^2+m)}{p}\right)=-\left(\frac{a}{p}\right)\iff \sum_{k=1}^p \left(\frac{k^2+m}{p}\right)=-1. $$To prove this, we use Euler's criterion, $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\pmod{p}$, and write the sum above as, $$ \sum_{k=1}^p (k^2+m)^{\frac{p-1}{2}}. $$Now, using the fact that, for every $1\leq \ell\leq p-2$, $p\mid 1^\ell + 2^\ell +\cdots +(p-1)^\ell$, the expression above is congruent to, $\sum_{k=1}^p k^{p-1}\equiv p-1\pmod{p}$. In particular, using the fact that Legendre's symbol takes values in the set $\{-1,1\}$, the expression above is between $-p$ and $p$, and is congruent to $-1$ in modulo $p$, hence is either $-1$, or $p-1$. But it is easy to see that it cannot be equal to $p-1$ (if $\ell$ of them is $1$, and $p-\ell$ is $-1$, we would have, $2\ell-p=p-1$, giving $2\ell =2p-1$, a contradiction). Hence, the claim follows.
03.04.2020 16:09
@2above there is a typo. Instead of $m$ in the fourth line it should be $n$.