北师大版高中数学选修4-6初等数论初步全套课件

北师大版高中数学选修4-6初等数论初步全套PPT课件整除新知学习通过整数的定义我们可知，两个整数的和、差与积仍然是整数。但是，任意整除相除却不一定是整数，我们可以举例说明：8＋6=14；8－6=2；8×6=48.8÷6=1.333333…2是整数，通常说6可以整除12；12÷6=2.1.333333…不是整数，通常说6可以整除8.新知学习一般地，我们给出如下关于整除的定义：定义设a，b是任意两个整数，其中b≠0，如果存在整数q使得等式a=bq成立，那么就说b整除a（或a被b整除），记作b丨a.此时我们把b叫做a的因数（或约数），把a叫做b的倍数。若上式中的整数q不存在，则称b不整除a（或a不能被b整除），记作b丨a.新知学习我们可以举例说明：6丨12,8丨12.根据整数的定义，我们可以得出以下结论：如果a，b，c都是非零的整数，就有：1、若a丨b，b丨c，则a丨c；2、若a丨c，则ab丨cb；3、若a丨b且a丨c，则对于任意整数m，n都有a丨（mb+nc）；新知学习4、若a丨b，则丨a丨≤丨b丨.我们可以对以上结论进行证明。（1）证明因为a丨b，则b=qa，又因为b丨c，所以存在整数p，使得：c=pb综上所述可知：c=pb=（pq）a所以，a丨c.新知学习（2）证明因为a丨c，则c=qa，故而可得cb=qab=（q）ab所以，ab丨cb.（3）证明因为a丨b，则b=qa，又因为a丨c，所以存在整数p，使得：c=pa新知学习故而可得：mb+mc=mqa+npa=（mq+np）a.mb=mqa.nc=npa.综上所述：所以，a丨（mb+nc）.新知学习（4）证明因为a丨b，则b=qa，根据绝对值的性质可知：丨b丨=丨qa丨.故可得：丨b丨=丨q丨丨a丨.因为q是正整数，综上所述可知：丨a丨≤丨b丨.新知练习1、用整除或者不整除的符号填空。（1）7____14,8____14；（3）9____18,9____26；（2）5____10,5____12；丨丨丨丨丨丨（4）6____24,6____35；丨丨（5）a____3a,b____3b；（6）m____4m,6m____m；丨丨丨丨新知练习2、对于任何的整数a，求证：2丨(a+1)(a+2)。证明因为除数为2，则可以分两种情况讨论：当a=2n+1（n∈Z）时，(a+1)(a+2)=(2n+1+1)(2n+1+2)=(2n+2)(2n+3)=2(n+1)(2n+3),新知练习所以2丨(a+1)(a+2)。当a=2n（n∈Z）时，(a+1)(a+2)=(2n+1)(2n+2)=2(2n+1)(n+1)，所以2丨(a+1)(a+2)。综上所述，对于任意的整数a都有：所以2丨(a+1)(a+2)。新知练习3、判断下列说法是否正确。（1）如果a丨b，a丨c，则b丨c（）。（2）如果a丨b，a丨c，则b丨c或c丨b（）。（3）如果a丨b，c丨b，则a丨c或c丨a（）。（4）如果a丨b，则一定存在整数c，使得b丨c，

（）。××××新知练习解析：（1）2丨4,2丨6，但是4丨6，故错误。（2）2丨4,2丨6，但是4丨6，且6丨4，故错误。（3）2丨6,3丨6，但是2丨3，且3丨2，故错误。（4）2丨0,不存在整数c，使得0丨c，故错误。课后练习1、关于下列说法正确的是（A）。A、如果a丨b，b丨c，则a丨c。B、如果n丨m，对于任意整数k都有kn丨km。C、如果a丨b，其中a可能为零。D、如果a丨b，则a＜b。谢谢！带余除法新知学习我们学习过整除的除法法则，比如：用4除40，得到的商是10，余数为0，可以写成：40=4×10+0；用6除40，得到的商是6，余数为4，可以写成：40=6×6+4；这就是我们通常所说的带余除法，它是初等数论的证明中最重要、最基本、最常用的工具。一般情况下表述为：新知学习设a，b是两个给定的整数，其中b＞0，那么，一定存在唯一的一对整数q及r，满足：a=bq+r，0≤r＜b.可以证明：b丨a的充要条件是r=0.我们称r是b除a所得的余数。证明（1）存在性列出b的所有倍数序列：…，-2b，-b，0，b，2b，…新知学习根据定义可知，a一定在序列中的任意相邻两项之间，则存在一个整数p，使得：pb≤a＜（p+1）b.成立。令r=a-pb，则a=pb+r，得出0≤r＜b.（2）唯一性假设还有整数p1与r1满足：a=bq1+r，0≤r1＜b.假设r1≥r，则0≤r1-r＜b，且有：新知学习r1-r=（p-p1）b.我们根据整数的定义可以推出：b丨（r1-r）.若r1-r≠0，则b≤（r1-r）.这与结论：0≤r1-r＜b.矛盾。所以必有r1=r，进而p1=p.新知学习根据上述所证定理，我们可将所有的整数按除数b与余数r进行分类。如：当除数为3的时，任何整数被3除，余数为0，或者为1，或者为2.这样我们可以将整数分为3类：一类余数为0，一类余数为1，一类余数为2，分别表示为：3k，3k+1，3k+2.类似的我们可以推出除数为4,5,6…的表示方式。当除数为4的时，任何整数被4除，余数为0，或者为1，或者为2，或者为3.这样我们可以将整数分为4类：一类余数为0，一类余数为1，一类余数为2，一类余数为3，分别表示为：4k，4k+1，4k+2，4k+3.新知学习新知学习例一对于任意整数k，求证：3丨k(k+1)(2k+1).证明当除数为3时，所有整数可分为3类：3n，3n+1，3n+2.所以我们可以分三种情况来讨论：（1）k=3n（n∈Z）时，3丨k，所以3丨k(k+1)(2k+1).（2）k=3n+1（n∈Z）时，2k+1=2（3n+1）+1=6n+3=3（2n+1），因为3丨2k+1，所以3丨k(k+1)(2k+1).新知学习（3）k=3n+2（n∈Z）时，k+1=3n+3=3（n+1），因为3丨k+1，所以3丨k(k+1)(2k+1).综上所述，对于任意的整数k，都有：3丨k(k+1)(2k+1).新知练习1、除数为8时，请将所有整数按8及其余数分类。分析：除数为8时，任何整数被8除，余数或者为0，或者为1，或者为2，或者为3，或者为4，或者为5，或者为6，或者为7.所以我们可以按8及余数进行分类：一类余数为0，一类余数为1，一类余数为2，…，一类余数为7.答案：8n，8n+1，8n+2，8n+3，8n+4，8n+5，

