数论浅谈
English speaker can click here.
本篇博客将会介绍一些浅显的模数数论
同余
同余其实只是一种表达式
符号
如果 a ÷ m = k ······ b
那么我们会写成 a ≡ b (mod m)
这个就是同余方程的书写。
一些定理
1. 如果 (a,b) = 1,那么一定存在一个k使k·a ≡ 1(mode m)
k写作a-1称作a关于m的逆元。
2.同余方程满足除了除法以外的所有等式的性质。
乘法逆元的求法
我们可以用扩展欧几里得。
首先我们考虑扩展欧几里得的本体,
xa+ym = gcd(x,y)
因为gcd(a,m) = 1
所以xa+ym = 1
仔细观察,这个的本质就是辗转相除法,
所以
int kzojld(int a,int b,int &x,int &y) { if(b==0) { x=1; y=0; return a; } int r=kzojld(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r; }
欧拉函数
定义
比x小的所有与x互质的数的个数
通项
欧拉定理
内容
aφ(m)≡ 1 (mod m)
关于这个公式我就不具体解释了。
证明
我们用X1,X2……Xφ(m)来表示所有与a互质的数。
我们根据一个定理:所有与m互质的同余类构成一个群。
关于
所以我们可以把{X1,X2……Xφ(m)}看成一个群,
通常这个被称作模m的简化剩余系,或者整数模m剩余群。
而群阶为φ(m),所以aφ(m)≡ 1 (mod m)
(关于群,环,域,过段时间我会再写一篇随笔)
费马小定理
内容
一个质数p。
ap-1 ≡ 1(mod p)
证明
费马小定理其实就是欧拉定理的特例,证明就自己理解吧。
应用
1.部分数求逆元。
中国剩余定理
ax ≡ c (mod n)
bx ≡ d (mod m)
(mod[m,n])