第一章整除与同余1.1整除整除的基本性质：整除的基本性质（证明）：整除的基本性质（证明）：整除的基本性质（证明）：整除的基本性质（补充）：带余除法：带余除法：最大公因子（定义）最大公因子（性质）最大公因子（求解）最大公因子（求解）欧几里德算法原理最大公因子（求解）最大公因子定理证明设Z是全体整数集合，构造如下一个集合：S={xa+ybx，yZ}．S中的元素显然大于等于0．设d是S中的最小正整数，设d=ua+vb．现在我们证明da且db．做带余除法：a=qd+r，0rd．于是r=a–qd=a–q(ua+vb)=(1–qu)a–qvb．这说明r也可表示为a，b的组合，则rS．由于d是S中的最小者，所以r=0．故da．同理db．设c是a，b的任意公因子，由ca和cb得cua+vb．故d是a，b的最大公因子，证毕．最大公因子定理互素互素（性质）互素性质证明互素性质证明互素性质证明公倍数，最小公倍数例8a=2，b=3．它们的公倍数集合为{0，6，12，18，…}．而[2，3]=6．最小公倍数与最大公约数关系定理2证明定理2证明d=qaka(a，b)=qbkb(a，b)，qaka=qbkb．因为(ka，kb)=1，则kaqb，kabqbb=d，这表明是公倍数中最小的，定理得证．最小公倍数与最大公约数关系1.2素数1.2素数定理2算术基本定理证明:标准因子分解式Eratosthenes筛法求不超过100的全部素数．第1步找出的全部素数：2，3，5，7．第2步在1～100中分别划去第1步找出的每个素数的全部倍数：分别划去2的全部倍数、3的全部倍数、5的全部倍数和7的全部倍数．（1）划去2的全部倍数：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100Eratosthenes筛法Eratosthenes筛法Eratosthenes筛法Eratosthenes筛法Eratosthenes筛法素数无穷个1.3同余1.3同余1.3同余同余性质及推论同余性质及推论3）ma2(a1b1)+b1(a2b2)=a1a2b1b2，故a1a2b1b2(modm)．4）由acbc(modm)，得macbc=c(ab)，因为(c，m)=1，则m(ab)，ab(modm)．5）由ab(modm)，得m(ab)，而dm，则dm(ab)，ab(modd)．证毕．同余性质及推论同余应用同余应用同余应用补充定理1.1（带余除法）补充定理1.1（带余除法）补充定理1.1（带余除法）