8n+6，8n+7.新知练习2、对于任意的整数m，求证：6丨m（m²-1）.证明当除数为6时，所有整数可分为6类：6n，6n+1，6n+2，6n+3，6n+4，6n+5.所以我们可以分六种情况来讨论：（1）m=6n（n∈Z）时，6丨m，所以6丨m（m²-1）.将整式变形可得：m（m²-1）=m(m+1)(m-1).新知练习（3）m=6n+2（n∈Z）时，m（m²-1）=(6n+2)(m²-1)

=(6n+2)(36n²+24n+3)

=6(3n+1)(12n²+8n+1)所以6丨m（m²-1）.（2）m=6n+1（n∈Z）时，m-1=6n+1-1=6n，

所以6丨(m-1),所以6丨m（m²-1）.新知练习（5）m=6n+4（n∈Z）时，m（m²-1）=(6n+4)(m²-1)

=(6n+4)(36n²+48n+15)

=6(3n+2)(12n²+16n+5)所以6丨m（m²-1）.（4）m=6n+3（n∈Z）时，m（m²-1）=(6n+3)(m²-1)

=(6n+3)(36n²+36n+8)

=6(2n+1)(18n²+18n+4)所以6丨m（m²-1）.新知练习综上所述可知，对于任意的整数m，都有：6丨m（m²-1）.（6）m=6n+5（n∈Z）时，m（m²-1）=(6n+5)(m²-1)

=(6n+5)(36n²+60n+24)

=6(6n+5)(6n²+10n+4)所以6丨m（m²-1）.谢谢！二进制新知学习在过去的计数和运算中，我们常常用到进制法。比如说：普通的加减乘除采用的十进制，10称为基数。时间的计数方法：1时=60分，1分=60秒，这是六十进制，基数为60.月的计数方法：1月=30天，这是三十进制，基数为30.年的计数方法：1年=365天，这是三百六十五进制，基数为365.新知学习在现代中，计算机使用二进制来处理各种信息。我们通过经验可知：任何数都可以用0,1,2，…，9这十个数字表示，同一数字再不同的位置上所代表的意义不同，如7777：从个位开始数，第一个7代表7×10，即7；0十位上的7代表7×10，即70；1百位上的7代表7×10，即700；2千位上的7代表7×10，即7000.3新知学习7777=7×10＋7×10＋7×10＋7×10.3210在二进制中，只用两个数字0和1来表示所有的整数，它究竟是如何表示呢？为了区分十进制和二进制，我们通常把二进制表示的数a写成（a），其中a的各个数码都是0和1.2我们知道二进制的方法是“逢二进一”，可以推断出（1111）中，每个“1”的数学意义：2个位上的1代表1×2，即1；0新知学习十位上的1代表1×2，即2；1百位上的1代表1×2，即4；2千位上的1代表1×2，即8.3（1111）=1×2＋1×2＋1×2＋1×2

=15.32102所以就有：这样我们就把二进制表示的数（1111）转化为了十进制的数15.2新知学习其实对于任何一个二进制表示的数（aa

…a）其中a=0或1,0≤j≤n），则二进制的数都可以表示为十进制的数：nn-102，ja.2+a.2+…+a.2+a

.nnn-1n-110利用上述公式，我们可以将所有二进制表示的数转化为十进制表示的数。新知学习例一、把下列二进制表示的数转化为十进制表示的数。（1）（1011）（2）（1101）（3）（1000）（4）（1110）2222分析：我们可以利用公式将二进制表示的数转化

为十进制表示的数：a.2+a.2+…+a.2+a

.nnn-1n-110（aa

…a）nn-102=新知学习

（2）（1101）=1×2＋1×2＋0×2＋1×2=8+4+0+1=133210（1）（1011）=1×2＋0×2＋1×2＋1×2=8+0+2+1=113210解：新知学习

（4）（1110）=1×2＋1×2＋1×2＋0×2=8+4+2+0=143210

（3）（1000）=1×2＋0×2＋0×2＋0×2=8+0+0+0=83210新知学习我们如何将十进制表示的数转化为二进制表示的数呢？以13为例，我们将13表示成二进制的形式：（aa

…a）nn-102则有：a.2+a.2+…+a.2+a

.nnn-1n-110=13a.2+a.2+…+a）+a

.nn-1n-1n-210=2（分析可知，a就等于13除以2所得的余数1.0新知学习则表示13除以2所

