二次剩余

2019-11-03  本文已影响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}

整数与多项式-【目录】

上一篇下一篇

猜你喜欢

热点阅读