数论笔记

310 字
2 分钟
数论笔记
数论笔记

随便写点数论~

数论基础略过

二次剩余#

对于 (a,p)=1(a,p)=1 ,若存在整数 xx 使得

x2≡a(modp)x^2\equiv a\pmod p

则 aa 为模 pp 的二次剩余,否则为二次非剩余

Euler 判别法#

根据费马小定理,二次剩余的一个简单的判据就是考察 ap−12 mod pa^{\frac{p-1}{2}}\bmod p 是 11 还是 −1-1

11 就说明是二次剩余,−1-1 就说明是二次非剩余

这被称为Euler 判别法,当然 p=2p=2 另说

证明

应该没伪证吧

最直接就考虑费马小定理 ap−1≡1(modp)a^{p-1}\equiv1\pmod p

也就是 (ap−12−1)(ap−12+1)≡0(modp)(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)\equiv0\pmod p

ap−12a^{\frac{p-1}{2}} 要么是 11 要么是 −1-1

而对于一个二次剩余 aa ,x2≡a(modp)x^2\equiv a\pmod p

则 ap−12≡xp−1≡1(modp)a^{\frac{p-1}{2}}\equiv x^{p-1}\equiv1\pmod p

满足 ap−12≡1(modp)a^{\frac{p-1}{2}}\equiv1\pmod p 的 aa 至多 p−12\frac{p-1}{2} 个

而二次剩余本身恰好 p−12\frac{p-1}{2} 个

于是

a是二次剩余  ⟺  ap−12≡1(modp)a是二次剩余 \iff a^{\frac{p-1}{2}}\equiv1\pmod pa是二次非剩余  ⟺  ap−12≡−1(modp)a是二次非剩余 \iff a^{\frac{p-1}{2}}\equiv-1\pmod p

二次剩余求解#

很巧妙的一点就是,对于 4k+34k+3 型的 pp 的二次剩余模 pp 下的平方根是容易求得的

然后 4k+14k+1 型的就用到一种 Tonelli-Shanks 这个迭代逼近的算法,

em,查阅发现在算法竞赛中似乎 Cipolla 用的更多?

合数模二次剩余似乎比较困难,约等于质因数分解这样子

咕咕咕

文章分享

如果这篇文章对你有帮助,欢迎分享给更多人!

数论笔记
https://azusaaa.com/posts/number-theory-note/
作者
dsyfb_437
发布于
2026-11-13
许可协议
CC BY-NC-SA 4.0

评论区

正在加载 Twikoo…
Profile Image of the Author
dsyfb_437
My love shines, dims, and flickers. Am I a star, then?
公告
欸,你是怎么发现这个的...
分类
标签
最新动态
站点统计
文章
5
分类
4
标签
8
总字数
5,714
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
Local
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0
文章目录