手机qq刷赞软件-周记300字左右

第九讲 巅峰篇之物不知数
故事引入：
韩信点兵
淮 安民间传说着一则故事——“韩信点兵”其次有成语“韩信点兵，多多益善”。韩信带1500
名兵士打 仗，战死四五百人，站3人一排，多出2人；站5人一排，多出4人；站7人一
排，多出6人。韩信马上 说出人数：1049。
中国剩余定理：
《孙子算经》中有记载：“今有物不知其数：三三数之余二，五五数之余三，七
七数之余二，问物几何？”它的意思就是，有一些物品，如果3 个3 个的数，最后
剩2 个；如果5 个5 个的数，最后剩3 个；如果7 个7 个的数，最后剩2 个；求这
些物品一共有多少？这个问题人们通常把它叫作“孙子问题”， 西方数学家把它称
为“中国剩余定理”．到现在，这个问题已成为世界数学史上闻名的问题．到了明
代，数学家程大位把这个问题的算法编成了四句歌诀：
三人同行七十稀，
五树梅花廿一枝；
七子团圆正半月，
除百零五便得知．
用现在的话来说就是：一个数用3 除，除得的余数乘70；用5 除，除得的余数乘
21；用7 除，除得的余数乘15．最后把这些乘积加起来再减去105 的倍数，就知
道这个数是多少．


同余概念
两个整数a b 若它们除以整数m所得的余数相等，则称
a与b对于模m同余或a同余于b模m或b模m余a
记作a≡b (mod m)
课上习题
【例1】一个大于10的数，除以3余1， 除以5余2，除以11余7，问满足条件的最小自然
数是多少？

【例2】一个大于10的自然数，除以5余3，除以7余1，除以9余8，那 么满足条件的自
然数最小为 ．


【例3】有连续的三个自然数a、a+1、a+2，它们恰好分别是9 、8 、7 的倍数，求这三个
自然数中最小的数至少是多少？





总结
①凑“多”相同，即把余数处理成相同
条件：余数与除数的和相同
②凑“缺”相同，即把余数处理成缺的数字相同
条件：除数与余数的差相同
③先考虑上面两种，如果都不行，可使用逐步满足法或使用“中国剩余定理”．
④逐步满足法：先满足条件一，得N，再用“M =N +已满足除数公倍数”来满足下一个条件．
课后习题
【闯关1】刘叔叔养了400 多只兔子。如果每3 只兔子关在一个笼子里，那么最后一个笼子
里有2 只；如果5 只兔子关在一个笼子里，那么最后一个笼子里有4 只；如果每7 只兔子关
一个笼子里，那么最后一个笼子里有5 只。请问：刘叔叔一共养了多少只兔子？


【闯关2】有三个连续的自然数，它们从小到大依次是5、7、9 的倍数。这三个连续自然数
最小是多少？




【闯关3】有一些自然数
n
，满足： 2^n
-n
是 3的倍数，3^n-
n
是 5的倍数，5^n-
n
是 2的倍
数。请问：这样的
n
中最小的是多少？

第十讲：费马小定理

费马小定理是数论中的一个重要定理，其内容为：
假如p是质数，且(a,p)=1，那么a^(p-1) ≡1(mod p)
假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1
一、准备知识：
引理1：若a,b,c为任意3个整数，m为正整数，且(m,c)=1，则当ac≡bc(mod m)时，有a
≡b(mod m)
证明：ac≡bc(mod m)可得ac–bc≡0(mod m)可得(a-b)c≡0(mod m)
因为(m,c)=1即m,c互质，c可以约去，a–b≡0(mod m)可得a≡b(mod m)
引理2：若m为整数且m>1,a[1],a[2],a[3],a[4]，…a[m]为m个整数，若 在这m个数中任
取2个整数对m不同余，则这m个整数对m构成完全剩余系。
引理3如果a,b,c,d是四个整数，且a≡b(mod m),c≡d(mod m)，则有ac≡bd(mod m)
证明：由题设得ac≡bc(mod m),bc≡bd(mod m)，由模运算的传递性可得ac≡bd(mod m)

