Elementary Proof for the number of quadratic residues for $n = p_1^{i}p_2^{j}p_3^k...p_\alpha^i$ I would just like to get some help in proving that the number of QRs for $n = p_1^{i}p_2^{j}p_3^k...p_\alpha^i$ is $\frac{\phi(n)}{2^\alpha} $.
Intuitively, I understand that each prime $p^i$ 'brings' $\frac{\phi(p^i)}{2} $ QRs to $n$ and obviously multiplying each of these together gives $\frac{\phi(n)}{2^\alpha} $.
I know this question is similar to:
On the number of quadratic residues $\pmod{pq}$ where$p$ and $q$ are odd primes. 
But could someone help me with how I would make my intuition a more formal generalised proof? 
Many thanks!
 A: Here is a heuristic justification that will give you grounds for more formal justification.
First of all, it should make sense that there are $\frac{p-1}{2}$ quadratic residues $\pmod{p}$, because the congruence $x^{2} \equiv a \pmod{p}$ should have two solutions: $x$ and $-x$, and there are $p-1$ non-zero residues $\pmod{p}$, so we're just pairing each $x$ with a $-x$ to leave $\frac{p-1}{2}$ solutions. Now consider the congruence $x^{2} \equiv a \pmod{n}$, where $n = pq$ and $p$ and $q$ are both odd primes. Remember that $x^{2} \equiv a \pmod{n} \iff x^{2} = a + nk$ for some $k \in \mathbb{Z}$. But remember that since $p \vert n$ and $q \vert n$, so we could get the same $a$ just by dividing $x^2$ by $p$ or $q$.
Well, first of all, it should make sense that there are $\frac{p-1}{2}$ quadratic residues $\pmod{p}$, because the congruence $x^{2} \equiv a \pmod{p}$ should have two solutions: $x$ and $-x$, and there are $p-1$ non-zero elements $\pmod{p}$, so we're just taking half of these. Now consider the congruence $x^{2} \equiv a \pmod{n}$, where $n = pq$ and $p$ and $q$ are both odd primes. Remember that $x^{2} \equiv a \pmod{n} \iff x^{2} = a + nk$ for some $k \in \mathbb{Z}$. But remember that since $p \vert n$ and $q \vert n$, so we could get some of the same $a$ just by dividing $x^2$ by $p$ or $q$. Also note that the set of quadratic residues $\pmod{p}$ is closed under multiplication (because $x^2y^2 = (xy)^2$). So if there are $\frac{p-1}{2}$ residues that we already know will be quadratic $\pmod{n}$ because we know $p \vert n$, it should make sense that we would be able to make more quadratic residues by multiplying each of the $\frac{p-1}{2}$ quadratic residues by the $\frac{q-1}{2}$ quadratic residues as a result of this closure. Because $n$ has only two prime divisors, we know that we can't do this again. So we know that there should then be exactly $\frac{p-1}{2} \cdot \frac{q-1}{2} = \frac{(p-1)(q-1)}{2^2}$ quadratic residues $\pmod{n}$. It should make sense why we can make more or less quadratic residues by this multiplication process which is dependent on the number of prime divisors of $n$. 