得的商6.则有：a.2+a.2+…+a=6nn-1n-1n-11a.2+a.2+…+a）+a

nn-2n-1n-3212（=6则表示6除以2所得

的商3.则有：分析可知，a就等于6除以2所得的余数0.1a.2+a.2+…+ann-2n-1n-32a.2+a.2+…+ann-1n-1n-11新知学习a.2+a.2+…+a=3nn-2n-1n-32a.2+a.2+…+a）+a

nn-3n-1n-4322（=3则表示3除以2所

得的商1.则有a=1.a.2+a.2+…+ann-3n-1n-43分析可知，a就等于3除以2所得的余数1.23（aaaa）32021=（1101）2则13的二进制表示：新知学习为了形象的表示上述过程，我们可以表示如图：1362232210………………………………余数1=a00=a11=a21=a3低位高位新知练习将十进制数25转化为二进制数。解：25122262231………………………………余数1=a00=a10=a21=a3低位高位20………1=a4（aaaaa）43122=（11001）2则25的二进制表示：0谢谢！素数的判别新知学习什么是素数？定义一个大于1的正整数，如果它的正因数只有1和它本身，就叫做素数。如何判断一个正整数是不是素数？为了确定251是不是素数，应该考察从1到246的所有正整数能否整除251.但是如此一来过程非常麻烦，我们能否找到简便方法呢？新知学习我们可以这样思考：如果m是a的因数，那么也一定是a的因数，m与不可能都大于.因此，为了确定a是否为素数，我们只要考察不大于的正整数能否整除a.从而我们得出结论：amam只需考察所有不大于的素数即可。新知学习例1判断251是否为素数。解：因为＜16，我们只需要考察所有小于16的所有素数：2,3,5,7,11,13能否整除251即可。通过验算之后发现上述素数都不能整除251，故251是素数。新知学习例2求出不超过200的所有素数。解：因为＜15，我们只需要找出所有小于15的所有素数：2,3,5,7,11,13的倍数即可，除去1以及所有的正合数即可。通过计算可知，没有被删去的数共46个，它们是：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199.新知学习这样我们就得到了不超过200的所有的素数。按照这样的做法，对于给定的任意整数N，可以找出不超过N的全部素数。这种寻找素数的方法，是希腊时期埃拉托塞尼（约公元前274-194）发明的，它好像用筛子筛出素数一样，所以通常叫作埃拉托塞尼筛法。新知学习练习1判断下列各数是否为素数。新知练习（1）249（2）397（3）1361（4）2159解：（1）因为＜16，我们只需要考察所有小于15的所有素数：2,3,5,7,11,13能否整除249即可。通过计算可知，它们都不能整除249，所以249是素数。新知练习（2）因为＜20，我们只需要考察所有小于20的所有素数：2,3,5,7,11,13,17,19能否整除397即可。通过计算可知，它们都不能整除397，所以397是素数。新知练习（3）因为＜37，我们只需要考察所有小于37的所有素数：2,3,5,7,11,13,17,19,23,29,31能否整除1361即可。通过计算可知，它们都不能整除1361，所以1361是素数。新知练习（4）因为＜47，我们只需要考察所有小于47的所有素数：2,3,5,7,11,13,17,19,23,29,31，37,41,43能否整除2159即可。通过计算可知，2159÷17=127，所以2459不是素数。新知练习练习2下列哪个数是素数（）

A.247B.127C.522D.687B分析：A.因为＜16，我们只需要考察所有小于16的所有素数：2,3,5,7,11,13能否整除127即可。通过计算可知，247÷13=19，所以247不是素数。新知练习C.因为＜23，我们只需要考察所有小于23的所有素数：2,3,5,7,11,13,17,19能否整除522即可。通过计算可知，522÷3=174，所以522不是素数。B.因为＜12，我们只需要考察所有小于12的所有素数：2,3,5,7,11能否整除127即可。通过计算可知，它们都不能整除127，所以127是素数。D.因为＜27，我们只需要考察所有小于27的所有素数：2,3,5,7,11,13,17,19,23能否整除687即可。通过计算可知，687÷3=229，所以687不是素数。新知练习谢谢！素数的个数新知学习根据素数的定义可知：所有大于2的偶数都是合数，各位数之和为3的倍数的数是合数，除了5之外，个位数字是5的整数也是合数……由此可见，合数的个数是无限个的，那么素数有多少个？是有限的么？这是一个非常有趣的问题，早在公元前约300年时，欧几里得第一次证明了素数的个数是无穷的。新知学习例1证明素数有无穷多个。证明用反证法.假设只有有限多个素数，不妨设它们是P1，P2，P3，…Pn，考虑整数：a=P1P2P3…Pn+1.显然，a是不同于Pi（i=1,2,3，…，n）的整数，所以a为合数，故必存在素数b丨a.新知学习根据假设可知：b必等于Pi（i=1,2,3，…，n）中的某一个，不妨设b=Pn妨设，则有：因此，假设不正确，即素数有无穷多个。Pn丨（P1P2P3…Pn+1），这明显是不可能的。新知练习练习1求不超过120素数的个数。分析：＜11，我们只需要找出所有小于11的所有素数：2,3,5,7的倍数即可，除去1以及所有的正合数即可。解：2的倍数有：120÷2=60（个）；3的倍数有：120÷3=40（个）；5的倍数有：120÷5=24（个）；7的倍数有：120÷7=17……1，则有17个；新知练习2、3的公倍数有：120÷2÷3=20（个）；2、5的公倍数有：120÷2÷5=12（个）；2、7的公倍数有：120÷2÷7=8……6,则有6个；3、5的公倍数有：120÷3÷5=8（个）；3、7的公倍数有：新知练习120÷3÷7=5……15，则有5个；5、7的公倍数有：120÷5÷7=3……15，则有3个；2、3、5的公倍数有：120÷2÷3÷5=4（个）；2、3、7的公倍数有：120÷2÷3÷7=2……36，则有2个；新知练习2、5、7的公倍数有：3、5、7的公倍数有：120÷3÷5÷7=1……15，则有1个；120÷2÷5÷7=1……50，则有1个；则有：=120－（60+40+24+17）＋（20+12+8+8+5+3）

