Show that $a$ is a quadratic residue mod $p$ if and only if a set has even cardinality 
Let $p$ be an odd prime and let $a$ be an integer that is not divisible by $p$. Show that $a$ is a quadratic residue mod $p$ if and only if
  $$|\{a, 2a, . . . ,((p − 1)/2)a\} ∩ \{(p + 1)/2 , (p+1)/2 + 1, ... , p-1\}|$$
  is even.

I tried hard to think about this question but so far I don't have any direction, and I'm stuck. Any help is really appreciated.
 A: The equivalence that you have mentioned is called Gauss's lemma, and you can find another proof in the wikipedia page.
Proof
Let $p$ be an odd prime and $a$ an integer such that $\gcd(a,p)=1$.
Define $S = \left\{{a, 2a, 3a, \ldots, \dfrac {p-1} 2 a}\right\} $. Now construct $R\subset [1,p-1]$ by replacing in $S$ every element by its residue modulo $p$. Let's write the elements of $R$ in an increasing order in the following way:
$$R = \left\{{b_1, b_2, \ldots, b_m, c_1, c_2, \ldots, c_n}\right\}$$
with $b_1<b_2<\ldots <b_m<\dfrac{p}{2} <c_1<c_2< \ldots<c_n $ and obviously we have $n+m=\frac{p-1}{2}$ (as the elements in the original set are different). Now take any $c_i$ and any $b_j$ we must have $b_j\neq p-c_i$ otherwise we can find $1\leq s\leq\frac{p-1}{2}$ and $1\leq r\leq \frac{p-1}{2}$ such that  $b_j\equiv sa \pmod p $ and $c_i\equiv ra \pmod p $ which gives us the following contradiction:
$$p\equiv (r+s)a\pmod p \text{ and } 2\leq r+s\leq p-1$$
Hence the set $R'=\left\{{b_1, b_2, \ldots, b_m, p-c_n, \ldots,p-c_2,p-c_1}\right\}$ contains $\frac{p-1}{2}$ different elements from the range $\left[1,\frac{p-1}{2}\right]$ and therefore:
$$R'= \left\{{1, 2, 3, \ldots, \dfrac {p-1} 2 }\right\}\tag{*}$$
All the operations that we have done conserve the product $\pmod p$ hence:
$$\begin{align}\left({\frac {p-1} 2}\right)!
&=& \prod_{x\in R'}x &\tag{using (*)}\\
&\equiv & (-1)^n \prod_{x\in R} x & \pmod p\tag{Def. $R\to R'$}\\
&\equiv & (-1)^n\prod_{x\in S}  x & \pmod p\tag{Def. $R\equiv_pS$}\\
&\equiv & (-1)^n a^{\frac{p-1}{2}}\left({\frac {p-1} 2}\right)!& \pmod p\tag{Def. $S$}
\end{align}$$
From this equation and $\gcd \left\{{p, \left({\dfrac {p-1} 2}\right)!}\right\} = 1 $ we get the identity :
$$(-1)^n\equiv a^{\frac{p-1}{2}} \pmod p\tag{**}$$
Now returning to your problem we can see that the intersection you are looking for is :
$$\left\{x\pmod p\big / x\in S\right\}\cap\left[{\dfrac{p+1}{2},p-1}\right]=\left\{{c1,\ldots,c_n}\right\} $$
So, what you are trying to do is to show that $a$ is a quadratic residue if and only if $n$ is even which can be done easily using what we have proved so far :
$$\begin{align}
\left|\left\{x\pmod p\big / x\in S\right\}\cap\left[{\dfrac{p+1}{2},p-1}\right] \right| \text{ is even } &\iff & n \text{ is even } \\
& \iff & 1\equiv a^{\frac{p-1}{2}} \pmod p\\
& \iff & a \text{ is quadratic residue } \pmod p
\end{align}
$$
And the proof terminates here.
