平方剩余

• 定义
  • 设 $p$ 是奇素数，$(a,p)=1$。
  • 若 $x^2\equiv a(\mathrm{mod}p)$ 有解，称 $a$ 是模 $p$ 的平方剩余 (QR)。
  • 若无解，称 $a$ 是模 $p$ 的平方非剩余 (QNR)。
• 计数定理
  • 在模 $p$ 的简化剩余系中，平方剩余和平方非剩余各占一半，即各有 $\frac{p-1}{2}$ 个。
  • 平方剩余恰好是 $1^2,2^2,\dots ,(\frac{p-1}{2}{)}^2$ 模 $p$ 的值。

1. 定理表述

设 $p$ 是奇素数，整数 $a$ 与 $p$ 互素（即 $\gcd (a,p)=1$）。

• 平方剩余判定： $a$ 是模 $p$ 的平方剩余，当且仅当： $a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$

• 平方非剩余判定： $a$ 是模 $p$ 的平方非剩余，当且仅当： $a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$

Link to original