Number of quadractic residues $\mod p$ and $\mod n$. 
Let $p$ be an odd prime.  Then among the integers $\{1,2,3,\cdots,p-1\}$ exactly half are quadratic residues modulo $p$.

I believe the above proposition.  

Let $n$ be an odd, square free integer.  How many integers $\{1,2,3,\cdots,n-1\}$ are quadratic residues mod $n$.

There are exactly $\phi(n)$ integers that are relatively prime to $n$.  Further, we can factor $n=P_1\cdots P_N$.  I keep thinking that the number of integers will be less than $\phi(n)/2$ or $(n-1)/2$.  I'm not sure if I am right or how to prove it.
 A: Let $n\gt 1$ be odd, and consider the set $A$ of $\varphi(n)$ numbers between $1$ and $n-1$ which are relatively prime to $n$. For any $a\in A$, let $f(a)$ be the remainder when $a^2$ is divided by $n$.
Suppose that $f(a)=b$. We ask: how many $x$ are there such that $f(x)=b$? 
We have $f(x)=b$ if and only if $x^2\equiv a^2\pmod n$, or equivalently if and only if $x\equiv at$ for some $t$ such that $t^2\equiv 1\pmod{n}$.
Let $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$, where the $p_i$ are distinct primes, and the $a_i$ are $\ge 1$. We will show that the congruence $t^2\equiv 1\pmod{n}$ has $2^k$ solutions.
It follows that the function $f(x)$ is $2^k$ to $1$,  and therefore the number of quadratic residues of $n$ is $\dfrac{\varphi(n)}{2^k}$. Here by quadratic residue of $n$ we mean a number $b$ relatively prime to $n$ such that $x^2\equiv b\pmod{n}$ has a solution.

It remains to prove the lemma about the number of solutions of $t^2\equiv 1\pmod{n}$.
To solve the congruence $t^2\equiv 1\pmod{n}$ is equivalent to solving the system of congruences $t^2\equiv 1\pmod{p_i^{a_i}}$ ($i=1,2,\dots,k$).
For any $i$, the congruence $t^2\equiv 1\pmod{p_i^{a_i}}$ has $2$ solutions, $t\equiv \pm 1\pmod{p_i^{a_i}}$.  By the Chinese Remainder Theorem, the system of congruence $t\equiv \epsilon_i \pmod{p_i^{a_i}}$, where for any $i$ we have $\epsilon_i=1$ or $\epsilon_i=-1$, has a unique solution modulo $n$. The sequence of $\epsilon_i$ can be chosen in $2^k$ ways, so the congruence $t^2\equiv 1\pmod{n}$ has $2^k$ solutions.
Remark: With some care, we can extend the result to even $n$. The key fact is that the congruence $t^2\equiv 1\pmod{2^{a_0}}$ has $1$ solution if $a_0=1$, $2$ solutions if $a_0=2$, and $4$ solutions if $a_0\ge 3$. 
A: Hint: A number $a$ is a quadratic residues modulo $n=pq$ ($p$, $q$ are primes) if and only if $a$ is a quadratic residues modulo $p$ and modulo $q$. There are $\frac{p-1}{2}$ quadratic residues modulo $p$ and $\frac{q-1}{2}$ quadratic residues modulo $q$. So, how many quadratic residues modulo $pq$ can be obtained?
A: Whenever $\mathbb{Z}_n^{\ast}$ is cyclic and $g$ is a primitive root modulo $n$, then $g^{2l−1}$ for $l = 1, 2,\ldots ,φ(n)/2$ are all the quadratic non-residue modulo $n$, and $g^{2l}$ for $l = 0, 1, · · · , φ(n)/2 − 1$ are all the quadratic residue modulo $n$. Otherwise we can consider the product of cyclic groups and multiply.
