Arbitary number of primes pairwise quadratic residues

Question

For each $n \in \mathbb{N}$ show that there exists primes $p_1,p_2,\dots ,p_n$ so that $p_i$ is a quadratic residue modulo $p_j$ for each $i \neq j$.

I was given a hint that you can find these primes always in the form $4k+1$ and then I tried to prove this by induction. First I showed that when $n=2$ then you can take $p_1 = 5$ and $p_2 = 29$ and then this holds.

I have been having trouble proving the induction step. I cannot seem to prove that when you have $p_1,p_2\dots,p_{n-1}$ for which is holds then I cannot construct $p_n$ such that this still holds. Any suggestions?

Answer 1

You can do it by induction. Suppose you have constructed $p_1,\dots,p_n$ primes such that $p_i$ is a quadratic residue $\pmod{p_j}$ for $j\ne i$, and that $p_i\equiv 1 \pmod{4}$.

Now consider any prime $q$ such that $q\equiv 1 \pmod{4p_1\cdots p_n}$; it exists by Dirichlet theorem on primes in arithmetic progressions.

Now, $$\left( \frac{p_i}q \right)=\left( \frac q{p_i} \right)=\left( \frac 1{p_i} \right)=1$$ by the reciprocity law. So you can add $q$ to the list of primes.

Note that strictly speaking you only need $q\equiv 1\pmod 4$ and a $q\equiv $ to a non-zero square $\pmod{p_1\cdots p_n}$ for the argument to work.