课程目录
本页目录

§4.1

二次剩余

模 p 之下,哪些数能开平方。

第四章 二次剩余 更新 2026.06.08 6 min 数论 / 二次剩余

定义

设 是奇素数,。若同余式

有解,则 叫做模数 的二次剩余;若无解,则 叫做模数 的二次非剩余。

例:取 ,在缩系 中:

故 是模 的二次剩余, 是模 的二次非剩余。


定理 1

在模数 的缩系 中,有 个模数 的二次剩余和 个模数 的二次非剩余。且 就是模 的全部二次剩余

证明

考虑 ,这 个数中的每一个都对应缩系中的一个二次剩余。

毕竟自己就是平方数嘛😅

注意到:

故 与 模 同余。因此只需考察

下面证明这 个数两两不同余。

反证法:若存在 使得 ,则

由于 , 不能整除 也不能整除 ,矛盾。

故这 个数互不同余,恰好给出 个二次剩余。缩系共有 个数,故剩余 个为二次非剩余。


定理 2(欧拉判别条件)

设 是奇素数,,则

  • 是模 的二次剩余 ;
  • 是模 的二次非剩余 。

证明

由费马小定理,,即

由于 是素数,必有 或 。

若 是二次剩余,则 使 ,且 。于是

若 ,需证 是二次剩余。

由定理 1,缩系中恰有 个二次剩余,设为 。考虑多项式

对每个二次剩余 ,由正向证明知 ,故 在模 下有 个不同的根。

而 ,由拉格朗日定理,模素数 下 至多有 个根。因此 的根就是全体二次剩余。

若 ,则 是 的根,故 必为二次剩余。

推论: 是二次非剩余。


定理 3(二次剩余乘积性质)

  • 模 的两个二次剩余之积仍是二次剩余;
  • 二次剩余与二次非剩余之积是二次非剩余;
  • 两个二次非剩余之积是二次剩余。

证明

设 均与 互质。由欧拉判别条件:

  • 若 都是二次剩余,则 ,积为 ,故 是二次剩余。
  • 若一个是二次剩余、一个是二次非剩余,则积为 ,故 是二次非剩余。
  • 若两个都是二次非剩余,则积为 ,故 是二次剩余。