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!
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.