引理 4．设m是一个整数，且m>1，b是一个整数且(m,b)=1。如果a1,a2,a3,a4，…am是模< br>m的一个完全剩余系，则ba[1],ba[2],ba[3],ba[4]，…ba[m]也构成模m的 一个完全剩余
系。
证明：若存在2个整数ba[i]和ba[j]同余即ba[i]≡ba[j](mod m)，
根据引理1则有a[i]≡a[j](mod m)。
根据完全剩余系的定义和引理3
可知这是不可能的，
因此不存在2个整数ba[i]和ba[j]同余。
可知ba[1],ba[2],ba[3],ba[4]，…ba[m]构成模m的一个完全剩余系。
二、证明过程：
构造素数p的完全剩余系P={1,2,3,4…(p-1)}，因为(a,p)=1，由引理3可得
A={a,2a,3a,4a，…(p-1)a}也是p的一个完全剩余系。
令W=1*2*3*4…*(p-1)，显然W≡W(mod p)。
令Y=a*2a*3a*4a*…(p-1)a，
因为{a,2a,3a,4a，…(p-1)a}是p的完全剩余系，
由引理2以及引理4可得a*2a*3a*…(p-1)a≡1*2*3*…(p-1)(mod p)即
W*a^(p-1)≡W(modp)
易知(W,p)=1，由引理1可知a^(p-1)≡1(modp)

第九讲 巅峰篇之物不知数
课后习题：
【闯关1】刘叔叔养了400 多只兔子。如果每3 只兔子关在一个笼子里，那么最后一个笼子
里有2 只；如果5 只兔子关在一个笼子里，那么最后一个笼子里有4 只；如果每7 只兔子关
一个笼子里，那么最后一个笼子里有5 只。请问：刘叔叔一共养了多少只兔子？
解析：令有满足后面三个条件的兔子数为a 只兔子，则根据条件有：
a÷3...2,a÷5...4，a÷7...5
满足前两个的所有的自然数为：14+15
n
。
所以有：（14+15
n）÷
7...5
由于14+15
n
≡15
n
≡
n（
mod 7）所以
n
最小取 5。
所以满足条件的最小的为89。现在刘叔叔应该养了89+3×105=404（只兔子）
答：刘叔叔一共养了404个兔子。
【闯关2】有三个连续的自然数，它们从小到大依次是5、7、9 的倍数。这三个连续自然数
最小是多少？
解析：根据题意，令这三个连续的自然数分别是：
a
、
a +
1、
a +
2，则它们从小到大依
次是5、7、9 的倍数。所以我们有：
a÷5...0,a÷7...6，a÷9...7
满足前两个的所有的自然数为：20+35
n
所以有：20+35
n÷
9...7，所以35
n ÷
9...5，有8
n ÷
9...5，则n 最小取 4。
此时
a
最小取160。
所以这三个自然数为160、161、162。

【闯关3】有一些自然数
n
，满足： 2^n
-n
是 3的倍数，3^n-
n
是 5的倍数，5^n-
n
是 2的倍
数。请问：这样的
n
中最小的是多少？
解析：根据题目意思，我们能够知道

2
n
n(mod3)
n

3n(mod5)


5
n
n(mod2)

根据
2n(mod3)
可知，由于2^n除以3的余数 是2,1,2,1,2,1，两个为一个周期，n除
以3的余数是1,2,0,1,2,0三个是一个周 期，则满足条件的n的取值是6k+4,6k+5;
根据
3n(mod5)
，由于 3^n除以5的余数是3,4,2,1,四个为一个周期，n除以5的余数
是1,2,3,4,0五个是 一个周期，则满足条件的n的取值是20p+7,20p+12;20p+13;20p+14
n
n

根据
5n(mod2)
，n必须为奇数。
则n应同时符合6k+5以及20p+7,20p+13
接下来就是尝试，当p=1时，27与33均不能表示成6k+5的形式，不符合
当p=2,47=6×7+5
所以n的最小值是47
答：n的最小值是47

n