－（4+2+1+1）=27（个）新知练习27并非就是不超过120的素数个数，因为这里排除了2,3,5,7这四个数，又包含了“1”这个非素数。2,3,5,7这四个数本身就是素数。故所求的不超过120的素数个数为：27+4-1=30故不超过120的素数个数为30个。新知练习练习1利用埃拉托塞尼筛法，写出101～200内所有的素数。解：因为＜15，我们只需要找出所有小于15的所有素数：2,3,5,7,11,13的倍数即可，除去不大于100的数以及所有的正合数即可。通过计算可知，没有被删去的数共21个，它们是：101,103,107,109,113,127,131,137,139,149,151,157,163，167,173,179,181,191，193,197,199.新知练习新知练习练习2判别下列各数是否为素数。（1）237（2）469（3）1381（4）1193解：（1）因为＜16，我们只需要考察所有小于16的所有素数：2,3,5,7,11,13能否整除237即可。237÷3=79，所以237不是素数。新知练习（2）因为＜22，我们只需要考察所有小于22的所有素数：2,3,5,7,11,13,17,19能否整除469即可。通过计算可知：469÷7=79，所以469不是素数。新知练习通过计算可知，它们都不能整除1381，所以1381是素数。（3）因为＜38，我们只需要考察所有小于38的所有素数：2,3,5,7,11,13,17,19,23,29,31,37，能否整除1381即可。新知练习通过计算可知，它们都不能整除1193，所以1193是素数。（3）因为＜35，我们只需要考察所有小于38的所有素数：2,3,5,7,11,13,17,19,23,29,31,能否整除1193即可。谢谢！最大公因数与辗转相除法新知学习什么是最大公因数？我们可以举例说明，例如24和18，这两个整数的公因数有1,2,3,6.其中，6是这些书中最大的，称之为18和24的最大公因数。最大公因数如何定义呢？设a，b是两个不全为零的整数，若整数d是它们所有公因数中最大的一个，则称d为它们的最大公因数，记作d＝（a，b）.新知学习在特殊情况下，当（m，n）=1时，m，n互素。素数的一个数的性质，互素是指两个数之间的数学关系，并不代表两个数都是素数。例如（20,21）=1,20与21互素，但是20和21本身都是合数。对于特殊的整数0，我们知道：任何整数（不为零）都是0的因数。因此对于任何整数m＞0，则（0，m）=m新知学习根据上述定义可知，求两个正整数的最大公数，可以先求出它们所有的公因数，然后确定最大的公因数。然而当两个数非常庞大的时候，我们该如何求解呢？我们可以证明以下定理：定理1对于三个不全为零的正整数a，b，c来说，若a=bq+c，其中q是非零正整数，则a，b与b，c有相同的公因数，且（a，b）=（b，c）.新知学习证明设d是a，b的任一公因数，由定义知，d丨a，d丨b.根据整除的性质可知：d丨（a-bq）；即d丨c，因为d也是b，c的一个公因数。同理可证，b，c的任一公因数也是a，b的公因数。所以a，b与b，c有相同的公因数,故（a，b）=（b，c）成立。新知学习根据这个定理，利用带余除法a=bq+r（0≤r＜b），我们可以将最大公因数问题转化为b与r的最大公因数问题。下面我们结合例题进行分析。新知学习例1求（1564，1123）.解：因为1564=1123×1+441，则有：（1564,1123）=（1123,441）.继续运用定理可知：1123=441×2+241.故：（1123,441）=（441,241）.441=241×1+200.故：新知学习（441,241）=（241,200）.241=200×1+41.故：（241,200）=（200,41）.200=41×4+36.故：（200,41）=（41,36）.41=36×1+5.故：（41,36）=（36,5）.新知学习36=5×7+1.故：（36,5）=（5,1）=1.综上所述可得：（1564，1132）=1.以上方法我们称为辗转相除法，用这种方法可以巧妙地求出两个数的最大公因数。新知学习定理2对于任意不全为零的两个正整数a，b，必存在整数s，t，使得（a，b）=sa+tb.例2已知（37,68）=1，利用辗转相除法求出整数s，t，使得37s+68t=1.解：我们可以运用辗转相除法写出下列式子：68=1×37+3137=31×1+6新知学习31=5×6+16=1+5所以1=31－5×6＝31－5×（37－31）＝6×31－5×37＝6×（68－37）－5×37＝6×68－11×37由此求得：s=-11，t=6.新知练习练习1求（1287，1965）.解：因为1965=1287×1+678，则有：（1965,1287）=（1287,678）.继续运用定理可知：1287=678×1+609.故：（1287,678）=（678,609）.678=609×1+69.故：（678,609）=（609,69）.609=69×8+57.故：（609,69）=（69,57）.69=57×1+12.故：（69,57）=（57,12）.57=12×4+9.故：（57,12）=（12,9）.新知练习新知练习12=9×1+3.故：（12,9）=（9,3）=3.综上所述可得：（1297，1965）=3.谢谢！算术基本定理新知学习我们知道任意一个合数m必有素因数，记为p1，因此，存在整数q1，使得m=p1q1，其中q1＜m.若q1是素数，则m就表示为两个素数的乘积；若q1是合数，则可以继续把q1表示为p2q2的形式，其中p2为素数.依次下去……由于m＞p1＞p2＞…＞0，因为这个过程一定会停止，于是我们可以得到以下算术基本定理：定理1任一大于1的整数m能表示成素数的乘积：m=p1p2…ps，新知学习其中pi（1≤i≤s）是素数。且在不及次序的议一下，表示式是唯一的。例如125=5×25=5×5×5.我们如何证明定理一的唯一性呢？证明由于pi不计次序，我么可以设：m=p1p2…ps，p1≤p2≤…≤ps.若还有素数q1，q2,…,qt，使得m=q1q2…qt，q1≤q2≤…≤qt.则：新知学习p1p2…p3=q1q2…qt下面我们首先来证明p1=q1.显然，p1丨q1q2…qt，必存在qi，使得p1=qi.又因为q1≤qi，所以q1≤p1.同理可证：p1≤q1，所以p1=q1.由此可知p2p3…ps=q2q3…qt.同法可得p2=q2，继续推断可得t=s，且pi=qi，i=1,2，…，s.新知学习继而我们可以推出以下结论：任一大于1的正整数m=p1p2…ps，a1asa2其中mi（i=1,2，…，s）为正整数，p1，p2，…，ps为素数，且满足p1＜p2＜…ps.我们把上式称为m的标准素因数分解式。新知学习例1把下列合数分解素因数，并写出其标准素因数分解式。（1）160（2）275（3）360（4）500解：（1）160=2×2×2×2×2×5=2×5.（2）275=5×5×11=5×11.52（3）360=2×2×2×3×3×5=2×3×5.32（4）500=2×2×5×5×5=3×5.32新知学习例2试求所有小于500，且与500互素的正整数的个数。分析因为500=2×2×5×5×5=2×5，所以，与500互素的数，也就是与2,5均互素的数。32所以，我们只要求出500以内2的倍数、5的倍数以及10的倍数即可。解：不大于500的正整数中，2的倍数共有500÷2=250个，5的倍数共有500÷5=100个，10的倍数有500÷10=50个，所以与500互素的数的个数为：新知学习500-（250+100）+50=200个。一般地，我们用ψ（m）来表示所有小于正整数m，且与m互素的正整数的个数。例如ψ（500）=200.这是一个定义在正整数集合上的函数，通常称为欧拉函数。新知练习练习1写出下列各数的标准素因数分解式。（1）350（2）420（3）650（4）780解：（1）350=2×5×5×7=2×5×7.2（2）420=2×2×3×5×7=2×3×5×7.2（3）650=2×5×5×13=2×5×13.2（4）780=2×2×3×5×13=2×3×5×13.2新知练习练习2求出5000内，且与5000互素的数。解：5000=2×5，所以与5000互素的数同时也与2,5互素。342的倍数有：5000÷2=2500个；5的倍数有：5000÷5=1000个；新知练习10的倍数有：5000÷10=500个；在5000以内且与5000互素的数有：5000-（2500+1000）+500=2000个.新知练习练习3计算。（1）ψ（144）

