# 数论（二）

# 5.二次剩余

# 5.1 二次剩余(Quadratic residue (opens new window))和二次非剩余定义

设整数,如果存在 $𝕫$ ,满足,那么称是模的二次剩余,否则就称为模的二次非剩余，用表示模的二次剩余集合，用表示模的二次非剩余集合

# 5.2 举例

# 5.3 定理：欧拉准则

针对质数的二次剩余判定，对于质数,任意，的充分必要条件为

的充分必要条件为

# 5.4 定理

针对合数的二次剩余判定，，那么的充分必要条件为：

# 5.5 举例

# 5.6 定理

对于质数,中有个元素是模的二次剩余，另外个元素是模的二次非剩余

# 5.7 举例

# 5.8 定理

对于两个质数的乘积，那么里恰好有1/4的数，也就是个是二次剩余，一般来说，如果合数n有k个质数因子，那么中的元素中有是二次剩余

# 5.9 举例

# 6. 勒让德-雅可比符号

# 6.1 定义

对于任意质数，和任意，定义勒让德符号(Legendre_symbol (opens new window))为

# 6.2 定理

勒让德符号计算方法

# 6.3 定义

对于合数, 其素因子（可重复），任意整数，定义雅可比符号(Jacobi symbol (opens new window))

注意：雅可比符号不能确定一个数是否是对模的二次剩余（除非是质数），比如

但7并不是143的二次剩余

# 6.4 简写

勒让德符号和雅可比符号也可统一简写为 ,或者

# 7. 模质数的二次平方根

# 7.1 定理

对于质数，如果，那么方程

在有两个解，也就是说a有两个平方根，其中一个在区间，另一个在区间，而且，其中一个平方根也属于模的二次剩余，称为主平方根(pricipal square root)

# 7.2 举例

对于方程

有两个解, 其中

# 7.3 算法：求模为质数时的平方根

# 7.3.1 特殊情况

对于方程
如果,
如果,
如果,

# 7.3.2

对于一般情况的质数,使用Tonelli–Shanks (opens new window)算法求解

# 8. 模合数的二次平方根

参考: https://www.johndcook.com/blog/quadratic_congruences/ (opens new window)

# 8.1 算法模2的幂

对于方程，有解
方程，当时有2个解，
方程, 当时有4个解，

# 8.2 算法模质数的幂

求解方程,
方程有解的充分必要条件是, 也就是a是模p的二次剩余
方程有两个解，使用Hensel's lemma (opens new window)算法
设是的解，有存在使得等式成立，那么是方程的解

# 8.3 举例

求解方程

其中，首先解方程

以为例，使用扩展欧几里得算法求解

同理，求方程

所以，最终方程的两个解是

# 8.4 算法

对于合数，整数, 求解方程
首先求解模质数方程

然后根据中国剩余定理，解方程组

得到，由于每个有两个解，所以最终有个解

# 8.5 举例

按照模为质数的方法解方程

按照中国剩余定理，解以下四个方程组

得到四个解

# 8.6 定理

如果不知道的素因子，那么就模的平方根是非常困难的问题

← 数论（一）数论（三） →