Let $p$ be an odd prime and $\gcd(a, p) = 1$. We prove that $\left(\frac{a}{p}\right) = (-1)^n$, where $n$ is the number of least positive residues of $a, 2a, \ldots, \frac{p-1}{2}a$ that exceed $p/2$.

By Euler's criterion: $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$

Consider the product: $P = a \cdot 2a \cdot 3a \cdots \frac{p-1}{2}a = a^{(p-1)/2} \cdot \frac{p-1}{2}!$

For each $ka$ where $1 \leq k \leq (p-1)/2$, let $r_k$ be its least positive residue modulo $p$. These residues can be partitioned into:

• Those with $r_k < p/2$ (there are $(p-1)/2 - n$ of them)
• Those with $r_k > p/2$ (there are $n$ of them)

For the larger residues, $p - r_k < p/2$. The crucial observation is that the multiset: $\{r_k : r_k < p/2\} \cup \{p - r_k : r_k > p/2\}$ equals $\{1, 2, \ldots, (p-1)/2\}$ (possibly after reordering).

Therefore: $P \equiv (-1)^n \cdot \frac{p-1}{2}! \pmod{p}$

Comparing with $P = a^{(p-1)/2} \cdot \frac{p-1}{2}!$ and canceling $\frac{p-1}{2}!$: $a^{(p-1)/2} \equiv (-1)^n \pmod{p}$

By Euler's criterion, this gives $\left(\frac{a}{p}\right) = (-1)^n$.

Let $p$ and $q$ be distinct odd primes. We use Gauss's Lemma to count the relevant residues.

Consider the lattice rectangle $R = [0, p/2] \times [0, q/2]$ in $\mathbb{R}^2$. The diagonal line $qx - py = 0$ passes through $(0, 0)$ and $(p/2, q/2)$.

Key insight: The number of lattice points below the diagonal in $R$ (excluding boundary) equals the number from Gauss's Lemma.

Specifically, let $\mu$ be the number of integers $k$ with $1 \leq k < p/2$ such that the fractional part of $kq/p$ exceeds $1/2$. This counts lattice points in the rectangle above the diagonal.

By geometric considerations and symmetry: $\mu = \frac{(p-1)(q-1)}{4} - \text{(lattice points below diagonal)}$

Similarly, let $\nu$ count the corresponding quantity with $p$ and $q$ interchanged.

The total number of interior lattice points in $R$ is: $\frac{(p-1)(q-1)}{4} = \mu + \nu$

By Gauss's Lemma: $\left(\frac{q}{p}\right) = (-1)^\mu, \quad \left(\frac{p}{q}\right) = (-1)^\nu$

Therefore: $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\mu + \nu} = (-1)^{(p-1)(q-1)/4}$

This completes the proof.

We prove $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$.

By Euler's criterion: $\left(\frac{-1}{p}\right) \equiv (-1)^{(p-1)/2} \pmod{p}$

Since both sides are $\pm 1$, congruence modulo $p$ implies equality.

Alternatively, $-1$ is a quadratic residue if and only if the equation $x^2 \equiv -1 \pmod{p}$ has a solution. The multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic of order $p-1$. An element of order $4$ exists if and only if $4 \mid (p-1)$, i.e., $p \equiv 1 \pmod{4}$.

If such an element $g$ exists, then $g^2$ has order $2$, so $g^2 \equiv -1 \pmod{p}$.