Quadratic congruence, given p is an odd prime, how to prove $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}$ (mod $p$)

Question

Theorem 3.1, part 1. Let $p$ be an odd prime. Then, every $a \in \mathbb{Z}$ satisfies $\left(\dfrac{a}{p}\right) \equiv a^{\left(p-1\right)/2}\mod p$, where $\left(\dfrac{a}{p}\right)$ denotes the Kronecker symbol.

This is the proof from the textbook (Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition 1991):

For the last third line, I don't understand what's the relation between $jj'$ and $(p-1)!$. "The combined contribution of $j$ and $j'$ to $(p-1)!$", does it mean $jj'^{(p-1)!}$? (This is part of an argument that if $\left(\dfrac{a}{p}\right) = -1$, then $a^{\left(p-1\right)/2} \equiv -1 \mod p$.)

Can anyone explain or show me a better proof?

Answer 1

Explanation: For odd prime $p.$ When $a$ is a non-square modulo $p$:

Partition the set $\{1,2,...,p-1\}$ into a collection of pairs $\{j,j'\}$ where $jj'\equiv a.$ For each such pair we have $j'\not \equiv j$ because $a$ is a non-square mod $p.$ Each member of $\{1,2,...,p-1\}$ belongs to just one of these pairs, because if $\{j,j'\}$ and $\{j,j''\}$ are two such pairs then $jj'\equiv a\equiv jj''\not \equiv 0,$ so $j'=j''$.

Let $S$ be the set of all these pairs. The main point is that $$(1).\quad \prod_{\{j,j'\} \in S} \left(jj'\right) \equiv (p-1)!$$ because each member of $\{1,2,...,p-1\}$ occurs exactly once ( as $j$ or $j'$) on the LHS of (1). And also $$(2),\quad \prod_{\{j,j'\} \in S} \left(jj'\right) \equiv a^{(p-1)/2}$$ because there are $(p-1)/2$ pairs in $S$ and for each $\{j,j'\}\in S$ we have $jj'\equiv a.$ Therefore $$\left( \frac {a}{p} \right)=-1\equiv (p-1)!\equiv a^{(p-1)/2}.$$

Answer 2

Here is another proof. All $\equiv$ symbols are congruences modulo $p$. First, since $\left(a^{\frac{p-1}{2}}\right)^2 \equiv 1$ you have $$a^\frac{p-1}{2} \equiv \pm 1 \,.$$

Let $b$ be a primitive root modulo $p$. Then $$a\equiv b^k \,.$$

If $\left( \frac{a}{p} \right)=-1$ then $k$ is odd.

Assume for contradiction that $$a^\frac{p-1}{2} \equiv 1 \,.$$ Then $b^{k \frac{p-1}{2}} \equiv 1$ and hence $$p-1 |k \frac{p-1}{2} \,.$$

It is easy to conclude that $2|k$.