（2）ψ（108）

（3）ψ（441）

（4）ψ（1225）

解：（1）144=2×3，所以与144互素的数同时也与2,3互素。422的倍数有：144÷2=72个；3的倍数有：144÷3=48个；6的倍数有：144÷6=24个；在144以内且与144互素的数有：144-（72+48）+24=48个.新知练习（2）108=2×3，所以与144互素的数同时也与2,3互素。232的倍数有：108÷2=54个；3的倍数有：108÷3=36个；新知练习6的倍数有：108÷6=18个；在144以内且与144互素的数有：108-（54+36）+18=36个。（3）441=3×7，所以与441互素的数同时也与3,7互素。223的倍数有：441÷3=147个；新知练习7的倍数有：441÷7=63个；21的倍数有：441÷21=21个；在441以内且与441互素的数有：441-（147+63）+21=252个。新知练习（4）1225=5×7，所以与441互素的数同时也与5,7互素。225的倍数有：1225÷5=245个；7的倍数有：1225÷7=175个；35的倍数有：1225÷35=35个；在1225以内且与1225互素的数有：1225-（245+175）+35=840个。新知练习谢谢！最小公倍数与算术基本定理的应用新知学习对于给定的整数18和24，我们可以求出它们的公共倍数有72,144,216，…其中，72是这些数中的整数，称之为18和24的最小公倍数。定义设a，b是两个整数，若整数d是它们所有公倍数中最小的一个正数，则称d为它们的最小公倍数，记作d=[a，b].根据最小公倍数的定义可知：[4,5]=20；新知学习[8,9]=72；[12,16]=48；[15,25]=75；根据上式可知：1、当两个数互素（即最大公约数为1）时，最小公倍数就等于这两个数的乘积。2、当两个数最大公因数不等于1时，最小公倍数就不等于这两个数的乘积。新知学习两个数的最小公倍数和最大公约数之间有怎样的关系？我们可以将160和300进行探究。160=2×2×2×2×2×5=2×3×5.50300=2×2×3×5×5=2×3×5.21而（160,300）=2×3×5=20；201215[160,300]=2×3×5=2400.12新知学习对于公因数2，在160和300中分别出现了2，2，其中次数较高的2出现在最小公倍数2400中，次数较低的2出现在最大公因数20中。同样地，3，5出现在最小公倍数中，3，5出现在最大公因数中。25521201这样我们就可以得出：（160,300）×[160,300]=20×2400=160×300.新知学习由上述计算可知：对于任意两个整数a，b，设p1，p2，…，ps是a和b的所有素因子，记a=p1p2

