Help in this proof of Legendre symbols I need help in the second part of this theorem:


I didn't understand the second part of this theorem:

*

*Why can we choose such $j$ and $j'$?


*What does the author mean by "the combined contribution $j$ and $j'$ to $(p-1)!$ is $jj'\equiv a (\mod p)$"?


*why are there $(p-1)/2$ such pairs?
I really need help and I would be very grateful if someone could help me.
Thanks a lot!
 A: We give what is essentially the same proof, but the wording will be different. I take it that you had no trouble with the part of the proof that says that if the Legendre symbol $(a/p)$ is $1$, meaning that $a$ is a QR of $p$, then $a^{(p-1)/2}\equiv 1 \pmod{p}$.
We want to show that if $(a/p)=-1$, meaning that $a$ is a NR of $p$, then $a^{(p-1)/2}\equiv -1\pmod{p}$.
Look at the numbers from $1$ to $p-1$. If $x$ and $y$ are in this interval, call $x$ and $y$ partners if $xy\equiv a\pmod{p}$. First we show that every $y$ has a partner. Since $y$ and $p$ are relatively prime, by Bézout's identity there exist integers $s$ and $t$ such that $sy+tp=1$. It follows that $(as)y+atp=a$, and therefore 
$$(as)y\equiv a\pmod{p}.$$
Let $x$ be the remainder when $as$ is divided by $p$. Then $1\le x\le p-1$ and $xy\equiv a \pmod{p}$. This $x$ is the partner of $y$. The $x$ is unique, for if $xy\equiv x'y\equiv a \pmod{p}$ then by cancellation $x\equiv x'\pmod{p}$. 
Note that $y$ is never her own partner, for if she were we would have $y^2\equiv a\pmod{p}$, contradicting the fact that $a$ is a NR of $p$.
Thus the numbers from $1$ to $p-1$ are divided into couples. There are obviously $(p-1)/2$ couples, since there are $p-1$ people.
The product of the two numbers in any couple is congruent to $a$ modulo $p$. This is by the definition of couplehood.
There are $(p-1)/2$ couples, each of which has product congruent to $a$. So the product of all the numbers in the interval $1$ to $p-1$ is congruent to $a^{(p-1)/2}$ modulo $p$. But by Wilson's Theorem the product of all the numbers from $1$ to $p-1$ is congruent to $-1$ modulo $p$. 
It follows that $a^{(p-1)/2}\equiv -1\pmod{p}$. 
