5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Victor Miller
    Commented Nov 12, 2010 at 21:02
  • $\begingroup$ 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. $\endgroup$
    – Victor Miller
    Commented Nov 12, 2010 at 21:04
  • $\begingroup$ 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. $\endgroup$
    – Felipe Voloch
    Commented Nov 12, 2010 at 23:41
  • $\begingroup$ @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. $\endgroup$
    – David E Speyer
    Commented Nov 16, 2010 at 19:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .