信息安全数学基础第一阶段知识总结
第一章 整数的可除性
一 整除的概念和欧几里得除法 1 整除的概念
定 1 a、b 是两个整数，其中 b≠0 如果存在一个整数 q 使得等式 a=bq 成立，就称 b 整除 a 或者 a 被 b 整除， 作 b|a ，并把 b 叫作 a 的因数，把 a 叫作 b 的倍数 . ， q 也是 a 的因数，我 常常将 q 写成 a／b 或
ba
否 ，就称 b 不能整除 a 或者 a 不能被 b 整除， 作 a 2 整除的基本性
(1) 当 b 遍 整数 a 的所有因数 ， -b 也遍 整数 a 的所有因数 . (2) 当 b 遍 整数 a 的所有因数 ， a/b 也遍 整数 a 的所有因数 . (3) b，c 都是非零整数， (i) (ii) (iii)
若 b|a ， |b|||a|. 若 b|a ， bc|ac. 若 b|a ， 1<|b| ≤|a|.
b.
3 整除的相关定理
(1) a，b≠0，c≠0 是三个整数 . 若 c|b ，b|a ， c|a. (2) a，b，c≠0 是三个整数，若 c|a ，c|b ， c|a ±b
(3) a，b，c 是三个整数 . 若 c|a ，c|b 任意整数 s，t，有 c|sa+tb. (4) 若整数 a1 , ?,a n 都是整数 c≠0 的倍数， 任意 n 个整数 s1，?，
s，整数
n
s1a1
sn an
是c的倍数
(5) a，b 都是非零整数 . 若 a|b ，b|a ， a=±b (6)
a, b , c
是三个整数，且
b≠0，c ≠ 0，如果 (a , c)=1,
(ab , c)=(b , c) (7) c | b. (8) p (9) a
a , b , c 是三个整数，且 c≠0，如果 c｜ab , (a , c) = 1,
是素数，若 p |ab , , ?,a
1
n
p |a 或 p|b
是 n 个整数， p 是素数，若 p| a
1n
?a ,p 一
定整除某一个 ak 二 整数的表示
主要掌握二 制、十 制、十六 制等的相互 化
.
三 最大公因数和最小公倍数
( 一) 最大公因数
1．最大公因数的概念 定 ：
是
个整数，若 .
, 称
, 称
两两互素，能否 出
能否 出
零，
两两互素
使得 ，
的最
称
大公因数． 作
的一个因数．公因数中最大的一个称
若
互素．
两两互素．
若
思考： 1．由
2．由
2．最大公因数的存在性 (1) 若
不全
最大公因数 存在并且
(2) 若 全 零， 任何整数都是它的公因数． ，它 没有
最大公因数．
3．求两个正整数的最大公因数 定理 1 ：
．
任意三个不全 零的整数，且
相除法
由 余除法 得
(1)
??
因 每 行一次 余除法，余数至少减少 1，且 是有限整数，故 有限次 余除法后， 可以得到一个余数是零的情况，即
由(1) 知，
定理 2：任意两个正整数 的余数．
,
是(1) 中最后一个不等于零
定理 3：任意两个正整数
的任意公因数都是
的因数．
4．性
定理 4：任意两个正整数 立
， 存在整数 ，使得 成
定理 5：
是不全 零的整数．
(i) 若
(ii) 若
(iii) 若 是任意整数，
从上面定理我 很容易得到下面几个常用 ：
, 那么
①
②
且
③
④
5．求两个以上正整数的最大公因数
设
则有下面的定理：
定理 6：若
是 个正整数，则
只需证① 是 的一个公因数．②
是
的公因数中最大一个 例 求
解：
6．求两个正整数的最大公因数的线性组合（重点掌握） 方法一 运用辗转相除法求最大公因数的逆过程； 方法二 补充的方法
方法三 运用列表法求解 ( 二) 最小公倍数
1．最小公倍数的定义 定义：
是
个整数，如果对于整数
，有
叫做
的一个公倍数．在 的一切
公倍数中最小一个正整数，叫做最小公倍 数．记作
．
2．最小公倍数的性质 ．
定理 1：设
(i) (ii)
是任给的两个正整数，则的所有公倍数都是
的倍数．
定理 2：设正整数
是 的一个公倍数，则
3．求两个以上整数的最小公倍数 定理 3：设
是 个正整数 , 若
则
只需证：①
是
的一个公倍数，即
,
②设 是
则 的任一公倍数 ,
例 1 求
解：
又
四 素数 算术基本定理
1．素数、合数的概念
定义：一个大于 1 的整数，如果它的正因数只有 1 和它的本身，我们就称它为素数，否则就称为合数． 2．性质
定理 1：设 是大于 1 的整数，则 至少有一个素因数，并且当
是合
数时，若 是它大于 1 的最小正因数，则
定理 2 设 n 是一个正整数，如果对所有地素数
pn，都有
信息安全数学基础第一阶段学习知识总结.docx
