# Arbitary number of primes pairwise quadratic residues

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?

## 1 Answer

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.