二次剩余

作者: 洛玖言 | 来源:发表于2019-11-03 23:13 被阅读0次

二次剩余

模 $p$ 的二次剩余

我们只需研究形如 $x^2\equiv a\pmod{p}\quad(3)$ 的同余方程即可.
当 $p|a$ 时，（3）仅有一个解 $x\equiv0\pmod{p}$ . 所以下面我们总假定 $p\not|\,a$ .
如果同余方程(3)有解，则称 $a$ 是模 $p$ 的二次剩余（在不引起混淆时，简称为二次剩余）；否则称 $a$ 时模 $p$ 的二次非剩余（简称二次非剩余）

如果同余方程（3）有解，则同余方程（3）恰有两个解. 此外，若 $a$ 是二次剩余，则模 $p$ 同余类 $\bar{a}$ 中每个数都是二次剩余. 对于二次非剩余也是如此.

Legendre符号

对每个整数 $a$ ，定义

$\left(\dfrac{a}{p}\right)=\begin{cases} 1,&如果 a是模p的二次剩余,\\ -1,&如果a是模p的二次非剩余,\\ 0,&如果 p|a. \end{cases}$

定理1

设 $p$ 时奇素数，则模 $p$ 的任意完系中恰有 $\dfrac{p-1}{2}$ 个二次剩余，以及 $\dfrac{p-1}{2}$ 个二次非剩余；并且模 $p$ 的全部二次剩余在

$\displaystyle1^2,2^2,\cdots,\left(\dfrac{p-1}{2}\right)^2$
所属的模 $p$ 的同余类中.

定理2

设 $p$ 为素数，则模 $p$ 的两个二次剩余之积时二次剩余，模 $p$ 的一个二次剩余和一个而二次非剩余之积是而此非剩余，模 $p$ 的两个二次非剩余之积是二次非剩余，模 $p$ 的两个而此非剩余之积是二次剩余。

定理3（欧拉判别法则）

设 $p$ 为奇素数，则

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

推论1

设 $p$ 为奇素数，则

$\left(\dfrac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}=\begin{cases} 1,&\text{if}\;\;p\equiv1\pmod{4}\\ -1,&\text{if}\;\;p\equiv3\pmod{4} \end{cases}$

推论2

设 $p$ 为奇素数，则

$\left(\dfrac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}=\begin{cases} 1,&\text{if}\;\;p\equiv\pm1\pmod{8}\\ -1,&\text{if}\;\;p\equiv\pm3\pmod{8} \end{cases}$

整数与多项式-【目录】

二次剩余

二次剩余

二次剩余

模 $p$ 的二次剩余

Legendre符号

定理1

定理2

定理3（欧拉判别法则）

推论1

推论2

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

二次剩余

二次剩余

二次剩余

模 的二次剩余

Legendre符号

定理1

定理2

定理3（欧拉判别法则）

推论1

推论2

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

模 $p$ 的二次剩余