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

信息安全数学基础第一阶段知识总结第一章 整数的可除性一 整除的概念和欧几里得除法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 的倍数(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，且 是有限整数，故经过有限次带余除法后，总可以得到一个...