1. ## Quadratic Residues of Primes

Use induction to show that, for all n, there exists a set of n distinct odd primes {p1,...,pn} such that every prime in the list is a quadratic residue modulo anyother prime in the list.

I'm confused as to how we can construct the pk+1 prime such that it is a quadratic residue for {p1,...,pn} and that {p1,...,pn} are quadratic residues of pk+1. Any help solving this problem would be appreciated. Thanks!

2. ## Re: Quadratic Residues of Primes

Here's a sketch of a solution:

Assume that the set of primes ${p_1, p_2, \dots, p_k}$ satisfies the conditions of the problem. It suffices to find a prime $p_{k+1} \equiv 1 \pmod{4}$ such that $p_{k+1}$ is a quadratic residue mod $p_i$ for $i=1, \dots, p_k$. That's because the law of quadratic reciprocity implies that each $p_i$ is then a quadratic residue mod $p_{k+1}$.

Consider the set of congruences

$\\x \equiv 1 \pmod{p_1} \\x \equiv 1 \pmod{p_2} \\. \\. \\.\\x \equiv 1 \pmod{p_k} \\x \equiv 1 \pmod{4}$

Any solution is a quadratic residue mod $p_i$ for all $i=1, 2, \dots, k$. By the Chinese Remainder Theorem, a solution $x_0$ exists and all solutions are of the form $x_0 + rm$, where $r \in \mathbb{Z}$ and $m=4p_1p_2\cdots p_k$. By Dirichlet's theorem, this arithmetic progression contains a prime $p_{k+1} \equiv 1 \pmod{4}$, as required.