Legendre's Theorem and Quadratic Reciprocity

As Gauss noted already, his Quadratic Reciprocity Law cannot be deduced from Legendre's Theorem without the existence of primes in arithmetic progressions. Here the deduction is made, with Dirichlet's Theorem replaced by the more elementary result of Selberg, which states that every non-square is a quadratic residue to half the primes.