…ps素因子，b=p1p2

…ps素因子，其中pi为素数，整数…、≥0（i=1,2，…，s），则：α1αiβ1α2αsβ2βsβi（a，b）=p1p2

…ps，其中ui=min（，），

i=1,2，…，s；u1u2usαiβi新知学习[a，b]=p1p2

…ps，其中vi=max（，），

i=1,2，…，s.u1u2usαiβi这里，min（αi，βi）表示αi，βi中最小的数，max（αi，βi）表示αi，βi中最大的数。

定理1设a，b是两个正整数，则：由此可得：（a，b）=[a，b]=ab.新知学习例1求57和69的最大公因数和最小公倍数。解：（57,69）=（57，12）=（12,9）=（9,3）=3.所以，[57,69]=57×69÷3=3933÷3=1311.新知学习例2求365和815的最大公因数和最小公倍数。解：（365,815）=（365，85）=（85,25）=（25,5）=5.所以，[365,815]=365×815÷5=297475÷5=59495.新知练习练习1求下列各组数的最大公因数和最小公倍数。（1）384与447（2）252与556（3）1257与1569（4）1260与3100新知练习[384,447]=384×447÷3=171648÷3=57216.解：（1）（384,447）=（384，63）=（63,6）=（6,3）=3.新知练习[252,556]=252×556÷4=140112÷4=35028.（2）（252,556）=（252，52）=（52,44）=（44,8）=(8,4)=4.新知练习[1257,1569]=1257×1569÷3=1972233÷3=657411.（3）（1257,1569）=（1257，312）=（312,9）=（9,6）=(6,3)=3.新知练习[1260,3100]=1260×3100÷20=3906000÷20=195300.（4）（1260,3100）=（1260，580）=（580,100）=（100,80）=(80,20)=20.谢谢！不定方程鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁母雏各几何？”解：设x,y,z分别表示鸡翁、鸡母、鸡雏的只数，则可列出方程如下：消去z得到方程：这里，方程的个数少于未知数的个数，在实数范围内，方程的解有无穷多个。而我们所关心的是其有无整数〔或正整数〕解，这种方程〔组〕称为不定方程。思考探究分析：这类问题实质上是“不定方程求正整数解”的问题，因为铺好的地板中间不能出空隙，所以两种图形内角拼在一起恰好要构成360度角，并且砖的块数又是正整数。于是就使几何拼图转化成不定方程求正整数解的问题。A、①②、B、①③、C、②③、D、②④60m+90n=360.思考探究小明家现有边长相等的正三角形、正方形、正五边形、正六边形四种地板砖，要选择其中两种用以铺地板,则下列选择正确的是（）。设需正三角形地砖m块，正方形地砖n块恰好铺成，则有：A二元一次不定方程的一般形式为:注：该方法对一次项系数较小的方程比较实用。知识梳理二元一次不定方程解的形式和判定:定理1若〔1〕式有整数解:

则〔1〕式的一切解可以表示为:（2）知识梳理定理1的证明：证：把〔2〕代入〔1〕，成立，故〔2〕是〔1〕的解。知识梳理写出下列方程通解的形式：典例分析定理2即为方程〔1〕的解。知识梳理求二元一次不定方程整数解的一般方法先求一个特殊解，再根据定理1写出其通解。对于方程(1),若有解，则可化为：一般地，利用辗转相除法，得到知识梳理求方程的一个特殊解。解：用7、4进行辗转相除法：典例分析求〔1〕的一切整数解。原方程可以化为:

先求〔3〕的一个整数解。107＝37×3－4，37＝4×9+1,从而:变式迁移故〔3〕的一个整数解是:

〔2〕的一个整数解是:

原方程的整数解为:

变式迁移求二元一次不定方程整数解的一般方法求的一切整数解。解：原方程可化为则方程可化为则方程可化为典例分析则方程可化为:

逐步往回代入，可得:

