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!

  • $\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 '14 at 0:32
  • $\begingroup$ Nice result! Any reference on it? $\endgroup$ – u1571372 Mar 18 '14 at 0:44
  • $\begingroup$ see oeis.org/A000229 $\endgroup$ – Will Jagy Mar 18 '14 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 '14 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 '14 at 1:41

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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