4
$\begingroup$

I was studying quadratic reciprocity laws and came across the following question: Is it true that for every $k \in \mathbb{N} $ there exists a prime $p$ such that $1,2,...,k$ are all quadratic residues mod p?

I think this might be true by recurrent use of Dirichlet Theorem, but I'm not quite sure that this idea works every time. For example:

For $k=3$, we need $2$ and $3$ to be quadratic residues, which is accomplished by choosing a prime $p$ that is $ \equiv 1 \mod{8}$ and $ \equiv 1 \mod{3}$ (for example), i.e., a prime of the form $24k+1$, which there are infinitely many by the Dirichlet Theorem. I think we can continue this idea and guarantee that the first primes we want are quadratic residues and, thus, as the product of quadratic residues is also a quadratic residue, the first $k$ naturals. The problem is that we have to connect the law of quadratic reciprocity with some congruence conditions and make sure that we can iterate the process without reaching any contradiction (for example, a prime simultaneously $\equiv 1 \mod{8}$ and $\equiv 3 \mod{4}$).

Does anybody see why or why not does this idea work? Thank you!

$\endgroup$
6
  • $\begingroup$ In fact, something even "stronger" is true: for every $k \in \mathbb N$, all sufficiently large primes $p$ possess at least $k$ consecutive quadratic residues (not necessarily $1, 2, \ldots, k$ of course). $\endgroup$
    – Erick Wong
    Mar 18, 2014 at 0:32
  • $\begingroup$ Nice result! Any reference on it? $\endgroup$
    – u1571372
    Mar 18, 2014 at 0:44
  • $\begingroup$ see oeis.org/A000229 $\endgroup$
    – Will Jagy
    Mar 18, 2014 at 0:55
  • $\begingroup$ @ErickWong, I cannot tell whether you have already been pinged, the OP has asked for a reference for your result. $\endgroup$
    – Will Jagy
    Mar 18, 2014 at 0:57
  • $\begingroup$ Thanks @WillJagy, I only got your subsequent ping. One reference is D. A. Buell and R. H. Hudson, “On runs of consecutive quadratic residues and quadratic nonresidues,” BIT, v. 24, 1984, pp. 243-247. IIRC the proof uses Deligne's well-known bounds on the number of points on curves, but I also know an elementary Ramsey-theoretic argument (which only works for the residue case as opposed to non-residues). $\endgroup$
    – Erick Wong
    Mar 18, 2014 at 1:41

1 Answer 1

Reset to default
4
$\begingroup$

First note that if $a$ and $b$ are quadratic residues modulo $p$ then so is $ab$. So if you want to prove that $n$ is a quadratic residue modulo $p$ for all positive integers $n\le k$, it suffices to prove that $q$ is a quadratic residue modulo $p$ for all primes $q\le k$.

As you have already checked the result for $k=2$ and $k=3$, let's assume $k\ge4$. By Dirichlet's theorem there is a prime $p$ of the form $p=mk!+1$. Then $p\equiv1\pmod4$; if $q$ is prime and $2<q\le k$ we have $q\mid k!$ and so $$\Bigl(\frac{q}{p}\Bigr)=\Bigl(\frac{p}{q}\Bigr)=\Bigl(\frac{1}{q}\Bigr)=1\ .$$ Morevover, if $q=2$ then it is a quadratic residue because $p\equiv1\pmod8$. The result follows.

$\endgroup$

You must log in to answer this question.

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