下载文档原格式
第二讲同余（数论复赛辅导）第二讲同余一.基础知识1.定义1. 设m 是正整数，若用m 去除整数b a ,，所得的余数相同，则称a 与b 关于模m 同余，记作)(mod m b a ≡，否则称a 与b 关于模m 不同余，记作a)(m o d m b .例如：)15(mod 434≡，)7(mod 11000-≡，98(mod 2) 等等。
当m b <≤0时，)(mod m b a ≡，则称b 是a 对模m 的最小非负剩余。
对于固定的模m ，通常有下面的性质：性质1. )(mod m b a ≡的充要条件是,a mt b t Z =+∈也即)(|b a m -。
性质2.同余关系满足以下规律：（1）（反身性）)(mod m a a ≡；（2）（对称性）若)(mod m b a ≡，则)(mod m a b ≡；（3）（传递性）若)(mod m b a ≡，)(mod m c b ≡，则)(mod m c a ≡；（4）（同余式相加）若)(m od m b a ≡，)(mod m d c ≡，则)(mod m d b c a ±≡±；（5）（同余式相乘）若)(mod m b a ≡，)(mod m d c ≡，则)(mod m bd ac ≡；注意：① 反复利用（4）（5），可以对多于两个的（模相同的）同余式建立加、减和乘法的运算公式；② 特别地，由（5）易推出：若)(mod m b a ≡，c k ,为整数且0>k ，则)(mod m c b c a k k ≡；③ 同余式的消去律一般并不成立，即从)(mod m bc ac ≡未必能推出)(mod m b a ≡，可是我们却有以下结果：若)(mod m bc ac ≡，则≡),(mod c m m b a . 由此可以推出：（6）若,1),(=m c )(mod m bc ac ≡，则有)(mod m b a ≡，即在c 与m 互素时，可以在原同余式两边约去c 而不改变模.（7）若)(mod m b a ≡，d ｜m ，则)(mod d b a ≡；（8）若)(mod m b a ≡，0≠d ，则)(mod dm db da ≡；（9）若(mod )(1,2,,)i a b m i k ≡=，则12(mod [,,,])k a b m m m ≡，特别地，若12,,,k m m m 两两互素时，则有12(mod )k a b m m m ≡；性质3.若k i m b a i i ,,2,1),(m od =≡，则)(mod 11m b a k i k i i i ∑∑==≡；11(mod )k ki ii i a b m ==≡∏∏；性质4.设)(x f 是系数全为整数的多项式，若)(mod m b a ≡，则))(mod ()(m b f a f ≡。
数论中的同余与模运算练习题及解析一、概念解析在数论中，同余是一种重要的关系。
对于整数a、b和正整数m，如果整数a和b除以m所得的余数相同，则称a与b关于模m同余，记作a≡b(mod m)。
同余关系具有以下性质：1. 反身性：a≡a(mod m)，任何整数与自身模m同余。
2. 对称性：如果a≡b(mod m)，则b≡a(mod m)。
3. 传递性：如果a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。
模运算是指对一个整数a进行除法运算后取余数的运算。
对于整数a和正整数m，a对m取模运算的结果记作a mod m。
模运算具有以下性质：1. 加法性质：(a+b) mod m = (a mod m + b mod m) mod m2. 减法性质：(a-b) mod m = (a mod m - b mod m) mod m3. 乘法性质：(a×b) mod m = (a mod m × b mod m) mod m二、练习题1. 求100 mod 7的值。
2. 若a≡2(mod 5)，b≡3(mo d 5)，求a+b的值。
3. 若a≡9(mod 11)，b≡7(mod 11)，求a-b的值。
4. 求12×25 mod 7的值。
5. 求13×17 mod 10的值。
三、解析1. 根据模运算的性质，100 mod 7等价于100除以7所得的余数。
由于100÷7=14余2，所以100 mod 7等于2。
2. 根据同余关系的定义，a≡2(mod 5)和b≡3(mod 5)意味着a和b分别与2和3关于模5同余。
根据加法性质，a+b≡(2+3)(mod 5)≡5(mod5)≡0(mod 5)。
所以a+b的值为0。
3. 类似于第2题的解法，根据同余关系的定义，a≡9(mod 11)和b≡7(mod 11)意味着a和b分别与9和7关于模11同余。
根据减法性质，a-b≡(9-7)(mod 11)≡2(mod 11)。
第4讲同余定理同余定理是奥数考试中最常考的题型，同时也是数论知识中最具有代表性的知识之一。
本讲将带领大家一起领略巧妙的数论方法，相信大家一定会被同余的意想不到的魅力所吸引。
若a c ÷余数为m ，b c ÷余数为n ，则()a b c +÷的余数等于()m n c +÷的余数；()a b c -÷的余数等于()m n c -÷的余数（m n >）或()m c n c +-÷的余数（m n <）。
a b c ⨯÷的余数等于m n c ⨯÷的余数。
特别的，当m n =时，()a b -是c 的倍数。
若两个整数a 、b 被同一个非零自然数c 除，余数相同，那么称a 、b 对于m 同余，用式子表示为(mod )a b c ≡.编写说明知识要点【例1】 有三个自然数a ，b ，c ，其中a 除以c 的余数是1，b 除以c 的余数是2，a b +恰好是c 的倍数，求c 的值。
【分析】 根据同余定理，a b +除以c 的余数是3，而a b +恰好是c 的倍数，所以3c =。
【拓展】 已知：6a b c -=，其中a 、b 、c 均为正整数，且b 除以6的余数是3，则a 除以6的余数是多少?【分析】 a b -是6的倍数，所以a 和b 除以6的余数相同，a 除以6的余数是3。
【温馨提醒】这边可以帮助学生总结出和（或差）的余数等于余数的和（或差）的余数。
【例2】 135********⨯⨯⨯⨯⨯的乘积除以8的余数是多少？【分析】 1，3，5，7，9，...，2007，2009除以8的余数分别为1，3，5，7，1，3，5，7， (1)3，5，7，1，1357⨯⨯⨯除以8的余数是1，所以135********⨯⨯⨯⨯⨯除以8的余数是1。
【温馨提示】这边可以帮助学生总结出积的余数等于余数的积的余数。
【拓展】 234199077777+++++的末两位是多少？【分析】 要求末两位，可以转化为求其除以100的余数是多少，7除以100余数是7，27除以100余数是49，37343=除以100余数为43，472401=除以100余数是1，54777=⨯除以100的余数是7，依此类推，余数是以7，49，43，1循环的，199044972÷=，所以所有余数的和是(749431)497749497+++⨯++=，49756除以100的余数是56，所以和的末两位是56。
![[第14讲] 初等数论(2)同余初步(中)](https://uimg.taocdn.com/08ae68c6c1c708a1284a44dc.webp)
【例1】 （常规题型）数1978n 与1978m 最后三位相等，试求使得m n +最小的正整数m n ，，其中n m > 【解析】 意即()19781978mod1000n m ≡所以()19781978mod8n m ≡()19781978mod125n m ≡1978的100次方满足mod125余1容易算出1978的1次方，4次方，20次方均不满足mod125余1（常见证法）立刻知道n m -至少为100又()19781978mod8n m ≡，3m ≥106m n +=，当3106m n ==，时取得最小值【例2】 （常规题型）数列{}13511n x =，，，满足关系112n n n x x x +-=+，n 大于等于2；数列{}n x 为71755161，，，，……满足关系1123n n n y y y +-=+，n 大于等于2.证明：此两数列没有相等的项【解析】 写出此两数列的的前若干项，容易发现（mod8）后他们都是周期数列：1，3，5，3，5，3，5……7，1，7，1，7，1，7，1……于是容易得证。
【点评】 类似的递推公式必然会得到一个mod m 周期数列，（证明略）要讲明白这一点。
5数论 同余问题选讲【例3】 试找出两个互素的四位数A 和B ，使得对于任何正整数m 和n ，数m A 和n B 都至少相差2009【解析】 取40018001A B ==，考虑mod 4000，立刻得证【例4】 设p 为给定之正整数，试确定()2221nm p p --之最小正值，这里m n ，为任意正整数。
【解析】 最小正值为()()2222141p p p --=-.下面给出证明： ()()222mod42p p p ≡-()()22121mod42p p p -≡--于是()()()22211mod42m n p p p --≡- 又()()()22222112mod4m n p p p p --≡--，所以()()222141m np p p ---≥命题得证. 点评：结合例3来讲【例5】 33N >且N 为奇数，证明：将n 元集合{}0123S = ，，，任意去掉一个元素后，总可以将剩下的元素分为两组，每组()1/2n -，两组的和mod N 同余【解析】 设挖去元素为x 注意到变换(){}mod T S x a x N a S =-=-∈，于是问题化为挖去元素为0时的特殊情形 当N 被4除余1时： 可分为3112244N N N N ⎧⎫--⎨⎬⎩⎭ ，，，，，，和余下作为一组，符合要求 当N 被4除余3时：43N k =+可分为{}124441542231k k k k k --++ ，，，，，，，，，，余下作为一组，也符合要求。
初等数论同余方程组初等数论是数学中的一个分支，主要研究自然数的性质和整数的性质。
同余方程组是初等数论中的一个重要概念，它涉及到数与数之间的整除关系。
本文将介绍同余方程组的定义、性质以及解法，并通过例题来加深理解。
一、同余方程组的定义同余方程组是由若干个同余方程组成的一组方程。
同余方程的定义如下：对于整数a、b和正整数m，如果m能整除(a-b)，即(a-b)能被m整除，则称a与b对于模m同余，记为a≡b(mod m)。
这里的≡表示同余关系。
二、同余方程组的性质1. 同余关系具有自反性、对称性和传递性。
即对于任意的整数a、b和正整数m，有a≡a(mod m)，a≡b(mod m)等价于b≡a(mod m)，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。
2. 同余关系具有加法和乘法的性质。
即对于任意的整数a、b和正整数m，若a≡b(mod m)，则a+c≡b+c(mod m)，ac≡bc(mod m)。
三、同余方程组的解法1. 线性同余方程组的解法：线性同余方程组是形如ax≡b(mod m)的方程组，其中a、b为整数，m为正整数。
若a与m互质，则存在唯一的解x0，且x≡x0(mod m)。
若a与m不互质，且b可被a整除，则方程组有无穷多个解，否则无解。
2. 中国剩余定理：中国剩余定理适用于一组两两互质的模数的同余方程组。
设m1、m2、...、mn为两两互质的正整数，a1、a2、...、an为整数，则同余方程组：x≡a1(mod m1)x≡a2(mod m2)...x≡an(mod mn)有唯一的解x，且0≤x<m1m2...mn。
四、例题解析1. 解线性同余方程组：求解方程组2x≡3(mod 5)和3x≡4(mod 7)。
首先，对于第一个方程，由于2与5互质，所以存在唯一解x0。
根据扩展欧几里得算法，我们可以求出x0=4。
然后，将x0代入第二个方程，得到3*4≡4(mod 7)，即12≡4(mod 7)。
第三讲：初等数论3——同余的性质和应用三、巩固练习1. 今天是星期三，到第1000天是星期几？解：从今天到第1000天相隔999天，1000-1≡5(mod 7)，3+5-7=1，是星期一.2. 若1059，1417，2313分别被自然数x除时，所得余数都是y，则x-y= ．解：∵1059≡y(mod x) ，1417≡y(mod x) ， 2313≡y(mod x)，∴1417-1059=358≡0(mod x)，2313-1417=896≡0(mod x)， 2313-1059=1254≡0(mod x)又（358，896，1254）的最大公约数为2，则x=2， y=1，x-y=1．3. 若正整数a和1995对于模6同余，则a的值可以是（）A. 25B. 26C. 27D. 28解：1995除以6的余数是3，a≡1995 (mod 6)，a除以6的余数也是3，只有a=27，选C.4. 一个两位数被7除余1，它的反序数被7除也余1，那么这样的两位数共有（）A. 2个B. 3个C. 4个D. 5个解：列出满足条件的所有两位数：15，22，29，36，43，50，57，64，71，78，85，92，99 两位数据反序数也满足条件的有：22，29，92，99，选C.5. 设n为自然数，则32n+8被8除的余数是_________.解：由32n+8=9n+8，知32n+8≡1n+0(mod 8)≡1(mod 8) ，故32n+8被8除余1.6. 黑板上写着13个数：1908，1918，1928，1938，1948，1958，1968，1978，1988，1998，2008，2018，2028．小明第一次擦掉其中的一个数，第二次擦掉剩下数中的两个数，第三次擦掉剩下数中的三个数，第四次擦掉剩下数中的四个数，他想使得每次擦掉数后剩下的所有数之和为13的倍数，小明的意图能否达到？如果可以，给出一种可行的方法，不能请说明理由．答案：可以：依次擦掉（2028）；（1958，1968）；（1908，1938，1978）；（1918，1928，1998，2008）。
初等数论（三）--同余基本性质：（1） 反身性：(mod )a a m ≡（2） 对称性：若(mod ),a b m ≡则(mod ),b a m ≡（3） 传递性：如果(mod ),a b m ≡(mod ),b c m ≡那么(mod ),a c m ≡以上三个性质说明∙“同余是一个等价关系，Z 中元素可以按照模m 分成m 个类，粗略地讲，用一类中的元素可以认为是相同的”（4） 如果(mod ),a b m ≡(mod ),c d m ≡那么(mod ),(mod ),a c b d m ac bd m ±≡±≡（5） 如果(mod ),a b m ≡那么(mod ),n n a b m ≡（6） 如果(mod )ac ab m ≡，不一定有(mod )c b m ≡（整数之间的乘法消去律不一定成立），（7） 若(mod ),ac bc m ≡则mod (,)m a b c m ⎛⎫≡ ⎪⎝⎭。
因此，(,)1c m =时，才会有(mod )a b m ≡。
例1.若质数5,p ≥并且21p +也是质数，证明：41p +是合数。
例2.对于任何n 个整数的集合，存在一个子集，该子集的元素之和被n 整除。
例3.证明表达式23,95x y x y ++按照相同的,x y 被17整除。
例4.设3p ≥为奇质数且111...21a p b +++=-， 证明：p a 。
作业：证明：3131421x x ++++被7整除。
例5.30对夫妻围着圆桌而坐。
证明：至少有两名妻子到各自丈夫的距离相等。
例6.设(,)1a m =，证明方程(mod )ax b m ≡在{0,1,2,3,...,1}m -中有唯一解。
例7.设01,,,,1,2,3,...n n a b x N x ax b n -∈=+=。
证明：数列12,,....,,...n x x x 不可能都是质数。
例8.证明方程2222x y z xyz ++=只有一个整数解0x y z ===。
第五章二次剩余理论例题分析补充知识高斯逐步淘汰法：首先，不妨设因解同余方程x 2=a+py，故，因而在求y 的值时，不必考虑大于4p的整数，这就大大缩小了讨论的范围。
其次，任取素数q≠p，求出q 的平方非剩余为a 1,a 2……a s 并以v 1,v 2,……v s 表示同余方程a+py≡a 1(mod q),a+py≡a 2(mod q)，……a+py≡a s (mod q)的解，由于平方数一定为任何模的平方剩余，故若取y≡v i (mod q)，则a+py 是q 的平方非剩余，因而a+py 一定不是平方数。
而不能有x 2=a+py 这样可淘汰满足y≡v i (mod g)的各个y 的值。
取不同的q，淘汰y 的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出（1）的解。
例：解同余方程x 2≡73(mod137)解∵⎪⎭⎫ ⎝⎛13773=1，∴x 2≡73(mod137)有二个解因为p=137，故0<y≤34取q=3，则2为3一平方非剩余。
解同余方程73+137y≡3(mod3)得y≡2(mod 3)，从不大于34的正整数中淘汰形如y=2+3t 的数，即有下面1，3，4，6，7，9，10，12，13，15，16，18，19，21，22，24，25，27，28，30，31，33，34。
再取q=5，2，3为g 的平方非剩余的同余方程73+137y≡2(mod5)，73+137y≡3(mod5)解为y≡2(mod5),y≡0(mod5)，再从前面的数中淘汰形如y=2+5t 和y=5t，有下面1，3，4，6，9，13，16，18，19，21，24，28，31，33，34。
又取q=7，3，5，6为g 的三个平方非剩余的同余方程73+137y≡3,5,6(mod7)的y≡0,4,6(mod7)淘汰y=4+7t,7t,6+7t,就只留下了1,3,9,16,19,24,31,33。
将上述数代入137y+73=x 2及137×3+73=484=222故x≡±22(mod137)为本题同余方程的解。
第1讲初等数论中的同余问题复旦大学附属中学万军2011年协作体夏令营系列讲座(一)初等数论中的同余问题复旦附中万军同余的概念和性质：设为非零整数，如果整数满足，则称和对模同余，记为；否则称和对模不同余，记为．注意到，，故，所以我们总是可以假定为正整数．对于固定的模，同余有很多性质：1）同余是一种等价关系，即有①自反性：；②对称性：若，则；③传递性：若，，则．2）加法、减法、乘法和乘方运算：若，，则，，．3）除法运算：，则．特别地，若，则．4）同余组：同时成立的充要条件是剩余类与完全剩余系：设为一个给定的正整数，则全体整数可以分成个集，记为，其中，则称为模的剩余类．模的剩余类有下列性质：1）每个整数必属于且仅属于模的一个剩余类中；2）两个整数同在一个剩余类中的充要条件是这两个整数模同余．事实上，，0≤≤，有如果个整数中不存在两个数属于同一剩余类，则称为模的一个完全剩余系（或称完系）．最常用的剩余系称为模的非负最小完全剩余系．此外也常用到绝对值最小完全剩余系，它们是：当为奇数时，当为偶数时，或完全剩余系有下列性质：1）个整数作为模的一个完全剩余系的充要条件是它们两两模不同余；2）若是模的一个完全剩余系，，那么也是模的一个完全剩余系；也常这样描述：设是正整数，，若通过模的一个完全剩余系，则也通过模的一个完全剩余系．3）若是互质的两个正整数，而分别通过的一个完全剩余系，则通过的一个完全剩余系．如果一个模的剩余类里面的数与互质，就把它叫做一个与模互质的剩余类，在与模互质的全部剩余类中，从每一类各任取一个代表元所组成的数集，叫做模的一个简化剩余类系（或缩系）．定理1：模的剩余类是模互质的剩余类的充要条件是此类中有一个数与互质．因此与模互质的剩余类的个数是，模的每一个简化剩余类系是由与互质的个对模不同余的整数组成的．其中，（欧拉函数）是定义在正整数上的函数，它在正整数上的值是集合中与互质的数的个数．定理2：若是个与互质的数整，并且两两对模不同余，则是模的一个简化剩余类系．定理3：若，通过模的一个简化剩余系，则也通过模的一个完全剩余系．定理4：若是互质的两个正整数，而分别通过的一个简化剩余系，则通过的一个简化剩余系．推论：若是互质的两个正整数，则．下面的几个定理在处理数论问题时经常用到，并且它们本身的证明也是很好的例题．1、（欧拉函数）是定义在正整数上的函数，它在正整数上的值是集合中与互质的数的个数，求．2、（欧拉定理）设是正整数，且，则．3、（费尔马小定理）若是质数，是正整数，则．4、（拉格朗日定理）设为素数，多项式是一个模为次整系数多项式，则关于的同余方程（在模的意义下）至多有个不同的解．5、（威尔逊定理）设为素数，则．6、设为整数，为正整数，若存在，使得，则称为模的二次剩余，否则，称为模的二次非剩余．7、已知斐波那契数列，设为大于5的素数，证明：8、求所有满足下面两式的三元组，其中为奇素数，为大于1的整数．①②练习题：1、设为素数，证明：存在无穷多个，使得．2、对，如果对任意，只要，就有，那么就称具有性质．1）证明：每个素数都具有性质；2）是否存在无穷多个合数具有性质？3、求所有满足的正整数和素数．（其中欧拉函数）4、求不定方程的整数解为．（其中表示最接近整数的5的倍数）5、对于正奇数，若存在正奇数，满足，求满足条件的正奇数的总和．6、设，，正整数数组满足：，如果不能将分为和相等的两组数，那么称数组为“优秀的”，求所有的“优秀的”数组．讲座一参考答案 2011-7-18例题答案：1.解：设，其中是质数，是正整数，由定理4的推论得，由欧拉函数的定义知等于减去集合中与不互质的元素个数，也就是减去集合中与不互质的元素个数，又是质数，∴∴另证：本定理也可以用容斥原理来证明．设，其中是质数，是正整数，记，∴由容斥原理得2.证明：设是模的一个简化剩余系，则由定理3知，也是模的一个简化剩余系．∴与且仅与中的一个数对模同余，∴即（*）又是模的一个简化剩余系，故．∴∴由（*）知：．3.证明：若，则，结论显然成立；若，由欧拉定理知，即．注：费尔马小定理的另一种形式：若是质数，是正整数，，则．另证：对进行归纳，当时，结论显然成立；假设时，结论也成立，即则．（其中用到了，当时，）∴对任意，有．4.证明：对进行归纳．当时，由于，则无解，∴定理成立．假设定理对所有次数小于的多项式都成立，现设存在一个次多项式，使得同余方程有个（在模的意义下）不同的解．利用因式定理，可设，则在模的意义下是一个至多次的多项式．由都是的解，知对≤≤，都有，而，故，从而至少有根，与归纳假设矛盾，所以，定理对次整系数多项式也成立．综上，定理成立．5.证明：当时，显然成立；当为奇素数时，考虑多项式可以看到的最高次数为又当时，，由费尔马小定理知，∴由拉格朗日定理知，的展开式中各项系数都是的倍数，∴又为奇素数，为偶数，∴，得证．6.设为奇素数，且，证明：是模的二次剩余充要条件是；是模的二次非剩余充要条件是．证明：若为模的二次剩余，即存在，使得．由，可知，由费尔马小定理知，．反过来，若，则是同余方程的解，由拉格朗日定理知，该方程至多有个解，而都是该同余方程的解，∴它们就是该方程的全部解，∴存在，使得．另一方面，若是模的二次非剩余，则但由费尔马小定理，，即∴，即反过来，，又是模的二次剩余，则∴与为奇素数矛盾．7.证明：知斐波那契数列的通项公式（）对大于5的素数，由费尔马小定理可知，∴，又∴或如果（其中用到了，当时，，及费尔马小定理）∴如果，类似计算可得，则综上，8.解：显然是①的解，代入②解得，∴都是方程的解．另外，当或时，同样可以得出上述解．下设≥5，当时，由②知而∴或但是，∴上式不可能成立．∴≥3由①知同理可得，∴∴③又在≥4时，单调递增，∴≥∴③式≤≤矛盾．∴由于又，没有平方因数，∴∴≥7，≥11并且≤≤，∴≤与③式矛盾．∴本题的解只能是．练习题答案：1、设为素数，证明：存在无穷多个，使得．证明：当时，只需要取为偶数即可；当为奇素数时，由费尔马小定理知，，此时令，则．2、对，如果对任意，只要，就有，那么就称具有性质．1）证明：每个素数都具有性质；2）是否存在无穷多个合数具有性质？证明：对任意素数，由，可知，从而由费尔马小定理知，∴，可得，∴∴．2）存在无穷多个合数具有性质．例如：对奇素数，数都具有性质．事实上，，则为奇数，∴又，∴或若，由1）知；若，由费尔马小定理知，，这时，∴综上，总有，∴，即数都具有性质．3、求所有满足的正整数和素数．（其中欧拉函数）解：若时，，∴为偶数，且中所有的奇数均与互质，∴若为奇素数，设，其中是质数，是正整数，且∴，∴，又∴，但是，当时，，而∴，，∴∴综上：时，；时，；4、求不定方程的整数解为．（其中表示最接近整数的5的倍数）解：由，若，设，则，又，∴解得；若，设，则，又∴解得或．5、对于正奇数，若存在正奇数，满足，求满足条件的正奇数的总和．解：由为正奇数得：又由为正奇数得：∴另一方面：若，可以找到满足条件的正奇数当时，则；当时，∴共个正奇数的平方和．综上：，则其总和为．6、设，，正整数数组满足：，如果不能将分为和相等的两组数，那么称数组为“优秀的”，求所有的“优秀的”数组．解：设数组为“优秀的”，对1≤≤，考虑下面的个数：，其中由于不能将分为和相等的两组数，即其中没有若干个数之和等于，∴上面的个数中，除外，其余任意两项对模不同余，否则这两项之差等于．另外，上面的个数中，必有两个数模同余，∴对都成立∴又∴综上：当为奇数时，中有一个是，其余都是1，或；当为偶数时，中有一个是，其余都是1．。
第20章 同 余20。
1.1★（1）证明:任意平方数除以4,余数为0或1； （2)证明：任意平方数除以8，余数为0、1或4． 解析 （1）因为奇数， 偶数, 所以，正整数(2)奇数可以表示为,从而奇数． 因为两个连续整数、中必有一个是偶数，所以是8的倍数，从而奇数． 又，偶数(为整数）．若偶数,则． 若奇数，则． 所以，平方数评注 事实上，我们也可以这样来证：因为对任意整数，有，±1，2()，所以，，1()；又0，±1，±2,±3，4(）,所以,0，1，． 20。
1.2★求证：一个十进制数被9除所得的余数，等于它的各位数字被9除所得的余数．解析 设这个十进制数． 因101（)，故对任何整数≥1，有．因此．即被9除所得的余数等于它的各位数字之和被9除所得的余数．评注 (1)特别地,一个数能被9整除的充要条件是它的各位数字之和能被9整除．(2)算术中的“弃九验算法”就是依据本题的结论． 20。
1.3★★求证：（1）；（2);()222214411(m o d 4)k k k =+=++≡()222240(m o d 4)k k ==≡21(m o d 4),;0(m o d 4),.n n n ⎧≡⎨⎩奇偶为数为数21k +()22441411k k k k =++=++k1k +()41k k +()2811m o d 8i =+≡()22224k k ==kk =2t =()224160m o d 8k t ==k =21t =+()()22244211644(m o d 8)k t t t =+=++≡()()()0m o d 8,1m o d 8,4m o d 8.⎧⎪≡⎨⎪⎩a 0a ≡mod40a ≡mod4a ≡mod82a ≡()4mo d 81210n n Aa a a a a -=≡mod9k ()1011m o d 9k k≡=1210n n Aa a a a a -=1110101010nn n n a a a a --=⨯+⨯++⨯+()110m o d 9n n a a a a -≡++++A ()199985517+()2837n +(3）． 解析 （1)因，所以 ，，于是．（2)因为,，所以，即 ．（3）因为,，所以 , 于是．20.1.4★★对任意的正整数，证明：能被1897整除．解析 ,7与271互质．因为 ,， ，，所以,故7|又因为 ， ，，所以，故271｜因(7，271）=1，所以1897整除．20.1。
福师期末考试《初等数论》复习题及参考答案本复习题页码标注所用教材为：教材名称 单价 作者版本 出版社 初等数论14.20闵嗣鹤，严士健第三版高等教育出版社复习题及参考答案一一、填空(40%)1 、求所有正约数的和等于15的最小正数为 考核知识点：约数，参见P14-19 2、若1211,,,b b b 是模11的一个完全剩余系，则121181,81,,81b b b +++也是模11的 剩余系.考核知识点：完全剩余系，参见P54-573．模13的互素剩余系为考核知识点：互素剩余系，参见P584.自176到545的整数中是13倍数的整数个数为 考核知识点：倍数，参见P11-13 5、如果p 是素数,a 是任意一个整数,则a 被p 整除或者考核知识点：整除，参见P1-46、b a ,的公倍数是它们最小公倍数的 . 考核知识点：最小公倍数，参见P11-137、如果b a ,是两个正整数,则存在 整数r q ,,使r bq a +=,b r ≤0.考核知识点：整除，参见P1-4 8、如果n 3，n 5，则15（ ）n . 考核知识点：整除，参见P1-4二、(10%)试证：6|n(n+1)(2n+1)，这里n 是任意整数。
考核知识点：整除的性质，参见P9-12提示：i)若 则ii)若 则iii)若 则又三、(10%)假定a 是任意整数，求证a a (mod )++≡2103或a a (mod )+≡203考核知识点：二次同余式，参见P88提示:要证明原式成立，只须证明231a a ++，或者23a a +成立即可。
四、（10％）设p 是不小于5的素数，试证明21(mod 24)p ≡ 考核知识点：同余的性质，参见P48-52提示： 且是不小于5的素数．又 且是不小于5的素数．只能是奇数且即即五、(15%)解同余式组 51(mod7)142(mod8)x x ≡⎧⎨≡⎩考核知识点：同余式，参见P74-75 提示∵ (14，8)=2 且 2 | 2 ∴ 14x ≡2(mod8) 有且仅有二个解解7x ≡1(mod4) ⇒ x ≡3 (mod4) ∴ 6x ≡10(mod8)的解为 x ≡3，3+4(mod8) 原同余式组等价于()()3mod 73mod8x x ≡⎧⎪⎨≡⎪⎩ 或()()3mod 77mod8x x ≡⎧⎪⎨≡⎪⎩分别解出两个解即可。
第四章同余式例题分析定义1：当（a ，m ）=1时，若ab )(mod 1m ≡，则记b )(mod 1m a ≡，称为形式分数。
根据定义和记号，则m a c a c关于模表示1⋅，则有下列性质1、.,),(mod 2121Z t t m mt a mt c a c∈++≡2、若（d ，m ）=1，且).(mod ,,1111m a ca c dc c da a ≡==则利用形式分数的性质把分母变成1，从而一次同余式的解。
例1：解一次同余式)25(mod 1917≡x 解：∵（17，25）=1，原同余方程有解，利用形式分数的性质，同余方程解为)25(mod 7172418861719≡--≡≡--≡≡x 例2：解同余方程组⎪⎩⎪⎨⎧≡≡-≡)15mod (1)10mod (6)12mod (2x x x 解：∵（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1∴原同余方程有解，且等位于⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≡≡≡≡-≡-≡)5mod ()3mod (1)5mod (6)2mod (6)3mod (2)4mod (2x x x x x x ⇔⎪⎩⎪⎨⎧≡≡-≡)5mod (1)3mod (1)4mod (2x x x 此时变成模两两互素由孙子定理可求得其解为：)60(mod 46≡x 例3：解一次同余式组⎩⎨⎧≡≡)4(mod 13)75(mod 5751x x 解:用常规方法先求每一个一次同余式的解，得到下列一次同余式组⎩⎨⎧≡≡)4(mod 3)75(mod 57,32,7x x 然后用孙子定理求解，所以同余方程组有3个解，且解分别为)300(mod 7≡x ，)300(mod 107≡x ，)300(mod 207≡x 例4：设2p +1是素数，则)(mod )()!(12012+≡-+p P p 证：设n =2p +1,由假设n 为素数，于是由威尔逊定理有(n -1)!≡-1(mod n )由于(n -1)!+1≡(n -1)(n -2)…(p +2)(p +1)p (p -1)…3·2·1+1≡1·(n -1)·2(n -2)·2(n -3)…·(p -1)[n -(p -1)]·p ·(n-p )+1≡p !(n -1)(n -2)…(n-p )+1≡(p !)2(-1)p +1(mod n )∴(p!)2(-1)p +1≡0(mod n )∴(p !)2+(-1)p ≡0(mod 2p +1)例5：解同余方程28x ≡21(mod 35)解：∵（28,35）=7|21，∴原同余方程有解，且有7个解原同余方程等价于4x ≡3(mod 5)而且4x ≡3(mod 5)解为x ≡2(mod 5)∴原同余方程解为2，7，12，17，22，27，31（mod 35）。
第三章同余1 同余的概念及其基本性质定义1 设m Z ，称之为模。
若用m去除两个整数a与b所得的余数相同，则称a, b对模m同余，记作： a b (mod m)；若所得的余数不同，则称a, b对模m不同余，记作： a b (mod m)。
例如，8 1 (mod 7)，；所有偶数 a 0 (mod 2)，所有奇数 a 1 (mod 2)。
同余是整数之间的一种关系，它具有下列性质：1、 a a (mod m)；(反身性)2、若a b (mod m)，则 b a (mod m)；(对称性)3、若 a b (mod m)， b c (mod m)，则 a c (mod m)；(传递性)故同余关系是等价关系。
定理1 整数a, b 对模m 同余的充分必要条件是m | (a b)，即a b mt，t Z。
证明设 a mq1 r1， b mq2r2，0 r1 , r2m，则 a b (mod m) r1 r2 a b m(q1 q2 ) m | (a b)。
性质1 (1) 若a1 b1 (mod m)，a2 b2 (mod m)，则a1a2 b1 b2 (mod m)；(2) 若a b c (mod m)，则 a c b (mod m)。
性质2 若a1 b1 (mod m)，a2b2(mod m)，则a1a2b1b2(modm)；特别地，若 a b (mod m)，则 k a kb (mod m)。
定理2 若 A 1 k B 1 k (mod m)， x i y i (mod m)， i 1,2, , k ，B 1 k y 1 1y k k(mod m)；特别地，若 a i b i (mod m)，1kn n1i 0,1,2,, n ，则a n x a n 1x性质3 若 a a 1d ， b b 1d ， (d , m) 1， a b (mod m)，则 a 1 b 1 (mod m)。
性质4 (1) 若 a b (mod m)， k 0，则 ak bk (mod mk)；(2) 若 a b (mod m)， d 是 a, b 及 m 的任一公因数，则a b(mod m )。
第三章同余例题分析
例1：求3406的末二位数。
解：∵（3，100）=1，∴3)100(φ≡1（mod 100）
φ(100)=φ(22·52)=40,∴340≡1(mol 100)
∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)
∴末二位数为29。
例2：证明（a+b ）p ≡a p +b p (mod p )
证：由费尔马小定理知对一切整数有：a p ≡a （p ），b p ≡b (P )，
由同余性质知有：a p +b p ≡a+b (p )
又由费尔马小定理有（a+b ）p ≡a+b (p )
（a+b ）p ≡a p +b p (p )
例3：设素数p >2，则2P -1的质因数一定是2pk +1形。
证：设q 是2p -1的质因数，由于2p -1为奇数，∴q ≠2，
∴（2·q ）=1,由条件q|2p -1,即2p ≡1（mod q ），又∵（q ,2）=1，2p ≡1（mod q ）设i 是使得2x ≡1（mod p ）成立最小正整数
若1<i <p ，则有i |p 则与p 为素数矛盾
∴i=p ,∴p |q -1
又∵q -1为偶数，2|q -1,
∴2p |q -1,q -1=2pk ,即q =2pk +1
例4：证明13|42n +1+3n +2
证：∵42n +1+3n +2≡4·16n +9·3n
≡3n (4+9)≡13×3n ·≡0(13)
∴13|42n +1+3n +2
例5：证明5y +3=x 2无解
证明：若5y +3=x 2有解，则两边关于模5同余
有5y +3≡x 2(mod 5)
即3≡x 2(mod 5)
而任一个平方数x 2≡0,1,4(mod 5)
∴30,1,4(mod 5)
∴即得矛盾，即5y +3=x 2无解
例6：求
50111......被7除的余数。
解：∵111111被7整除，∴ 50111......≡11（mod 7）≡4（mod 7），即余数为
4。
例7：把..0.04263化为分数。
解：设b =...360420，从而1000b=...3642,
100000b=...364263，99000b=4263-42b=990004221
==11000469。
当然也可用直化分数的方法做。
例8：设一个数为62XY427是9，11的倍数，求X ，Y
解：因为9|62XY427
所以9|6+2+X+Y+4+2+7，即9|21+X+Y
又因为11|62XY427，有11|（7+4+X+6-2-Y-2）
即11|（X-Y+13）
因为0≤X，Y ≤9，所以有21≤21+X+Y ≤39，
4≤X-Y+13≤22，由此可知
21+X+Y=27，X-Y+13=11
或21+X+Y=36，X-Y+13=22
X+Y=6，X-Y=-2
或X+Y=15，X-Y=9，解得X=2，Y=4。
例9：证明：8a+7不可能是三个整数的平方和。
证：由于每一个整数对于8，必同余于0，1，2，3，4，5，6，7这八个数之一
注意到对于模8，有
,002≡,112≡,422≡,
132≡,042≡,152≡,462≡,
172≡因而每一个整数对于模8，必同余于0，1，4这三个数
不能222,,z y x 如何变化，只能有)
8(mod 6,5,4,3,2,1,0222≡++z y x 而)8mod 778≡+a ，故78+a 不同余于222z y x ++关于模8
≠+78a 222z y x ++，从而证明了结论。
