下载文档原格式
信息安全数学基础第一阶段知识总结第一章整数得可除性一整除得概念与欧几里得除法1 整除得概念定义1 设a、b就是两个整数，其中b≠0如果存在一个整数q 使得等式a=bｑ成立，就称b整除a或者ａ被ｂ整除，记作b|a ,并把b 叫作a得因数,把a叫作b得倍数、这时，q也就是a得因数,我们常常将ｑ写成a/b或否则,就称b不能整除a或者a不能被b整除,记作a b、2整除得基本性质(1)当b遍历整数a得所有因数时,－b也遍历整数a得所有因数、（2)当ｂ遍历整数a得所有因数时,a/b也遍历整数a得所有因数、（3)设b，c都就是非零整数，(i）若b|a,则|b|｜|ａ|、(ｉｉ)若ｂ｜a,则ｂｃ|aｃ、(iii)若b|a,则1〈|b｜≤|ａ|、3整除得相关定理（1)设a,ｂ≠0,c≠０就是三个整数、若c｜b,b|a,则ｃ|a、(２)设a，b，c≠０就是三个整数,若ｃ|ａ,ｃ|b,则ｃ｜a±b(3）设a，b,c就是三个整数、若c｜a，ｃ|b则对任意整数s，t,有c|ｓa+tb、(４）若整数a１, …,aｎ都就是整数c≠0得倍数，则对任意n个整数s１,…,ｓｎ，整数就是c得倍数（5）设a，b都就是非零整数、若a|b,ｂ|a,则a=±b(6)设a,ｂ，c就是三个整数,且b≠0,c ≠0,如果(a , c）=1,则(ab , ｃ)＝（ｂ，c）(7) 设ａ，b , c就是三个整数,且ｃ≠0，如果c｜ａb，（a , ｃ）＝1, 则c｜b、（8）设ｐ就是素数，若ｐ|ab ,则p |a或p|b（9）设a1，…,a n就是n个整数，p就是素数,若ｐ｜a1…a n，则p一定整除某一个ａk二整数得表示主要掌握二进制、十进制、十六进制等得相互转化、三最大公因数与最小公倍数（一)最大公因数1．最大公因数得概念定义:设就是个整数,若使得 ,则称为得一个因数。
公因数中最大得一个称为得最大公因数。
记作、若，则称互素。
若,则称两两互素。
第一章整数的可除性§1 整除整数集对于加、减、乘三种运算都是封闭的，但是对于除法运算不封闭。
为此，我们引进整除的概念。
定义1设a,b∈Z，b≠0，如果存在q∈Z，使得等式a=bq成立，那么称b 整除a或a被b整除，记作：b|a，此时称b为a的因数（约数），a为b的倍数。
如果不存在满足等式a=bq的整数q，那么称b不能整除a或a不被b整除，记作b| a。
定理1设a,b,c∈Z，b≠0，c≠0，则（1）如果c|b，b|a，那么c|a；（2）如果b|a，那么bc|ac；反之亦真；（3）如果c|a，c|b，那么，对于任意m,n∈Z，有c|(ma+nb)；（4）如果b|a，a≠0，那么|b|≤|a|；（5）如果b|a，a|b，那么|b|=|a|。
证明可选证。
定理2（带余除法）设a,b∈Z，b≠0，则存在q,r∈Z，使得a=bq+r，0≤r<|b|，并且q及r是唯一的。
证明当b|a时，取q=a/b，r=0即可。
当b!|a时，考虑集合E={a-bk|k∈Z }，易知E中有正整数，因此E中有最小正整数，设为r=a-bk>0，下证：r<|b|。
因为b!|a，所以r≠|b|，若r>|b|，则r’=r-|b|>0，又r’∈E，故与r的最小性矛盾，从而存在q,r∈Z，使得a=bq+r，0≤r<|b|。
唯一性。
设另有q’,r’∈Z，使得a=bq’+r’，0≤r’<|b|，则b(q-q’)=r’-r，于是b|(r’-r)，但由于0≤|r’-r|<|b|，故r’-r=0，即r=r’，从而q=q’。
定义2等式a=bq+r，0≤r<|b|中的整数q称为a被b除所得的（不完全）商，整数r称为a被b除所得的余数。
注r=0的情形即为a被b整除。
例1 设b=15，则当a=255时，a=17b+0，故q=17，r=0；当a=417时，a=27b+12，故q=27，r=12；当a=-81时，a=-6b+9，故q=-6，r=9。
第一章整数的可除性整除整除是数论中的基本概念，在这一部分中，我们从这个概念出发，引进带余数除法及辗转相除法，然后利用这两个工具，建立最大公因数与最小公倍数的理论，进一步证明极具重要性的算术基本定理。
最后介绍两个重要的函数[]与{},并用[]来说明如何把!表成质数幂的乘积。
整除的定义设，是任意两个整数，其中≠０，如果存在一个整数使得等式=(1)成立，我们就称为整除或被整除,记做|，此时我们把叫做的因数，把叫做的倍数，如果（1）里的整数不存在，就说不能整除或不被整除，记做。
例如＝6，＝3时，有q＝2使＝，故3|6；又如＝4，＝3时，不存在整数使＝bq，故34。
整除的性质定理1若是的倍数，是的倍数，则是的倍数。
即：|，||。
证：由|，|及整除的定义知存在整数使得。
因此，但是一个整数，故ｃ|。
定理2若，都是的倍数，则也是的倍数。
证，都是的倍数的意义就是存在两个整数，使得所以，但为整数，故是的倍数。
用类似方法可以证明下面的定理3，请同学们自己给出证明。
定理3若都是的倍数，是任意个整数，则是的倍数。
例证明3|(+1)(2+1)，其中是任何整数。
证因为(+1)(2+1)= (+1)[(+2)+(-1)]=(+1)(+2)+(-1)(+1)，而三个连续整数的积可被3整除，于是3|(+1)(+2)，3|(-1)(+1) 。
所以3|(+1)(2+1)。
第一章整数的可除性带余数除法任给两个整数，它们之间不一定有整除关系，一般有下面的带余数除法。
定理若，是两个整数，其中>0，则存在两个整数及，使得（2）成立，而且及是唯一的。
证作整数序列…，－3，－2，－，0，，2，3，…则必在上述序列的某两项之间，即存在一个整数使得成立。
令－＝，则为整数，且＝＋，而。
设是满足（2）的另两个整数，则，所以，于是，故。
由于都是小于的正整数或零，故。
如果，则，这是一个矛盾。
因此，从而。
整数的很多性质都可以从这一定理引导出来，我们这一章的最主要部分就是建立在这一定理的基础上的。
