$P$ the set of primes $p$ for which $q$ is a quadratic residue modulo $p$. Show that there is $n$ and $φ(n)/2$ arithmetic progressions such that.. $q$ is a prime and let $P$ be the set of primes $p$ for which $q$ is a quadratic residue modulo $p$.
Show that there is an integer $n$ and $φ(n)/2$ arithmetic progressions
with difference $n$ each, such that $P$ is the union of the primes in these progressions.
Can anyone give me any hint/help? I'm clueless right now..
 A: Apologies about the length: I have not had the time to shorten it.
Case $q=2$: First, to get in the mood, let us deal with the even prime $q=2$. It is a standard result that $2$ is a quadratic residue of the (odd) prime $p$ if and only if $p\equiv \pm 1\pmod{8}$. 
Let $n=8$. Then $\varphi(n)/2=2$, and all primes for which $2$ is a quadratic residue belong to one of the two arithmetic sequences $1,9,17,25,\dots$ or $7,15,23,31,\dots$. Each of the $2$ arithmetic sequences has common difference $8$.
Note that we do not need to take $n=8$. For example, let $n=16$. Then $\varphi(n)/2=4$. Each prime that has $2$ as a quadratic residue belongs to one of the $4$ arithmetic sequences $1,17,33,\dots$ or $9, 25, 41,\dots$ or $7,23,39,\dots$ or $15,31,49,\dots$. It just so happens that $n=8$ is the smallest positive integer with the required property.
Now we look at the cases where $q$ is an odd prime. The analysis is a little different for $q$ of the form $4k+1$ than it is for $q$ of the form $4k+3$. The case $q$ of the form $4k+1$ is the easier one.
First note that in the description of $P$, it should have said odd primes. Minor oversight, but if we allow $p=2$ the result is not correct.
Case $q$ of the form $4k+1$: By Quadratic Reciprocity, we have $(q/p)=(p/q)$. Now whether $(a/q)=1$ or $(a/q)=-1$ is completely determined by the congruence class of $a$ modulo $q$. Of the numbers $1,2,3,\dots,q-1$, exactly half are quadratic residues modulo $q$, and half are quadratic non-residues. So the number of distinct $a$ modulo $q$ which are not congruent to $0$ and which are quadratic residues of $q$ is $(q-1)/2$. Note that this is $\varphi(q)/2$.
Thus if we let $n=q$, then all primes $p$ (indeed all positive integers) for which $(p/q)=1$ belong to one of $\varphi(n)/2$ congruence classes modulo $q$, that is, to one of $\varphi(n)/2$ arithmetic sequences, each with common difference $n$. This is by no means the only possible choice of $n$. For example, we could take $n=2q$, in which case the number of arithmetic sequences does not change, or we could take $n=4q$, in which case the number of sequences doubles (but so does $\varphi(n)$), exactly as we described for the case $q=2$.
Supplementary Remark: By Dirichlet's Theorem on primes in arithmetic progressions, it turns out that each of the $\varphi(n)/2$ arithmetic sequences we have described contains infinitely many primes.
Case $q$ is of the form $4k+3$: Quadratic Reciprocity tells us that if $p$ is of the form $4k+1$, then $(q/p)=(p/q)$. As before, there are exactly $(q-1)/2$ congruence classes modulo $q$ for which this is the case. However, we must build in the fact that $p$ is of the form $4k+1$. By the Chinese Remainder Theorem, there are, modulo $4q$, exactly $(q-1)/2$ numbers congruent to $1$ modulo $4$ and congruent to a quadratic residue of $q$ modulo $q$. Let $n=4q$. Then $\varphi(n)=2(q-1)$, and we have obtained $(q-1)/2$ arithmetic sequences with common difference $n=4q$ that contain all primes $p$ of the form $4k+1$ that are quadratic residues of $q$. This gives us $\varphi(n)/4$ such sequences, exactly half as many as required.
However, we have not yet dealt with the cases where $p$ is of the form $4k+3$. In that case, $(q/p)=-(p/q)$. So in that case $q$ is a quadratic residue of $p$ is and only if $p$ is a quadratic non-residue of $q$. There are exactly $(q-1)/2$ congruence classes modulo $q$ of quadratic non-residues of $q$. Thus by the Chinese Remainder Theorem, there are $(q-1)/2$ congruence classes modulo $4q$ for which $p\equiv 3\pmod{4}$ and $p$ is a quadratic non-residue of $q$. 
This gives us $(q-1)/2$ additional congruence classes modulo $4q$ such that $q$ is a quadratic residue of $p$. So we have obtained an additional $\varphi(n)/4$ sequences with the desired property, giving a total of $\varphi(n)/2$.
Remark: The most complicated case, where $q$ is of the form $4k+3$, will seem less mysterious if you find explicitly the $6$ sequences with common difference $28$ that must contain all odd primes $p$ such that $(7/p)=1$. These will be (i) the $3$ sequences of numbers congruent to $1$ mod $4$ and to one of $1,2,4$ mod $7$ and (ii) the $3$ sequences of numbers congruent to $3$ mod $4$ and to one of $3,5,6$ mod $7$.
