On the number of quadratic residues $\pmod{pq}$ where$p$ and $q$ are odd primes. I have read that the formula for the number of quadratic residues $\pmod{pq}$ for odd primes $p$ and $q$ is $\frac{(p-1)(q-1)}{4}$. Is this the case, and if it is, why is it the case and how would one going about proving it? More generally, is there a formula for the number of quadratic residues for any composite modulus $m$ (and if so, why is it so and how would I prove that the formula holds)?
 A: For any $x$ between $1$ and $pq-1$ which is relatively prime to $pq$, let $f(x)$ be the remainder when $x^2$ is divided by $pq$. We show that the function $f$ is $4$-to-$1$. That  yields your formula. 
To show that $f$ is $4$-to-$1$, note that $x^2\equiv y^2 \pmod{pq}$ if and only if $(zx)^2\equiv 1\pmod{pq}$, where $z$ is the multiplicative inverse of $y$. 
Now all we need to do is to show that the congruence $w^2\equiv 1\pmod{pq}$ has precisely $4$ solutions. Note that $w$ is a solution of the congruence if and only if $w^2\equiv 1\pmod{p}$ and $w^2\equiv 1\pmod{q}$. Each of these congruences has $2$ solutions, so using the Chinese Remainder Theorem we find that the congruence $w^2\equiv 1\pmod{q}$ has $4$ solutions. 
Essentially the same argument shows that if $n=p_1^{a_1}\cdots p_k^{a_k}$, where the $p_i$ are distinct odd primes, there are $\frac{\varphi(n)}{2^k}$ numbers $x$ in the interval $[1,n-1]$, relatively prime to $n$, which are squares modulo $n$. Here $\varphi$ is the Euler $\varphi$-function.
Remark: Even $n$ are a little more complicated, one has to treat separately the cases where the highest power of $2$ that divides $n$ is $2^1$ or $2^2$ and the cases where the highest power is $2^k$ for some $k\ge 3$. 
Added: In case the reduction to the congruence $w^2\equiv 1 \pmod{pq}$ seems mysterious, here is a more elementary approach. Let $a$ be fixed. We want to find how many solutions there are to the congruence $x^2\equiv a^2\pmod{pq}$. 
Rewrite this as $(x-a)(x+a)\equiv 0 \pmod{pq}$. The congruence holds if one of $x-a$ or $x+a$ is divisible by $p$, and one of $x-a$ or $x+a$ is divisible by $q$. The $4$ solutions are obtained by setting (1) $x\equiv a \pmod{p}$, $x\equiv a \pmod{q}$; (2) $x\equiv -a \pmod{p}$, $x\equiv -a \pmod{q}$; (3) $x\equiv a \pmod{p}$, $x\equiv -a \pmod{q}$; (4) $x\equiv -a \pmod{p}$, $x\equiv a \pmod{q}$. Each of these systems of $2$ congruences has a unique solution modulo $pq$ by the Chinese Remainder Theorem.  
A: This answer isn't as good as André Nicolas's answer, because he made his very accessible while I'm going to be slightly more abstract. However, if you want to understand the number of quadratic residues for general composite modulus $m$, then this is the way to go about it.
First of all, the Chinese remainder theorem says (among other things) that the (abelian) multiplicative group $(\mathbb Z/pq\mathbb Z)^\times$ is isomorphic to the direct product $(\mathbb Z/p\mathbb Z)^\times \times (\mathbb Z/q\mathbb Z)^\times$.
Next, the existence of primitive roots modulo primes tells us that these individual multiplicative groups are cyclic; that is, $(\mathbb Z/p\mathbb Z)^\times \cong \mathbb Z/(p-1)\mathbb Z$ (where the latter is an additive abelian group) and $(\mathbb Z/q\mathbb Z)^\times \cong \mathbb Z/(q-1)\mathbb Z$. Since we're switching from multiplicative notation to additive notation, sqaruing elements in $(\mathbb Z/p\mathbb Z)^\times$ corresponds to doubling elements in $\mathbb Z/(p-1)\mathbb Z$.
So the squares in $(\mathbb Z/pq\mathbb Z)^\times$ (that is, the quadratic residues modulo $pq$) correspond to the elements of $\mathbb Z/(p-1)\mathbb Z \oplus \mathbb Z/(q-1)\mathbb Z$ where both "coordinates" are even. And there are exactly $\frac{p-1}2 \frac{q-1}2$ of these.
To do the general case, you'd still use the Chinese remainder theorem; at the second step, you'd use the existence of primitive roots modulo any odd prime power (and the slight complication André mentioned when $8\mid m$); at the third step, you'd use what you know about cyclic groups.