典例分析谢谢欣赏！同余在生活中，我们关注的常常不是某些整数本身，而是用这些数除以某一固定整数所得的余数，这就是我们今天所学的数论中非常重要的一个概念——同余。自学导引观察下面2组除式：探索新知2÷2=1……04÷2=2……06÷2=3……08÷2=4……0……3÷2=1……15÷2=2……17÷2=3……19÷2=4……1……你能发现什么呢？探索新知2÷2=1……04÷2=2……06÷2=3……08÷2=4……0……3÷2=1……15÷2=2……17÷2=3……19÷2=4……1……1、任意一个整数被2除，所得的余数只有0,1两种情况。2、每组除式中余数都相同。3、每组除式中，任意两个被除数的差都能被除数2整除。……知识梳理定义给定一正整数m，把它叫做模。如果用m去除任意两个整数a和b所得余数相同，则称a，b为对模m同余，记作ab(modm)；若余数不同，则称a,b为对模m不同余，记作ab(modm)。同余的概念例如：6-4能被2整除，我们就说6和4对模2同余，记作64（mod2）.知识巩固2014年9月10日是教师节30周年，这一天是星期五，那么9月17日是星期几呢？9月24日呢？我们数一下就可以得出这几天都是星期五。这个现象说明了什么？有什么样的规律？知识巩固我们用今天所学的知识来解释一下，由于9月17日与9月10日相隔7天，9月24日与9月10日相隔14天，而70（mod7），140（mod7），所以这两天都是星期五；另一方面，若与9月10日相隔的天数与0对模7不同余，则这天一定不是星期五。知识梳理同余是数论中的一个非常重要的概念。由以上定义可知道，如果两个数对模m同余，则这两个数被m除所得的余数相同，即这两个数的差能被m整除：存在一个整数k，使得a-b=km，用式子表示为：如果ab（modm),那么a-b=km，即a=km+b.从某个角度来说，也可认为b是a被m除所得的“余数”，这也反映出同余和带余除法之间的内在联系。证明：若m是奇数，则m²≡1（mod8）.典例分析证明：因为m是奇数，所以可设m=2k+1, 其中k为整数，所以 m²=(2k+1)²=4k²+4k+1.典例分析因此有：m²-1=4k²+4k=4k(k+1).而对于任何整数k，k和k+1中一定有一个为偶数，所以m²-1是8的倍数，即m²≡1（mod8）.1、设a、b、m为整数（m﹥0）,若a和b被m除得的余数相同，则称a和b对模m同余，记为a≡b(modm).b≡a(mod10),则b的值可以是（）。A.2015B.2012C.2008D.2006变式迁移变式迁移变式迁移变式迁移谢谢欣赏！同余的性质知识梳理在学习中，处理一些整数问题是，余数会让整个式子看起来复杂，然而我们运用同余符号后，比整除符号和除法算式要方便、快捷很多。为了更好的运用同余符号，我们首先来学习同余的性质。知识梳理由同余的定义可以得到下列性质：①aa(modm).②若ab(modm),则ba(modm).③若ab(modm),bc(modm),则ac(modm).知识探究根据等式的性质，我们来探究一下同余式的性质：因为3=3，5=5，所以3+5=3+5若2≡5（mod3），1≡4（mod3），是否有2+1≡5+4（mod3）知识探究因为3=3，5=5，所以3×5=3×5若2≡5（mod3），1≡4（mod3），是否有2+1≡5+4（mod3）知识探究因为3=3，所以3²=3²若2≡5（mod3），1≡4（mod3），是否有2+1≡5+4（mod3）知识探究右边方框中问题的答案是肯定的，所以我们能够得到一下的性质：④若a≡b（modm），c≡d（modm），则a+c≡b+d（modm）.知识探究求证：若a≡b（modm），c≡d（modm），则a+c≡b+d（modm）.证明：由a≡b（modm），c≡d（modm），根据同余定义可知：m|（a-b）,m|(c-d),根据整除的性质，有m|[（a-b)+(c-d)],也就是：m|[（a+c)-(b+d)],即：a+c≡b+d(modm).知识探究同样的我们还可以证明以下推论：⑤若a≡b（modm），c≡d（modm），

则ac≡bd（modm）.知识探究⑥若a≡b（modm），则aⁿ≡bⁿ（modm）.⑦当c＞0时，若a≡b（modm），则ca≡cb（modm）;若ca≡cb（modm），则a≡b（modm）.知识探究因为3×4=3×4，所以4=4若6×3≡6×8（mod10），是否有3≡8（mod10）右边方框的结论是否成立？是否都和等式的性质完全一样呢？若7×3≡7×13（mod10），是否有3≡13（mod10）知识探究显然，3≡8（mod10），而3≡13（mod10），也就是说，同余式和等式的性质并不是完全相同的。但在一定的条件下，同余式仍然能够保持“消去律”。即：⑧若ca≡cb（modm），且（c,m）=1,则a≡b（modm）.也就是说当c,m互素时，同余式两边可约去c.知识探究求证：若ca≡cb（modm），且（c,m）=1,则a≡b（modm）.证明：由ca≡cb（modm），可得：m|c（a-b）,因为（c,m）=1,根据整除的性质得：m|（a-b）,即为：a≡b(modm).知识探究例如：我们知道21≡9（mod2），而21和9有公约数3，并且（3,2）=1，所以，可在同余式两边同除以3，就得到7≡3（mod2）.谢谢欣赏！整除的判断与弃九法课前练习将下面数字填入相应的位置：2、1、-6、0、3、45、20、-9、-15、108、-98、17、43能被2整除的：能被3整除的：能被5整除的：2、-6、0、20、108、-98-6、0、3、45、-9、-15、1080、45、20、-15知识回顾观察这些数字我们会发现：能被5整除的数的特征：个位数是5或0。能被3整除的数的特征：所有位数上数字相加的和是3的倍数。能被2整除的数的特征：个位数是偶数。知识回顾观察这些数字我们会发现：能被5整除的数的特征：个位数是5或0。能被3整除的数的特征：所有位数上数字相加的和是3的倍数。能被2整除的数的特征：个位数是偶数。知识探究我们尝试用同余的性质对整除的判断作出解释：以3|237为例：我们知道：237=2×100+3×10+7.因为10≡1（mod3），所以30≡3（mod3）.因为100≡1（mod3），所以200≡2（mod3）.根据同余性质，可知200+30+7≡2+3+7（mod3）.因此我们知道，如果2+3+7能够被3整除，那么200+30+7就能被3整除，而2+3+7恰好是237的各位数字之和。典例分析例1.判断93753能否被9整除。解析：能被9整除的数的特征是---所有位数上数字相加的和是9的倍数；只需要求所有位数上的数的和即可。解：因为9+3+7+5+3=27,27能被9整除，所以93753能被9整除。新知学习弃九法：“弃九法”也叫做弃九验算法，利用这种方法可以验算加、减、乘、除计算的结果是否错误。新知学习弃九法的原理是：同余原理。如果一个数的各个数位上的数字之和能被9整除，那么这个数能被9整除；如果一个数各个数位上的数字之和被9除余数是几，那么这个数被9除的余数也一定是几。利用这个性质可以迅速地判断一个数能否被9整除或者求出被9除的余数是几。新知学习例如，3645732这个数，各个数位上的数字之和为：3＋6＋4＋5＋7＋3＋2＝30，30被9除余3，所以3645732这个数不能被9整除，且被9除后余数为3。

