# 欧拉判别法则与勒让德符号

二次剩余

设 $m$ 是正整数，若同余式

$$x^2\equiv a\pmod m,(a,m)=1$$

有解，则 $a$ 称为模 $m$ 的二次剩余；否则， $a$ 称为模 $m$ 的二次非剩余

勒让德符号

设 $p$ 是素数，定义勒让德符号：

$$(\frac{a}{p})=\left\{\begin{matrix} 1 & \text{若 a 是模 p 的二次剩余}\\ -1 & \text{若 a 是模 p 的二次非剩余}\\ 0 & \text{若 p|a} \end{matrix}\right.$$

可以转换成：

若 $x^2\equiv a\pmod p$ 有解，则 $(\frac{a}{p})=1$

一些化简技巧

1. 设 $p$ 是素数，若 $a\equiv b\pmod p$，则 $(\frac{a}{p})\equiv (\frac{b}{p})$

2. 欧拉判别法则：设 $p$ 是奇素数，则对于任意整数 $a$，

   $$(\frac{a}{p})\equiv a^{\frac{p-1}{2}}\pmod p$$

4. 二次互反律：设 $p,q$ 是互素奇素数，则

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

可以记住等式

1. $$(\frac{1}{p})=1$$

2. $$(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}$$

3. $$(\frac{ab}{p})=(\frac{a}{p})(\frac{b}{p})$$

4. $$(\frac{a^n}{p})=(\frac{a}{p})^n,n>0$$

5. $$(\frac{2}{p})=(-1)^{\frac{p^2-1}{2}}$$

习题1

习题2

# 雅可比符号

雅可比符号

设 $m=\prod\limits_{i=1}^{n}p_i$，$p_i$ 是奇素数，对于任意整数 $a$，定义 $a$ 模 $m$ 的雅可比符号为

$$(\frac{a}{m})=\prod_{i=1}^n(\frac{a}{p_i})$$

所有性质和等式和勒让德符号一致

在二次互反的时候将条件削弱成要求都是正奇数

任何奇素数都有 $\frac{p-1}{2}$ 个二次剩余和 $\frac{p-1}{2}$ 个二次非剩余

证明

$$x^2\equiv a\pmod p$$

$a$ 的取值一定时， $x$ 有两个解 $\pm x_0$

可证，在模 $p$ 的简化剩余系中，$\pm x_0$ 不同余

即 $x\to a$ 是二对一的关系，所以 $a$ 的取值只有 $\frac{p-1}{2}$ 个

习题

判断同余式

$$2x^2+x+7\equiv 0\pmod {91}$$

是否有解

如果在实数域上判断 $2x^2+x+7= 0$ 是否有解，我们需要判断 $\Delta$ 是否能开根号

那么放在 $Z_{91}$，可以看成是否存在一个解使得 $x=\sqrt\Delta$，那么就是相当于求 $\Delta$ 是否存在模 $91$ 的二次剩余

$$\Delta=1^2-4\cdot 2\cdot 7=-55$$

利用雅可比符号：

$$(\frac{-55}{91})=1$$

因为是雅可比符号，所以还需要判断是否每一个素因子都是 $1$

$$(\frac{-55}{7})=1\\ (\frac{-55}{13})=1$$

所以原同余式有解

# 阶与指标

阶

设 $<g>$ 是一个 $n$ 元循环群，$a\in<g>$，如果对于正整数 $m$，由

1. $$a^m=e$$

2. 对于任意素因子 $p|m,a^{\frac{m}{p}}\neq e$，则 $ord(a)=m$，且 $m|n$

通俗解释--如何求元素的阶

假设一个群 $<g>$ 的阶是 $63$，求 $a\in<g>$ 的阶

若 $a^{63}=1$ $\Rightarrow$ 验证 $a^{21}$ 是否等于 $1$

• 若 $a^{21}\neq 1$，则 $a$ 的阶是 $63$，$ord(a)=63$
• 若 $a^{21}=1$，则继续比较 $a^7,a^3...$

通俗解释--如何找群的生成元（阶最大的元素）

已知群的阶是 $n$，则找生成元即找一个元素的阶是 $n$

随机找 $a,b$，可以得到 $ord(a)=m_1,ord(b)=m_2$，并且 $m_1,m_2$ 没有互为倍数，即 ${[m_1,m_2]>max\left\{m_1,m_2\right\}}$

存在整数 $s|m,t|n,(s,t)=1,st=[m,n]$，那么 $ord(a^{\frac{m}{s}}b^{\frac{n}{t}})=[m,n]$，即可得到一个比 $m,n$ 阶都大的元素

不断增加新的元素即可

指标

设 $<g>$ 表示由元素 $g$ 生成的一个 $n$ 元循环群，则对于任意 $a\in <g>$，存在 $0\leq i<n,a=g^i$，则称 $i$ 为以 $g$ 为底 $a$ 的指标，记作 $ind_g^a$

^ 设 $<g>$ 是一个 $n$ 元循环群，$a,b\in <g>$，则 $ind_g^{ab}\equiv ind_g^a+ind_g^b\pmod n$

对于 $n$ 元循环群 $<g>$，如果我们事先计算所有的 $g^i,,0\leq i<n$，并列表存储，显然对于任意 $a,b\in<g>$ 和整数 $m$，有

$$ab=g^{ind_g^{ab}}=g^{(ind_g^a+ind_g^b)\pmod n}\\ a^m=g^{ind_g^{a^m}}=g^{mind_g^a\pmod n}$$

原根

设 $m$ 是正整数，整数 $a$ 满足 $(a,m)=1$，$a$ 模 $m$ 的阶 $ord_m(a)$ 是指 $a\pmod m$ 在 $Z_m^*$ 中的阶

若 $Z_m^*$ 为循环群，整数 $a$ 称为模 $m$ 的原根是指 $a\pmod m$ 为 $Z_m^*$ 的生成元

• 当 $m=2,4$ 时，模 $m$ 的原根分别为 $1,3$
• 当 $m=2^n,n\geq 3$ 时，模 $m$ 没有原根
• 当 $m=p^{\alpha}$，$p$ 为奇素数，$\alpha\geq 1$ 时，模 $m$ 一定有原根
• 当 $m=2p^{\alpha}$，$p$ 为奇素数，$\alpha\geq 1$ 时，模 $m$ 一定有原根

当模 $m$ 有原根时，一共有 $\varphi(\varphi(m))$ 个原根

习题1--求模 m 的所有原根

求模 $18$ 的所有原根

$\varphi(18)=6$，所以模 $18$ 的简化剩余系中有 $6$ 个元素，即 ${\left\{1,5,7,13,15,17\right\}}$

这是一个 $6$ 元乘法群，经验证，${5^3\equiv -1\pmod {18},5^2\equiv 7\pmod {18}}$

所以 $ord(5)=6$，即 $5$ 是一个原根

模 $18$ 的所有原根可以表示成 $5^i\pmod {18},(i,6)=1,1\leq i<6$，即共有 $\varphi(6)=2$ 个，分别是 $5,5^5=11$

习题2--求同余式

已知 $6$ 是模 $41$ 的一个原根，且 ${6^{15}\equiv 3\pmod {41}}$，试求同余式 ${x^5\equiv 3\pmod{41}}$

$$ind_6^{x^5}=ind_6^3=15\color{red}{\pmod {40}}$$

即

$$5ind_6^x=15\pmod {40}$$

所以

$$ind_6^x\equiv 3,11,19,27,35\pmod {40}$$

即

$$x\equiv6^3,6^{11},6^{19},6^{27},6^{35}\color{red}{\pmod {41}}$$

计算得

$$x\equiv 11,28,34,12,38\pmod{41}$$

$n$ 次剩余

设 $m$ 是大于 $1$ 的正整数，如果 $n$ 次同余式

$$x^n\equiv a\pmod m,(a,m)=1$$

有解，则 $a$ 称作模 $m$ 的 $n$ 次剩余；否则，$a$ 称作模 $m$ 的 $n$ 次非剩余

设 $m$ 是大于 $1$ 的正整数，$g$ 是模 $m$ 的一个原根，$(a,m)=1,d=(n,\varphi(m))$，那么 $x^n\equiv a\pmod m$ 有解的充要条件是

$$a^{\frac{\varphi(m)}{d}}\equiv 1\pmod m$$

习题3--求同余式解的个数

试求同余式 ${x^{34}\equiv 261\pmod{4500}}$ 的解的个数

$$\left\{\begin{matrix} x^{34}\equiv 1\pmod{2^2} \\ x^{34}\equiv 0\pmod {3^2} \\ x^{34}\equiv 11\pmod{5^3} \end{matrix}\right.$$