Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I would like to classify the integers $m \geq 2$ for which the four quadratic polynomials $3k^2$, $3k^2+2k$, $3k^2+3k+1$, and $3k^2+5k+2$ together represent all integers modulo $m$. That is, every integer modulo $m$ should be in the range of at least one of these polynomials (where all operations are carried out modulo $m$). Computer evidence suggests that this holds if and only if $m$ is one of the following: $7, 10, 19, 2^j, 3^j, 5^j, 11^j, 13^j, 41^j, 2\cdot3^j, 5\cdot3^j$, where $j \geq 1$.

Does someone see how to prove this? Thank you.

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

For a prime $p>2$, fix a nonsquare $c$. If you find $y$ such that $y/3$ is a non-square (i.e. $y/3=cx^2, x\ne0$) and $y/3 - 1/9 = cz^2, z\ne 0$, then $y$ is not represented by the first two polynomials and I can't be bothered completing the square to write the conditions for the other two. Bottom line is, you find such a $y$ if you can find a point on a curve over the finite field $\mathbb{F}_p$. By Weil, this will happen as soon as $p$ is large enough. So your $m$ can only have prime factors from a finite set. Should be downhill from here.

share|improve this answer
Good start. However, since the set that we're looking at is the union of images of polynomials, a Chinese remainder theorem type argument doesn't work. An interesting generalization of the original questions is given a finite set of polynomials in $\mathbb{Z}[x]$ (say of degree $>1$) is there only a finite set of $m$ such that every point $\bmod m$ is the image of the value of one of the polynomials? –  Victor Miller Nov 12 '10 at 21:02
Added: in this specific case, since for any $m>2$ there's always a $c$ which is a quadratic non-residue mod all the primes dividing $m$ a CR type argument can be made to work. I don't see how to do it in the general case in my last comment. –  Victor Miller Nov 12 '10 at 21:04
Victor, if $y \equiv f(k) \mod m$ then $y \equiv f(k) \mod p$ if $p|m$. I am not using CRT. But for arbitrary polynomials, the complement of their image is not the projection of a curve in one of its coordinates, so yes, your generalization will be harder. –  Felipe Voloch Nov 12 '10 at 23:41
@Victor Miller: Asking for only a finite set of such m will require additional conditions. For example, take the polynomials $k^2$ and $-k^2$. For any prime which is $3 \mod 4$, the union of their images is everything. –  David Speyer Nov 16 '10 at 19:00
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.