信息安全数学基础 Chapter 1——整除

定理1.1 任意给定整数a和正整数b>0，存在唯一的一对整数q，0≤r≤b，使得a=qb+r

推论1 任意给定整数a和正整数b<0，存在唯一的一对整数q，$0\le r\le |b|$，使得a=qb+r
推论2 任意给定整数a,c和整数b≠0，存在唯一的一对整数q,c≤r≤|b|+c，使得a=qb+r

定义1.1 整除、倍数、因子、商

定理1.2 设a,b,c为整数：
(1) 若a|b，b|a，则a=b
(2) 设整数k≠0，若a|b，则ka|kb，反之亦然
(3) 对任意整数k，若a|b，则a|kb
(4) 若a|b，b≠0，则$\frac{b}{a}|b$
(5) 若a|b，b|c，则a|c
(6) 若a|b，a|c，则对任意整数s和t，a|sb+tc（裴蜀定理）

定义1.2 公因数、互素

定理1.3 设a,b为两个不全为0的整数，且a=qb+r，q，r为整数，则(a,b)=(b,r)

推论 设a,b为两个不全为0的整数，q为整数，则(a, b)=(a±bq, b)=(a, b±aq)

定理1.4 设a,b为两个正整数，r_n-2=q_n-1r_n-1+r_n，0≤r_n≤r_n-1为欧几里得辗转相除算式，则：
(1) (a,b)=r_n
(2) 存在整数s,t，使得r_n=sa+tb
(3) 任意整数c，若满足c|a且c|b，则c|r_n

定理1.5 设a,b为两个正整数，上式为其欧几里得辗转相除算式，则由S₀=0，S₁=1，S_i+1=S_i-1-q_n-iS_i，n≥i≥1递推所得的S_n-1和S_n满足S_n-1a+S_nb=r_n

证明：写成矩阵形式

定理1.6 设a,b为两个不全为0的整数，则
(1) 对于任意正整数k，(ka,kb)=k(a,b)
(2) $(\frac{a}{(a,b)},\frac{b}{(a,b)})=1$

定理1.7 设a,b,c是三个整数，a≠0，c≠0，若(a,b)=1，则(a,bc)=(a,c)

定理1.8 设a,b是两个不全为0的整数，关于x和y的整系数不定方程ax+by=c有整数解的充要条件是(a,b)|c。若x=x₀，y=y₀是方程的一个特解，那么方程的所有整数解都可以表示为：$x=x_0-\frac{b}{(a,b)}t, y=y_0+\frac{a}{(a,b)}t,t\in\mathbb Z$

定义1.3 多个数的公因数、最大公因数、互素

定理1.9 设a₁,a₂,…,a_n是n个不全为0的整数，不妨设a₁≠0，定义d₁=(a₁, a₂)，d₂=(d₁, a₃)，…，d_n-1=(d_n-2, a_n)，则d_n-1=(a₁, a₂, … a_n)

推论 设正整数d是a₁，a₂，…，a_n的最大公因数，存在s₁，s₂，…，s_n有d=s₁a₁+s₂a₂+…+s_na_n

定理1.10 正整数c是a₁，a₂，…，a_n的最大公因数，当且仅当：
(1) c|a₁, c|a₂, …, c|a_n
(2) 任一整数d若满足d|a₁, d|a₂, …, d|a_n，则d|c

定义1.4 公倍数、最小公倍数

定理1.11 设a,b为两个正整数，且(a,b)=1
(1) 若a|c，b|c，则ab|c
(2) [a,b]=ab

定理1.12 设a,b为两个正整数
(1) 对于任何正整数k，[ka, kb]=k[a,b]
(2) $[a,b]=\frac{ab}{(a,b)}$
(3) 若a|c，b|c，则[a,b]|c

定理1.13 设a₁，a₂，…，a_n是n个不为0的整数，定义m₁=[a₁, a₂]，m₂=[m₁, a₃]，…，m_n-1=[m_n-2, a_n]，则[a₁, a₂, …, a_n]=m_n-1

定理1.14 与定理1.10类似，不想抄了

定义1.5 素数

定理1.15 合数的最小的不等于1的正因子p一定是素数且小于根号m
推论 若所有小于根号m的素数都不是m的因子，则m为素数

定理1.16 素数有无穷多个

定理1.17 素数定理：$\lim_{x\rightarrow\infty}\pi(x)\frac{\ln(x)}{x}=1$

定理1.18 切比雪夫定理：设整数n>3，则至少存在一个素数p满足n<p<2n-2

定理1.19 算数基本定理：n为一个大于1的正整数，则n必然可以分解为一些素数的乘积，如果将素因子顺序排列，则n分解方式唯一。

定义1.6 标准分解式

定义1.7 高斯函数

定理1.20
(1) 若x≤y，则[x]≤[y]
(2) 整数a满足x-1<a≤x$\Leftrightarrow$a=[x]
(3) 整数a满足a≤x<a+1$\Leftrightarrow$a=[x]
(4) 任意整数n，[n+x]=n+[x]

定理1.21 整数a,b且b>0，带余除法算式a=qb+r，0≤r<b，则q=$[\frac{a}{b}]$

定理1.22 n!中包含的p次幂次数为$\sum_{i\ge 1}[\frac{n}{p^i}]$