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

信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 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，且是有限整数，故经过有限次带余除法后，总可以得到一个余数是零的情况，即　 　　由(1)知， 　　 定理2：任意两个正整数,则是(1)中最后一个不等零的余数． 定理3：任意两个正整数的任意公因数都是的因数．4．性质定理4：任意两个正整数，则存在整数，使得成立 定理5：设是不全为零的整数． 　　　(i)若则 　　　(ii)若则 　　　(iii)若是任意整数，则 从上面定理我们很容易得到下面几个常用结论： 　　① 　　② 且　　　 　　③ 　　④ 5．求两个以上正整数的最大公因数 　　设 则有下面的定理：定理6：若 是个正整数，则只需证①是的一个公因数．② 是的公因数中最大一个求 解： 　　 最小公倍数1．最小公倍数的定义 定义： 是 个整数，如果对于整数，有 ,那么叫做的一个公倍数．在 的一切公倍数中最小一个正整数，叫做最小公倍数．记作 ． 2．最小公倍数的性质． 定理：设是任给的两个正整数，则 　　　 (i)的所有公倍数都是的倍数． 　　　 (ii) 定理：设正整数是的一个公倍数，则3．求两个以上整数的最小公倍数定理：设是个正整数, 若　 则 只需证：①是 的一个公倍数，即 　　　　②设是的任一公倍数,则 求 解： 　 又 　　 　　 　　　　 1．素数、合数的概念 定义：一个大于1的整数，如果它的正因数只有1和它的本身，我们就称它为素数，否则就称为合数． 2．性质 定理1：设是大于1的整数，则至少有一个素因数，并且当是合数时，若是它大于1的最小正因数，则，都有 p n,则n一定是素数. 求素数的基本方法：爱拉托斯散筛法。 定理：设是素数，是任意整数，则 　　　　(i) 或 　　　(ii) 若 则或3．素数的个数 定理：素数的个数是无穷的．n1都可以表示成素数的乘积，且在不考虑乘积顺序的情况下，该表达式是唯一的.即 n= p1 … ps , p1≤ … ≤ps , (1) 其中pi 是素数，并且若n = q1 …qt , q1 ≤ … ≤ qt , 其中qj 是素数，则 s= t , pi = qj,