初等数论 期末复习 同余精选例题分析

第二讲同余（数论复赛辅导）第二讲同余一.基础知识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。

【例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 ===。