Please enable JavaScript.
Coggle requires JavaScript to display documents.
第一章 整除 - Coggle Diagram
第一章 整除
素数与算数基本定理
设𝑝是一个整数，𝑝 ≠ 0， ± 1，如果除了±1， ± 𝑝外，𝑝没有其它的因数，则称𝑝为素数（或者质数，或者不可约数），否则为合数（或者可约数）
合数𝑚的最小的不等于1的正因子𝑝一定是素数，且𝑝 ≤ √m
设整数𝑚 > 1，如果所有不大于 𝑚的素数都不是𝑚的因子，那么𝑚是素数。
素数有无穷多个
算术基本定理
设𝑛是一个大于1的正整数，那么𝑛一定可以分解成一些素数的乘积。若规定𝑛的所有素因子按照从小到大的顺序排列，那么𝑛的分解方式是唯一的。
辗转相除法
𝑎和𝑏的最大公因数一定是正整数，且 (𝑎, 𝑏) = (±𝑎，±𝑏)=
（±𝑏, ±𝑎) ；若𝑎 ≠ 0，则 (𝑎, 0) = 𝑎 。
设𝑎，𝑏是两个不全为0的整数，且𝑎 = 𝑞𝑏 + 𝑟，𝑞，𝑟为整数，
则 (𝑎, 𝑏)= (𝑏, 𝑟) 。
设𝑎，𝑏是两个不全为0的整数，𝑞为整数，则(a,b)=(a±𝑏𝑞, 𝑏) = (𝑎, 𝑏 ± 𝑎𝑞) 。
设𝑎，𝑏是两个正整数， 𝑞𝑖为其欧几里得辗转相除算式的部分商，则由𝑆(0) = 0，𝑆(1) = 1，𝑆(𝑖+1) = 𝑆(𝑖−1) − 𝑞(𝑛−𝑖)𝑆(i)，𝑖 ≥ 1所得的𝑆(𝑛−1)和
𝑆(𝑛)满足𝑆(𝑛−1)𝑎 + 𝑆(𝑛)𝑏 = 𝑟(n)
一次不定方程
设𝑎，𝑏是两个不全为0的整数，则
(1)对于任何正整数𝑘，(𝑘𝑎, 𝑘𝑏) = 𝑘 (𝑎, 𝑏) ；
(2)(a/(a,b),b/(a,b))=1
设𝑎，𝑏，𝑐是三个整数，𝑎 ≠ 0, 𝑐 ≠ 0，若 (𝑎, 𝑏) = 1，则
(𝑎, 𝑏𝑐) = (𝑎, 𝑐) 。
设𝑎，𝑏，𝑐是三个整数，𝑎 ≠ 0，若 𝑎, 𝑏 = 1，𝑎|𝑏𝑐，则𝑎|𝑐。
设𝑎，𝑏是两个不全为0的整数，整系数不定方程𝑎𝑥 + 𝑏𝑦 =𝑐有解的充要条件是(𝑎, 𝑏)|𝑐。此时，若𝑥 = 𝑥0，𝑦 = 𝑦0是方程的一特解，那么方程的所有整数解可以表示为
x=x(0)-(b/(a,b))*t
y=y(0)+(a/(a,b))*t
最小公倍数
设𝑎，𝑏是两个正整数，且 (𝑎, 𝑏) = 1，
(1)若𝑎|𝑐，𝑏|𝑐，则𝑎𝑏|𝑐；
(2) [𝑎, 𝑏] = 𝑎b
设𝑎，𝑏是两个正整数,
(1)对于任何正整数𝑘， [𝑘𝑎, 𝑘𝑏] = 𝑘 [𝑎, 𝑏] 。
(2)[a,b]=ab/(a,b)
(3)若𝑎|𝑐，𝑏|𝑐，则[𝑎, 𝑏]|c
设𝑎1，𝑎2，…，𝑎𝑛是𝑛个不全为0的整数，不妨设𝑎1 ≠ 0，定义
𝑑1 = (𝑎1, 𝑎2) , 𝑑2 = (𝑑1, 𝑎3) , ⋯ , 𝑑𝑛−1 = (𝑑𝑛−2, 𝑎𝑛) ，则 (𝑎1, 𝑎2, … , 𝑎𝑛) = 𝑑𝑛−1
若正整数𝑑是𝑎1，𝑎2， …，𝑎𝑛的最大公因数，则存在整数𝑠1，
𝑠2， …，𝑠𝑛，使得 𝑑 = 𝑠1𝑎1 + 𝑠2𝑎2 + ⋯ + 𝑠𝑛𝑎n
高斯函数
对于 𝑥 ，以下结论成立：
(1)若𝑥 ≤ 𝑦，则 [𝑥] ≤ [𝑦]
(2)整数𝑎满足𝑥 − 1 < 𝑎 ≤ 𝑥 ⇔ 𝑎 = [x]
(3)整数𝑎满足𝑎 ≤ 𝑥 < 𝑎 + 1 ⇔ 𝑎 = [𝑥]
(4)对于任意整数𝑛， [𝑛 + 𝑥] = 𝑛 + [x]
(5)[𝑥 + 𝑦] ≥ [𝑥] + [𝑦] 。
对于整数𝑎，𝑏，且𝑏 > 0，带余除法算式为𝑎 = 𝑞𝑏 +𝑟, 0 ≤ 𝑟 < 𝑏，则 𝑞 =[a/b]
设𝑝是一个素数，则𝑛!中包含𝑝的幂次为∑i≥0[n/p^i]
整除性
任意给定整数𝑎和正整数𝑏 > 0，存在唯一的一对整数𝑞，0 ≤𝑟 < 𝑏，使得： 𝑎 = 𝑞𝑏 + r
整除的性质
若𝑎|𝑏，𝑏|𝑎，则𝑎 = ±b
设整数𝑘 ≠ 0，若𝑎|𝑏，则±𝑘𝑎| ± 𝑘𝑏，反之亦然
对任意整数𝑘，若𝑎|𝑏，则𝑎|𝑘b
若𝑎|𝑏，𝑏 ≠ 0，则(b/a)|b
若𝑎|𝑏，𝑏|𝑐，则𝑎|c
若𝑎|𝑏，𝑎|𝑐，则对任意整数𝑠和𝑡，𝑎|𝑠𝑏 + 𝑡c