二次剩余和Guass互反律

发表于 |

从二次剩余问题，引入Legendre符号，由此一步步导出Guass互反律，最后延伸到Jacobi符号，整个步骤确实连贯优美，脍炙人口。

寒假回家好好调整了一下状态，回学校后感觉还不错，效率也蛮高。发现理图虽然比较破，但是还是很不错的，哈哈哈。每次读潘承洞先生的《数论基础》都觉得受益匪浅，我把自己很喜欢的部分写入到该文中。

二次剩余

考虑如下形式二次同余式
$$ x^2 = a \; (mod \; p) $$
其中 $p$ 是奇素数。

经过简单推理很容易发现，在模 $p$ 的简化系中，二次剩余与二次非剩余各占一半。且容易知道，$1^2,2^2,\cdots,(\frac{p-1}{2})^2$ 都是二次剩余。

Legendre 符号

$$\left( \frac{a}{p} \right) = \left\{ \begin{array}{cc} 1, & a\; R\; p \\ 0, & p\;|\;a \\ -1, & a\; \overline{R}\; p. \end{array} \right.$$
定理1 $\quad -(\frac{a}{p}) (p-1)! \equiv a^{\frac{p-1}{2}} \;(mod \; p)$

Proof: 对于 $p\;|\;a$ 的情形，结论显然。下面考虑 $(p,a)=1$ 的情形，令
$$ S = \lbrace 1,2,\cdots,p-1 \rbrace $$
对任意的 $ x \in S $ 必存在唯一的 $ y \in S $ 为下面同余式的解
$$ yx \equiv a \; (mod \; p) $$

(i) 当 $ (\frac{a}{p}) = -1 $ 时，同余式
$$ x^2 = a \; (mod \; p) $$
无解，所以 $y \neq x $ .因此集合 $S$ 中的元素可以分成 $\frac{p-1}{2} $ 对，我们就有
$$ (p-1)! \equiv a^{\frac{p-1}{2}} \;(mod \; p) $$
(ii) 当 $ (\frac{a}{p}) = 1 $ 时，同余式
$$ x^2 = a \; (mod \; p) $$
有两个解 $x_0$ 和 $p - x_0$.在$S$中去掉这两个数外剩下$p-3$个数分出 $\frac{p-3}{2}$对，则有
$$ (p-1)! \equiv a^{\frac{p-3}{2}}x_0(p-x_0) \;(mod \; p) \equiv - a^{\frac{p-1}{2}} \;(mod \; p) $$ 证毕。

推论2 (Wilson 定理)

$$ (p-1)! \equiv -1 \;(mod \; p) $$
Proof: 定理一 中取 $a=1$即可。

推论3 (Euler 判别法)

$$ \left( \frac{a}{p} \right ) \equiv a^{\frac{p-1}{2}} \;(mod \;p ) $$
Proof: 由定理1和推论2显然。Euler判别法不仅有理论价值(下面都是推论3的直接推论)，由于快速幂的存在，使得Euler判别法在计算时有相当好的效果。

推论4 (Format 小定理) 设 $(a,p)=1$ ,则

$$ a^{p-1} \equiv 1 \;(mod \; p) $$

推论5 $\; (\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$
推论6 $\; (\frac{ab}{p}) =(\frac{a}{p})(\frac{b}{p}) $

推论3说明，我们求 Legendre 符号，可以转化成求 $ (\frac{2}{p}),(\frac{q}{p}) $.

定理7 $\; (\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}}$

Proof:
$$ 2^{\frac{p-1}{2}}(\frac{p-1}{2})! = 2 \cdot 4 \cdots (p-1) \equiv (\frac{p-1}{2})!(-1)^{1+2+\cdots+\frac{p-1}{2}}\;(mod \; p) $$
所以
$$ (\frac{2}{p}) \equiv 2^{\frac{p-1}{2}} \equiv (-1)^{\frac{p^2-1}{8}} \;(mod \; p) $$ 证毕。

定理8 (Guass 二次互反律) 设 $p,q$ 为不同的奇素数，则有

$$ (\frac{p}{q}) (\frac{q}{p}) = (-1)^{\frac{(p-1)(q-1)}{4}}$$

Proof: 略。

这里只是简介的纪录一下比较简洁精彩的部分。更多数论的内容还是很推荐潘承洞先生的书的。另外指数原根等一些知识也讲的特别简洁明了。下面给出我写的求原根的MATLAB代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function d = zhi_shu(g,n)
%---------------------------------------
% 输入：底数g和模n
% 输出：其指数
% 2016-2-16 in FDU by dna049
%---------------------------------------
r = 1;
for d = 1:n
    r = mod(r*g,n);
    if r == 1
        break;
    end
end
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function x = phi_euler(n)
%---------------------------------------
% Euler function in number theory
% 2016-2-16 in FDU by dna049
%---------------------------------------
    if isprime(n)
        x = n-1;
    else
        pn = primes(n);
        x = n;
        for i = pn
            if mod(n,i) == 0
                n = n/i;
                while mod(n,i) == 0
                    n = n/i;
                end
                x = x/i*(i-1);
            end
            if i>n
                break;
            end
        end
    end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function d = yuan_gen_s(p)
%---------------------------------------
% 输入：素数p
% 输出：所有原根
% 2016-2-16 in FDU by dna049
%---------------------------------------
d_now = p-1;
v = ones(1,p);
v(1) = 0;
v(p) = 0;
for i = 2:p-1
    if v(i) == 1
        td = zhi_shu(i,p);
        if td ~= p-1
            tp = 1;
            for j = 1:td
                tp = mod(tp*i-1,p)+1;
                v(tp) = 0;
            end
        end
    end
end
d = 1:p;
d = d(v==1);
end