Thặng dư bậc hai

Nó biến một câu hỏi tồn tại (có $x$ nào bình phương ra $a$ không?) thành một phép lũy thừa modulo duy nhất, chính điều này khiến ký hiệu Legendre tính được và có tính nhân.

Vì $(\mathbb{Z}/p\mathbb{Z})^{*}$ là nhóm xyclic cấp $p-1$ (một sự kiện chuẩn cho môđun nguyên tố), ta cố định một căn nguyên thủy $g$ và viết $a \equiv g^k \pmod p$ với $0 \le k \le p-2$. Thặng dư bậc hai theo môđun $p$ chính là các lũy thừa chẵn của $g$: nếu $a=g^{2m}$ thì $x=g^m$ thỏa $x^2\equiv a$, và ngược lại mọi bình phương $x^2=(g^j)^2=g^{2j}$ đều là lũy thừa chẵn. Vậy $a$ là thặng dư bậc hai đúng khi $k$ chẵn.

Bây giờ tính $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$. Nếu $k$ chẵn, viết $k=2m$; khi đó $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$ theo định lý Fermat nhỏ, khớp với trường hợp thặng dư.

Nếu $k$ lẻ, thì $g^{k(p-1)/2}$ là một căn bậc hai của $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$, nên $a^{(p-1)/2}\equiv \pm 1$. Nó không thể bằng $1$: nếu vậy, cấp của $g$ phải chia hết $k(p-1)/2$, nhưng $\operatorname{ord}(g)=p-1$ và $k$ lẻ nghĩa là $k(p-1)/2$ không phải bội của $p-1$ trừ khi $(p-1)/2$ đã là bội, mâu thuẫn với việc $g$ là căn nguyên thủy có cấp đúng bằng $p-1$. Vậy $a^{(p-1)/2}\equiv -1\pmod p$ đúng khi $k$ lẻ, tức đúng khi $a$ là bất thặng dư.

Gộp cả hai trường hợp: $a^{(p-1)/2}\equiv 1\pmod p$ khi và chỉ khi $a$ là thặng dư bậc hai, và $\equiv -1$ trong trường hợp còn lại, đó chính xác là phát biểu $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$.

Nó nói rằng việc $p$ có là số chính phương theo môđun $q$ hay không và việc $q$ có là số chính phương theo môđun $p$ hay không thực ra là cùng một câu hỏi, sai khác một dấu chỉ phụ thuộc vào lớp dư của $p,q$ theo môđun $4$ — biến một bài toán hai biến trông khó thành một quy tắc một dòng.

Ta dùng bổ đề Gauss làm bước đệm: với số nguyên tố lẻ $p$ và $\gcd(a,p)=1$, xét các số dư dương nhỏ nhất của $a, 2a, \dots, \frac{p-1}{2}a$ theo môđun $p$, gọi $\mu$ là số lượng trong chúng vượt quá $p/2$. Bổ đề Gauss phát biểu $\left(\dfrac{a}{p}\right)=(-1)^{\mu}$; điều này suy ra từ việc ghép mỗi số dư "lớn" $r$ như vậy với $p-r\le p/2$ và theo dõi dấu khi nhân $\frac{p-1}{2}$ số theo hai cách khác nhau.

Sự tinh chỉnh của Eisenstein biểu diễn $\mu$ như một phép đếm điểm nguyên: người ta chứng minh $\mu \equiv \sum_{k=1}^{(p-1)/2} \left\lfloor \frac{kq}{p} \right\rfloor \pmod 2$ khi $a=q$ lẻ, bằng cách so sánh $\lfloor kq/p\rfloor$ (số bội của $p$ nhỏ hơn $kq$) với khoảng cách của $kq \bmod p$ tới $p/2$. Áp dụng cùng lập luận đếm một cách đối xứng cho $\left(\frac{q}{p}\right)=(-1)^{S(q,p)}$ và $\left(\frac{p}{q}\right)=(-1)^{S(p,q)}$, trong đó $S(q,p)=\sum_{k=1}^{(p-1)/2}\left\lfloor \frac{kq}{p}\right\rfloor$ và $S(p,q)=\sum_{k=1}^{(q-1)/2}\left\lfloor \frac{kp}{q}\right\rfloor$.

Về mặt hình học, $S(q,p)+S(p,q)$ đếm số điểm nguyên $(x,y)$ với $1\le x\le \frac{p-1}{2}$, $1\le y\le \frac{q-1}{2}$ nằm hẳn dưới đường thẳng $qx=py$ (đếm được $S(q,p)$ điểm) cộng với số điểm nằm hẳn trên đường đó (đếm được $S(p,q)$ điểm, do vai trò đối xứng của $p,q$). Không điểm nguyên nào nằm đúng trên đường thẳng vì $\gcd(p,q)=1$ và $x<p$, nên hai phép đếm này phủ kín toàn bộ hình chữ nhật gồm $\frac{p-1}{2}\cdot\frac{q-1}{2}$ điểm nguyên.

Do đó $S(q,p)+S(p,q) = \frac{p-1}{2}\cdot\frac{q-1}{2}$, và nhân hai công thức ký hiệu Legendre lại cho $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{S(p,q)+S(q,p)}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, đúng bằng $\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$.