信息安全数学基础第一阶段知识总结

信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 1 整除的概念 定义1 设a、b 是两个整数，其中b≠0 如果存在一个整数 q 使得等式 a=bq 成立，就称b 整除a 或者a 被b 整除，记作b|a ，并把b 叫作a 的因数，把a 叫作b 的倍数.这时，q 也是a 的因数，我们常常将q 写成a／b 或 否则，就称b 不能整除a 或者a 不能被b 整除，记作a b. 2 整除的基本性质 (1)当b 遍历整数a 的所有因数时，-b 也遍历整数a 的所有因数. (2)当b 遍历整数a 的所有因数时，a/b 也遍历整数a 的所有因数. (3)设b，c 都是非零整数， (i)若b|a，则|b|||a|. (ii)若b|a，则bc|ac. (iii)若b|a，则1<|b|≢|a|. 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 , … ,an 都是整数c≠0 的倍数，则对任意 n 个整数s1，…，sn，整数 是c 的倍数 abnnasas11(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) 设a , b , c 是三个整数，且 c≠0，如果 c｜ab , (a , c) = 1, 则c | b. (8) 设p 是素数，若p |ab , 则p |a 或 p|b (9) 设a1 , … ,an 是n 个整数，p 是素数，若p| a1 … an ,则p 一定整除某一个 ak 二 整数的表示 主要掌握二进制、十进制、十六进制等的相互转化. 三 最大公因数和最小公倍数 (一)最大公因数 1．最大公因数的概念 定义：设是个整数，若使得 ，则称为的一个因数．公因数中最大的一个称为的最大公因数．记作. 若 ,则称 互素． 若,则称两两互素． 思考：1．由两两互素，能否导出 2．由 能否导出两两互素？ 2．最大公因数的存在性 (1)若 不 全 为 零，则最 大 公 因 数存 在 并 且 (2)若全为零，则任何整数都是它的公因数．这时，它们没有最大公因数． 3．求两个正整数的最大公因数． 定理1：设任意三个不全为零的整数，且 则 辗转相除法 由带余除法 得 (1) …… 因为每进行一次带余除法，余数至少减少 1，且是有限整数，故经过有限次带余除法后，总可以得到一个余数是零的情况，即 由(1)知， 定理2...