课程目录
数论
Number Theory
本页目录
On this page
§4.1
二次剩余
模 p 之下,哪些数能开平方。
定义
设 是奇素数,。若同余式
有解,则 叫做模数 的二次剩余;若无解,则 叫做模数 的二次非剩余。
例:取 ,在缩系 中:
故 是模 的二次剩余, 是模 的二次非剩余。
定理 1
在模数 的缩系 中,有 个模数 的二次剩余和 个模数 的二次非剩余。且 就是模 的全部二次剩余
证明
考虑 ,这 个数中的每一个都对应缩系中的一个二次剩余。
毕竟自己就是平方数嘛😅
注意到:
故 与 模 同余。因此只需考察
下面证明这 个数两两不同余。
反证法:若存在 使得 ,则
由于 , 不能整除 也不能整除 ,矛盾。
故这 个数互不同余,恰好给出 个二次剩余。缩系共有 个数,故剩余 个为二次非剩余。
定理 2(欧拉判别条件)
设 是奇素数,,则
- 是模 的二次剩余 ;
- 是模 的二次非剩余 。
证明
由费马小定理,,即
由于 是素数,必有 或 。
若 是二次剩余,则 使 ,且 。于是
若 ,需证 是二次剩余。
由定理 1,缩系中恰有 个二次剩余,设为 。考虑多项式
对每个二次剩余 ,由正向证明知 ,故 在模 下有 个不同的根。
而 ,由拉格朗日定理,模素数 下 至多有 个根。因此 的根就是全体二次剩余。
若 ,则 是 的根,故 必为二次剩余。
推论: 是二次非剩余。
定理 3(二次剩余乘积性质)
- 模 的两个二次剩余之积仍是二次剩余;
- 二次剩余与二次非剩余之积是二次非剩余;
- 两个二次非剩余之积是二次剩余。
证明
设 均与 互质。由欧拉判别条件:
- 若 都是二次剩余,则 ,积为 ,故 是二次剩余。
- 若一个是二次剩余、一个是二次非剩余,则积为 ,故 是二次非剩余。
- 若两个都是二次非剩余,则积为 ,故 是二次剩余。