文档介绍：数论简介
带余除法
带余除法定理
设a 和b 为整数,b > 0,则存在惟一的整数q 和r 使得a = qb + r,0 r < b
上式称为带余除法。
q 称为不完全商。
r 称为余数。
带余除法
Proof.
考虑形如a - nb 形式的数
r 应该是这些数中最小的非负数
利用反证法说明q , r 是惟一的
带余除法
floor 函数
定义
设x R,小于或等于x 的最大整数称为x 的整数部分,记为[x]。
[x] x < [x] + 1
整除和因子
a = b q + r, 当 r = 0 时,
b 能整除 a
b 是 a 的因子
a 是 b 的倍数
a 和 b 的这种关系记为b|a
若 b 1,b a 则称b为a的真因子。
整除的基本性质
设b > 0,c > 0, 整除有如下性质
1. 若c | b,b | a, 则c | a;
2. 若b | a,则bc | ac;
3. 若c | a,c | b,则对任意整数m,n 有
c |ma + nb。
模运算
设n是一正整数,a是整数,若
a=qn+r, 0≤r<n, 则a mod n=r
若(a mod n)=(b mod n),称为a,b模n同余,记为a≡b mod n
称与a模n同余的数的全体为a的同余类,记为[a],a称为这个同余类的代表元素
模运算
同余的性质
若n|(a-b),则a≡b mod n
(a mod n) ≡(b mod n),则a≡b mod n
a≡b mod n,则b≡a mod n
a≡b mod n, b≡c mod n,则a≡c mod n
求余运算a mod n将a映射到集合{0,1,…,n-1},求余运算称为模运算
模运算
模运算的性质
[(a mod n)+(b mod n)] mod n=(a+b) mod n
[(a mod n)-(b mod n)] mod n=(a-b) mod n
[(a mod n)×(b mod n)] mod n=(a×b) mod n
模运算
例:Z8={0,1,2,3,4,5,6,7},模8加法和乘法
+
0
1
2
3
4
5
6
7
0
0
1
2
3
4
5
6
7
1
1
2
3
4
5
6
7
0
2
2
3
4
5
6
7
0
1
3
3
4
5
6
7
0
1
2
4
4
5
6
7
0
1
2
3
5
5
6
7
0
1
2
3
4
6
6
7
0
1
2
3
4
5
7
7
0
1
2
3
4
5
6
×
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
6
7
2
0
2
4
6
0
2
4
6
3
0
3
6
1
4
7
2
5
4
0
4
0
4
0
4
0
4
5
0
5
2
7
4
1
6
3
6
0
6
4
2
0
6
4
2
7
0
7
6
5
4
3
2
1