设 (n,p)=1(n,p)=1, 可以通过如下方式求 (np)(\frac{n}{p}):
取整数 k∈{1,2,…,p−12}k \in \{1,2,\ldots, \frac{p-1}{2}\}，对于每个 kk 的取值计算 nknk 模 pp 的剩余 rkr_k. 设 mm 为：
- 若 rkr_k 为最小非负剩余，则 mm 为所有 rkr_k 中大于 p2\frac{p}{2} 的个数，
- 若 rkr_k 为最小绝对值剩余，则 mm 为所有 rkr_k 中小于 00 的个数，
那么
(np)=(−1)m\left(\frac{n}{p}\right)=(-1)^m
示例
计算 (1119)(\frac{11}{19}).
解：k∈P={1,2,3,4,5,6,7,8,9}k\in P=\{1,2,3,4,5,6,7,8,9\}.
nP={−8,3,−5,6,−2,9,1,−7,4}nP = \{-8,3,-5,6,-2,9,1,-7,4\}.
一共有 4 个元素小于 0，所以 (1119)=(−1)4=1(\frac{11}{19})=(-1)^4=1.
计算 2 的二次剩余
对奇素数 pp，
(2p)=(−1)p2−18={1,p≡±1(mod8)−1,p≡±3(mod8)\begin{aligned} \left(\frac{2}{p}\right)&=(-1)^{\frac{p^2-1}{8}}\\ &=\begin{cases} 1, & p\equiv \pm 1\pmod 8 \\ -1, & p\equiv \pm 3\pmod 8 \\ \end{cases} \end{aligned}
证明
设 P={1,2,…,p−12}P=\{1,2,\ldots, \frac{p-1}{2}\}.
若 pp 为 4k+14k+1 型，则 2P={2,4,…,p−12,p+32,…,p−1}2P=\{2,4,\ldots, \frac{p-1}{2}, \frac{p+3}{2},\ldots, p-1\}，其中 {p+32,…,p−1}\{\frac{p+3}{2},\ldots, p-1\} 均大于 p2\frac{p}{2}，所以 m=p−14m=\frac{p-1}{4}. 所以 (2p)=(−1)p−14\left(\frac{2}{p}\right)=(-1)^{\frac{p-1}{4}}.
若 pp 为 4k+34k+3 型，则 2P={2,4,…,p−32,p+12,…,p−1}2P=\{2,4,\ldots, \frac{p-3}{2}, \frac{p+1}{2},\ldots, p-1\}，其中 {p+12,…,p−1}\{\frac{p+1}{2},\ldots, p-1\} 均大于 p2\frac{p}{2}，所以 m=p+14m=\frac{p+1}{4}. 所以 (2p)=(−1)p+14\left(\frac{2}{p}\right)=(-1)^{\frac{p+1}{4}}.
综上
(2p)={1,p≡±1(mod8)−1,p≡±3(mod8)\begin{aligned} \left(\frac{2}{p}\right) =\begin{cases} 1, & p\equiv \pm 1\pmod 8 \\ -1, & p\equiv \pm 3\pmod 8 \\ \end{cases} \end{aligned}