但是，当一个数的数位较多时，这种计算麻烦且易错。有没有更简便的方法呢？新知学习因为我们只是判断这个式子被9除的余数，所以凡是若干个数的和是9时，就把这些数划掉，如3＋6＝9，4＋5＝9，7＋2＝9，把这些数划掉后，最多只剩下一个3（如下图），所以这个数除以9的余数是3。

3645732新知学习这种将和为9或9的倍数的数字划掉，用剩下的数字和求除以9的余数的方法，叫做弃九法。新知学习弃九法就是“逢九必划，剩几余几”。一个数被9除的余数叫做这个数的九余数。新知学习利用弃九法可以计算一个数的九余数，还可以检验四则运算的正确性。例2.

求多位数7645821369815436715除以9的余数。

分析与解：利用弃九法，将和为9的数依次划掉。只剩下7，6，1，5四个数，这时口算一下可知，7，6，5的和是9的倍数，又可划掉，只剩下1。所以这个多位数除以9余1。这个大数和1对于9同余。典例分析谢谢欣赏！剩余类新知学习寺庙有一群和尚，九个九个的数，还剩一个；八个八个的数，还剩一个；七个七个的数，还剩一个，问：这座寺庙至少有多少个和尚？以上说明，整数可以有不同的分类方式，下面我们一起来研究剩余类的问题。将和尚的数量除以九，余数为一；除以八，余数为一；除以七，余数为一。每一个这样的集合都称为是模m的一个同余类，或模m的剩余类。我们以rmodm表示r所属的模m的同余类，称r为所属的剩余类的代表。新知学习对于给定的模m，全体整数可以按照对模m是否同余分成m个两两不相交的集合，使得在同一个集合中的任意两个整数对模m一定同余，而属于不同集合中的两个整数对模m一定不同余。新知学习根据上述定义，我们知道整数可以分为模2的两个剩余类0mod2和1mod2；或分为模3的3个剩余类0mod3,1mod3，2mod3.我们还可以将整数按照模4、模5等分为相应的剩余类。我们可以为剩余类定义运算法则，下面我们给出剩余类的加法和乘法运算。新知学习我们以模6的剩余类为研究对象进行说明：模6的剩余类有：0mod6,1mod6,2mod6,3mod6,4mod6,5mod6.我们从3mod6和4mod6中各选择一个元素，例如3和4，那么：3+4≡1（mod6）.新知学习所以3+4一定属于1mod6，所以，我们可以定义：3mod6+4mod6=（3+4）mod6.所以有：3mod6+4mod6=1mod6.同理可定义：3mod6×4mod6=（3×4）mod6.新知学习根据同余的性质可知：（3×4）mod6=12mod6=0mod6，即：3mod6×4mod6=0mod6.新知学习例1根据剩余类的运算定义，计算：5mod6×4mod6.解根据剩余类的乘法定义，我们得出：5mod6×4mod6=（5×4）mod6=20mod6.=2mod6.新知学习定义若m个整数，其中任何两数都不在同一个剩余类里，则这m个整数叫做m的一个完全剩余系。例如0,1是模2的一个完全剩余系；0,4,8是模3的一个完全系；0,5,10,15是模4的一个完全剩余系；……0,1,2，…，m-1是模m的一个完全剩

余系。新知练习练习1计算下列各式。（1）（4mod7+5mod7）×（2mod7）（2）（3mod9+6mod9）×（1mod9）（3）（2mod8+1mod8）×（3mod8）（4）（5mod6+3mod6）×（1mod6）新知练习解

（1）（4mod7+5mod7）×（2mod7）=（9mod7）×（2mod7）=（2mod7）×（2mod7）=（2×2）mod7=4mod7.

（2）（3mod9+6mod9）×（1mod9）=（0mod9）×（1mod9）=（0×1）mod9=0mod9.新知练习

（3）（2mod8+1mod8）×（3mod8）=（3mod8）×（3mod8）=（3×3）mod8=1mod8.

（4）（5mod6+3mod6）×（1mod6）=（8mod6）×（1mod6）=（2mod6）×（1mod6）=（2×1）mod6=2mod6.新知练习练习2利用剩余类的知识判断：n²被5除的余数可能是什么？并证明你的结论。解：以模7的剩余类为研究对象，则有：0mod5,1mod5,2mod5,3mod5,4mod5.当n=0mod5时，n²=（0mod5）²

=（0×0）mod5

=0mod5.新知练习当n=1mod5时，n²=（1mod5）²

=（1×1）mod5

=1mod5.当n=2mod5时，n²=（2mod5）²

=（2×2）mod5

=4mod5.新知练习当n=3mod5时，n²=（3mod5）²

=（3×3）mod5

=4mod5.当n=4mod5时，n²=（4mod5）²

=（4×4）mod5

=1mod5.综上所述，n²除以5的余数为0,1,4.谢谢！欧拉定理·费马小定理新知学习我们知道模6的剩余类为：0mod6,1mod6,2mod6,3mod6,4mod6,5mod6.其中剩余类1mod6,5mod6里的所有数均与6互素，我们称这两个剩余类为与6互素的剩余类。给定模m，如果模m的一个剩余类里面的某个数与m互素，就把这个剩余类叫作一个与模m互素的剩余类。新知学