当前位置：文档之家 › 同余

同余

  • 格式：pdf
  • 大小：202.25 KB
  • 文档页数：7

下载文档原格式

  / 7

合集下载

同余法解题完整版

同余法解题完整版

同余法解题集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。

同余的定义是这样的：两个整数，a,b,如果他们同时除以一个自然数m，所得的余数相同，则称a,b对于模m同余。

记作a≡b（mod.m）。

读作：a同余于b模m。

同余的性质也比较多，主要有以下一些：1..对于同一个除数，两个数的乘积与它们余数的乘积同余。

例如201×95的乘积对于除数7，与201÷7的余数5和95÷7的余数4的乘积20对于7同余。

2..对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。

例如519和399对于一个除数同余，那么这个除数一定是519与399的差的因数，即519与399的差一定能被这个除数整除。

3..对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。

例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余，当然余数大小随次方变化。

4．对于同一个除数，若三个数a≡b（mod m），b≡c（mod m），那么a,b,c三个数对于除数m都同余（传递性）例如60和76同余于模8，76和204同余于模8，那么60,76,204都同余于模8。

5. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么a±c≡c±d （mod m），（可加减性）6. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么ac≡cd（mod m），（可乘性）二、中国剩余定理解法一个数被3除余1，被4除余2，被5除余4，这个数最小是几？解法：求3个数：第一个：能同时被3和4整除，但除以5余4，即12X2＝24第二个：能同时被4和5整除，但除以3余1，即20X2＝40第三个：能同时被3和5整除，但除以4余2，即15x2＝30这3个数的最小公倍数为60，所以满足条件的最小数字为24＋40+30-60=3412X2＝24 20X2＝40 15x2＝30中2的来历。

同余的基本概念和性质

同余的基本概念和性质

模相等的同余关系的运算性质
模相等的同余关系满足交换律和结合律 模相等的同余关系满足消去律 模相等的同余关系满足分配律 模相等的同余关系满足幂等律
同余的应用
同余在模方程中的应用
模方程的同余解法 同余在模方程中的应用实例 同余在模方程中的求解步骤 同余在模方程中的优势与局限性
同余在数论中的应用
整除理论：同余是整除理论中的重要概念，用于研究整数之间的除法关系。
● - 同余关系具有反身性，即任意整数a都与自身对模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)。 ● - 对于任意整数a、b和c，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。
同余的性质
模相等的同余关系
● 定义：如果两个整数a和b除以同一个正整数m的余数相同，则称a和b对模m同余，记作 a≡b(mod m)。
● 性质： - 同余关系具有反身性，即任意整数a都与自身对模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)。 - 对于任意整数a、b和c，若a≡b(mod m)且 b≡c(mod m)，则a≡c(mod m)。
同余的基本概念和性质
汇报人：XX
目录
同余的定义
同余的性质
01
02
同余的应用
同余的证明方法
03
04
同余的定义
什么是同余
同余的定义：两个整数除以某 个固定整数得到的余数相同， 则称这两个整数同余。

同余

同余

可以理解为： 31除以4的余数是3 可以理解为： 50除以4的余数是18
求123+72的和除以10的余数
方法一：123+72=195
求121+74的和除以3的余数
方法一：121+74=195
求121-74的差除以3的余数
方法一：121-74=47
同余式定义和基本性质
若ab(mod m), cd(mod m), k为正整数 ①可加减性 和（差）的余数等于余数的和（差） 即a±c b±d(mod m), 特别地有a±k b±k(mod m). 同时有a-b 0（mod m） 显然：移项变号同样适用于同余式
【例7】若今天是星期六，从今天 102003天后的那一天是星期（ ）
10 3(mod7)
6
10
2003
3
2003
(mod7)
3 （ 1 mod7） 2003 6 333 5
10
2003
3 3
2003
5
5(mod7)
∴所求那天是星期四。
一次同余式组
• 本节介绍一次同余式组的解法及其应用举 例． • 在公元三世纪前,《孙子算经》里已提出了下 面的同余式组 xb1(mod m1), xb2(mod m2),…, xbk(mod mk) (1) • 这种形式的问题, 并且很好地解决了它.《孙子 算经》里所提出的问题之一如下: • “今有物不知其数, 三三数之剩二, 五五数之 剩三, 七七数之剩二. 问物几何？” “答日二 15:51:43 十三.”
一个数除以3余2，除以5余3，除以7余 2，求这个数。 被7除余2的数有：2，9，16，23
被5除余3的数有：3，8，13，18，23 被3除余2的数有：2，5，8，11，14，17 ，20，23

同余问题解析

同余问题解析

同余问题解析所谓同余问题，就是给出“一个数除以几个不同的数”的余数，反求这个数，称作同余问题。

一、“差同减差，和同加和，余同取余，最小公倍加倍”这是解较简单同余问题的口诀。

首先要对这几个不同的数的最小公倍数心中有数。

下面以4、5、6为例，请记住[4,5,6]=60。

1、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。

例：一个数除以4余1，除以5余2，除以6余3，求这个数。

因为4-1=5-2=6-3=3，所以取-3，表示为60k-3，k为非零自然数。

即：当k=1、2、3、4、5…时都满足60k-3≡1（mod 4），60k-3≡2（mod,5），60k-3≡3（mod 6）。

2、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。

例：一个数除以4余3，除以5余2，除以6余1，求这个数。

因为4+3=5+2=6+1=7，所以取+7，表示为60k+7，k为非零自然数。

即：当k=1、2、3、4、5…时都满足60k+7≡3（mod 4），60k+7≡2（mod 5），60k+7≡1（mod 6）。

3、余同取余：用一个数除以几个不同的数，得到的余数相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的余数，称为：“余同取余”。

例：一个数除以4余1，除以5余1，除以6余1，求这个数。

因为余数都是1，所以取+1，表示为60k+1，k为非零自然数。

60k+1≡1（mod 4），60k+1≡1（mod 5），60k+1≡1（mod 6）。

4、最小公倍加倍：用一个数除以几个不同的数，得到的余数为0，此时反求的这个数，可以选这几个不同的数的最小公倍数的倍数，称为：“最小公倍加”，也称为：“公倍数作周期”例：一个数被4、5、6整除，求这个数。

同余的概念与性质

同余的概念与性质

同余的概念与性质同余：设m 是大于1的正整数，若用m 去除整数b a ,，所得余数相同，则称a 与b 关于模m 同余，记作)(mod m b a ≡，读作a 同余b 模m ；否则称a 与b 关于模m 不同余记作)(mod m b a ≠。

性质1：)(mod m b a ≡的充要条件是Z t mt b a ∈+=,，也即)(|b a m -。

性质2：同余关系满足下列规律：（1）自反律：对任何模m 都有)(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 ≡。

性质 3:若,,,2,1),(mod s i m b a i i =≡则).(mod ),(mod 21212121m b b b a a a m b b b a a a s s s s ≡+++≡++推论： 设k 是整数，n 是正整数，（1）若)(mod m c b a ≡+，则)(mod m b c a -≡。

（2）若)(mod m b a ≡，则)(mod m a mk a ≡+；)(mod m bk ak ≡；)(mod m b a n n ≡。

性质4：设)(x f 是系数全为整数的多项式，若)(mod m b a ≡，则 ))(mod ()(m b f a f ≡。

性质5：若)(mod m bd ad ≡，且1),(=m d ，则)(mod m b a ≡。

性质6：若)(mod m b a ≡，且m d b d a d |,|,|，则)(mod d m d b d a ≡。

性质7：若)(mod m b a ≡，且m m |1，则)(mod 1m b a ≡。

性质8：若)(mod i m b a ≡，s i ,,2,1 =，则]),,,(mod[21s m m m b a ≡这里],,,[21s m m m 表示s m m m ,,,21 的最小公倍数。

同余的基本概念和性质

同余的基本概念和性质
4 16，28 256，216 154，232 1 (mod 641)。
例3 说明 是否被641整除。
因此 0 (mod 641)，
即641 。
第一节 同余的基本性质
第一节 同余的基本性质
设式(4)对于n = k成立，则有 1 (mod 2k + 2) = 1 q2k + 2， 其中qZ，所以
=(1 q2k + 2)2=1 q 2k + 31(mod 2k + 3)， 其中q 是某个整数。这说明式(4)当n = k 1也成立。 由归纳法知式(4)对所有正整数n成立。
第一节 同余的基本性质
a2 1 (mod p) pa2 1 = (a 1)(a 1)，
证明 由
pa 1或pa 1，
所以必是
a 1或a 1 (mod p)。
例8 设p是素数，a是整数，则由a2 1(mod p)可以推出
即a 1 (mod p)或a 1 (mod p)。
解 因为792 = 8911，故 792n 8n，9n及11n。 我们有 8n 8 z = 6，
证明 留作习题。
定理5 下面的结论成立： (ⅰ) a b (mod m), dm, d>0 a b (mod d); (ⅱ) a b (mod m), k > 0, kN ak bk (mod mk)； (ⅲ) a b (mod mi )，1 i k a b (mod [m1, m2, , mk])； (ⅳ) a b (mod m) (a, m) = (b, m)； (ⅴ) ac bc(modm), (c, m) =1 a b (mod m).
定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为 a b (mod m)， 此时也称b是a对模m的同余

数论中的整除与同余概念

数论中的整除与同余概念整除和同余是数论中的重要概念。

整除指的是一个数被另一个数整除，也就是能够整除有余数为零的关系。

同余则是指两个数除以同一个数所得的余数相等。

这两个概念在数论中有着广泛的应用和深入的研究。

首先，我们来讨论整除的概念。

设a和b是两个整数，如果存在一个整数c，使得b=c*a，我们就说a整除b，记作a|b。

即b能够被 a 整除而没有余数。

整除是一个基本的数学运算，我们通过它可以判断两个数的倍数关系。

例如，如果a|b且a|c，那么我们可以得到a|(b+c)和a|(b-c)。

这是因为有整数d和e，使得b=d*a，c=e*a。

那么b+c=(d+e)*a，b-c=(d-e)*a，它们都可以被a整除。

正是因为整除的这些性质，我们能够通过对整数的整除关系进行研究，揭示整数之间的规律。

整除在数论中扮演着重要的角色，例如在质数的研究中，整除是一个关键概念。

质数指的是除了1和自身外没有其他因数的数，也就是只能被1和自身整除的数。

例如，2、3、5、7等都是质数。

对于一个数n，我们可以通过判断是否有除了1和n外的其他因数来判断n是否为质数。

这个思想就是质数检验的基础。

接下来，我们来深入讨论同余的概念。

给定两个整数a和b，如果它们除以一个正整数m所得的余数相等，即(a-b)能被m整除，我们就说a与b对模m同余，记作a≡b(mod m)。

同余关系是模m下的一种等价关系，也就是说它满足以下性质：1. 自反性：对于任意的整数a，a≡a(mod m)。

2. 对称性：对于任意的整数a和b，如果a≡b(mod m)，那么b≡a(mod m)。

3. 传递性：对于任意的整数a、b和c，如果a≡b(mod m)且b≡c(mod m)，那么a≡c(mod m)。

同余关系的一个重要应用是在时钟和日历的计算中。

例如，我们常使用12小时制的时钟，它的小时数是以0到11表示的。

那么如果现在是下午8点，过了6个小时后是几点呢？我们可以通过同余的概念来解决这个问题。

第36讲 同 余

第 17 讲 同 余同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一。

设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a 与b 对模同余，记作)(mod m b a ≡，否则，就说a 与b 对模m 不 同余，记作)(mod m b a ≡，显然，)(|)(,)(mod b a m Z k b km a m b a -⇔∈+=⇔≡；1、 同余是一种等价关系，即有自反性、对称性、传递性1).反身性：)(mod m a a ≡；2).对称性：)(mod )(mod m a b m b a ≡⇔≡；3). 传递性：若)(mod m b a ≡，)(mod m c b ≡则)(mod m c a ≡;2、加、减、乘、乘方运算若 a b ≡（mod m ） c d ≡（mod m ）则 a c b d ±≡±（mod m ），ac bd ≡（mod m ），n na b ≡（mod m ） 3、除法 设 ac bd ≡（mod m ）则 a b ≡（mod (,)m c m ）。

A 类例题例1．证明： 一个数的各位数字的和被9除的余数等于这个数被9除的余数。

分析 20≡2(mod9)，500≡5(mod9)，7000≡7(mod9)，……，由于10n－1=9M ，则10n ≡1(mod9)，故a n ×10n ≡a n (mod9)。

可以考虑把此数变为多项式表示a n ×10n + a n-1×10n-1+…+ a 1×10+a 0后处理。

证明 设a=110n n a a a a =a n ×10n + a n-1×10n-1+…+ a 1×10+a 0，∵10≡1(mod9)，∴10n ≡1(mod9)，∴a n ×10n + a n-1×10n-1+…+ a 1×10+a 0≡a n + a n-1+…+ a 1+a 0。

同余


a 用a modm表示余数r，则 a [ ]m ( a m odm ) m
定理3 整数a, b模m 同余 a modm=b modm
ab (modm) m|a-b a modm=b modm
a=b+km
性质：
(1) ( 2) ( 3)
[(a modm ) (b modm )]modm (a b) modm [(a modm ) (b modm )]modm (a b) modm [(a modm ) (b modm )]modm (a b) modm
(r r ) a b (q q)m
m a b的充分必要条件是 m r r. 但因为 0 r r m ， 因此，
且 m r r 的充分必要条件是 r r 0 ，所以 m a b 的充分必 要条件是 r r 0. 这就是定理的结论.
2
2003
2

22 1 4 4(mod 7).
故第 22003 天是星期二。 定理5 若 x y(mod m),
ai bi (mod m),
0 i k, 则 0 i k.
a0 a1 x ak x k b0 b1 y bk yk (mod m).
故 3 n, 9 ｜ n.
k 定理7 设 n ak 1000 a11000 a0 , 0 ai 1000. 则7或11,或
13 n 7或11或 13 a0 a2 - a1 a3 .
例4 设 n 637693.
例5 设n 75312289.
定理10 设a b ( mod m) . 若d | m, 则a b ( mod d) .

同余的运算法则

同余的运算法则全文共四篇示例，供读者参考第一篇示例：同余的概念最早出现在数论领域，是一种描述整数间的模运算关系的数学概念。

同余的运算法则涉及到模运算的一系列性质和规律，对于解决一些数论问题和密码学中的加密算法起着至关重要的作用。

本文将介绍同余的概念及其运算法则，并讨论其在数学和应用方面的重要性。

1. 同余的定义在数论中，我们通常使用符号“≡”表示同余关系。

如果两个整数a和b除以一个正整数m的余数相等，即a除以m和b除以m的余数相等，我们就说a与b关于模m同余，记为a≡b(mod m)。

简单来说，同余就是指两个数除以同一个数的余数相等。

12和22关于模5同余，因为12除以5的余数为2，22除以5的余数也为2，即12≡22(mod 5)。

2. 同余的运算法则在模运算中，同余有着一系列的运算法则。

我们可以根据这些法则来简化模运算的计算，并处理一些复杂的数论问题。

（1）同余的传递性如果a≡b(mod m)且b≡c(mod m)，那么可以推出a≡c(mod m)。

这就是同余关系的传递性，即如果两个数与同一个模同余，那么它们之间也是同余的。

举例来说，如果5≡15(mod 10)且15≡25(mod 10)，那么可以推出5≡25(mod 10)。

（2）同余的对称性和反对称性（3）同余的加法和乘法性质对于同余关系来说，加法和乘法都具有良好的性质。

（4）同余的幂运算性质如果a≡b(mod m)，那么对于任意正整数n，有a^n≡b^n(mod m)。

即同余数的幂运算后依然同余。

（5）同余的逆元如果a在模m下存在逆元，即存在整数b使得ab≡1(mod m)，那么我们称b是a的逆元。

对于素数模m来说，任意整数a在模m下都有逆元。

同余的概念在数论和密码学领域有着广泛的应用。

（1）同余在数论中的应用在数论中，同余可以用来证明一些整数性质和解决一些数论问题。

在证明费马小定理和欧拉定理等定理时就会用到同余的性质。

在密码学中，同余的概念有着重要的应用。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。


。
同余类：由关于模 m 同余的数组成的集合，每一个集合叫做关于模 m 的同余类（或者 叫做关于模 m 的剩余类） 。由于任何整数模 m 的余数只有 0,1,2, , m 1 这 m 种，所 以 可 以 将 所 有 整 数 按 照 模 m 的 余 数 分 成 m 个 子 集 ： A0 , A1 , , Am 1 。 其 中
10. （ 2005 年克罗地亚数学奥林匹克） 已知 99 个小于 100 且可以相等的正整数。 若所有 2 个， 3 个，或者更多数的和都不能被 100 整除，求证：所有的数均相等。 证明：设给定的数为 n1 , n 2 , , n99 ，反证，若存在两数 n1 n2 ，考察下面 100 个数：
mn 1(mod 5) ，即 5 | mn 1 ，设 A am 3 bm 2 cm d , B dn 3 cn 2 bn a
则 An 3 B ( mn 1)[a ( m 2 n 2 mn 1) bn( mn 1) cn 2 ] ，所以 5 | An 3 B ，由 于 5 | A ，所以 5 | B 。 5. 连续写出 19 至 80 的两位数，所得到的数： 19202122 787980 能否被 1980 整除？
2
2.
解： 2007 3 223 ，∵ n 为正奇数，∴ 116 n a 107 n a 1107 n mod 223 。 ∴ 223 | a 1 107 ，∴ 223 | a 1 ，令 a 1 223k 。
n
又∵ 116 a 107 1 a 1 a 1mod 9 ，
a 0 , a 1 , , a m 1 叫做模 m 的一个完全剩余系。
5. 若 k , m 1 ，a 0 , a 1 , , a m 1 是模 m 的一个完全剩余系，则 ka 0 b, ka 1 b ，……，
ka m 1 b 也是模 m 的一个完全剩余系。
【利用同余解决整除问题】 1. 求最大的正整数 n ，使得 2 n | 31024 1
| n 1。 显然 a i a i 1 ∥ a j a j 1 a i a i 1 a j a j 1 (mod n) ，若 n 为偶数，则 2
所以模 n 完系的和为：
n1 n 1 i
n( n 1) 0(mod n) ， 2
n 1 n1 i 0 i 0
S 1 n1 , S 2 n2 , S 3 n1 n2 , , S 100 n1 n2 n99 ，由于其中没有一个 100 的倍
数，所以必有 i , j ( i j , ( i , j ) ( 2,1)) ，使得 S i S j (mod 100) ，所以 100 | S i S j ，矛 盾。 11. （第 57 届俄罗斯数学奥林匹克-改）将 2013 个正整数放在一个圆周上，使得任意相邻 的 5 个数中有 3 个数的和等于另两个数的和的 2 倍。求证：这 2013 个数都是 0 . 证明：设这些数为 a1 , a 2 , , a 2013 ，对于任意相邻的五个数 a i , a i 1 , a i 2 , a i 3 , a i 4 ，有：
12. （ IMO 30 预选） 连接正 n 边形的顶点， 获得一个闭的 n 折线， 求证： 若 n 为偶数， 则在连线中有两条平行线；若 n 为奇数，连线中不可能恰有两条平行线。 证明：依逆时针顺序将正 n 边形的顶点上标上 0,1,2, , n 1 。 则连接顺序即为 0,1,2, , n 1 的一个排列，用 a 0 , a 1 , a n1 表示。
2.同余
【知识点】 1. 定义：设 m 为正整数，若整数 a , b 被 m 除所得余数相同，则称 a 和 b 对模 m 同余，记 作 a b(mod m ) ； a b(mod m ) n | a b 。 2. 性质： （1）若 a b(mod m ) ， c d (mod m ) ，则 a c b d (mod m ) 。 （2）若 a b(mod m ) ， c d (mod m ) ，则 ac bd (mod m ) 。
6.
用数码 1,2,3,4,5,6,7 作一个七位数，每个数码只用一次，求证：这些七位数中没有一个 是另一个的倍数。
证明：假设有这样两个七位数 a, b ，存在大于 1 的整数 c，使得 a bc 成立。 由于 a b 1 2 3 4 5 6 7 1(mod 9) 所以 c 1(mod 9) 由于 c 1 所以 c 10 。 a 不是七位数，矛盾。 7. 求在小于 10000 的正整数中，有多少个整数 x ，可使 2 x 能被 7 整除。
而
(a
i 0
所以 a i a i 1 a i 1 ) a i a i 1 2 a i n( n 1) 0(mod n) ，
i 0
不 能 构 成 模 n 的 一 个 完 系 。 所 以 必 有 i j(0 i , j n 1 ， 使 得
i n 2i mod m ，两式相减： m | 2 n 1 i n ，因为 m ,2 n 1 1 ，
1024
解： 3
1 3512 1 3512 1 3512 1 3 256 1 3 2 1 3 13 1







当 k 时偶数时，3 k 1 2mod 4 ，∴除了 3 1 4 含有 2 个 2 外，其他 10 项都只有 1 个 2 ，∴ n 的最大值为 12 。 求最小的正整数 a ，使得存在正奇数 n ，满足 2007 | 116 n a 107 n 。
所以对于任意的 i , j 有 a i a j (mod 3) 。由于
a i a i 1 a i 2 a i 3 a i 4 5a i 0(mod 3) a 所以 a i 0(mod 3) 。设 bi i ，则 bi 满足条件，且严格小于 a i ，由无穷递降法， 3 知 a i 0( i 1,2,3, ,2013) 。
a i a i 1 a j a j 1 (mod n) 。即存在平行线： a i a i 1 ∥ a j a j 1 。
若 n 为奇数，且恰有一对边平行，此时 a i a i 1 ( i 0,1, n 1) 恰有一个剩余类 r
n 1 n 1
出现了两次，恰少一个剩余类 s 。由 2 | n 1 ，得： 而 r s(mod n) ，矛盾。
n n
n
n
∵ a 1 223k ，∴ a 1 223k 2 7 k 2mod 9 ， 最小的 a ，当 k 1 时，满足题意， a min 224 。
3.
对任意自然数 n， 求证：S n 1 2 3 4 ,当且仅当 n 不是 4 的倍数时， 被 5 整除。
x 2
8.
一个立方体的顶点标上数 1 或者 1 ， 面上标一个数， 它等于这个面四个顶点处的数的 乘积。求证：这样标出的 14 个数之和不等于 0.
证明：记原来这 14 个数的和为 S。现在进行如下操作：变动顶点处的一个 1 到 1 ，则变 动了这个数后，S 中有 4 个数的符号会发生改变，记这改变的四个数为 a, b, c, d ，改变后的 和为 S ` 则： a b c d 0(mod 2) 。所以 S S ` 2( a b c d ) 0(mod 4) ，即改变 前后两和对 4 同余。重复进行如此操作，直至所有顶点处标的都是+1，则
（3）若 ac bc (mod m ) ，则 a b mod

m 。 m, c
（4）若 a b(mod m ) ， d | m ，则 a b(mod d ) 。 （5）若 a b(mod m ) ， d 0 ，则 da db(mod dm ) 。 （6）若 a b(mod m i ) ，其中 i 1,2,3, , k ，则 a bmod m 1 , m 2 , , m k 3.
a i a i 1 0(mod n) 从
i 0 i 0 m
13. 设 m 、 n 为正整数， m 为奇数，且 m ,2 n 1 1 ，求证： m |


i
i 1
n
。
证明：显然 1,2, , m 是模 m 的一个完系，则 2 1, ,2 m 也是模 m 的一个完系，所以
|d。 证明：若 5 | m ，则 5 | d ，矛盾。所以 5
设 m 5k r , r 1,2,3,4 ，由于 1 1 1(mod 5),2 3 1(mod 5),4 4 1(mod 5) ，当
m 取 5k 1,5k ,2,5k 3,5k 4 时，取相应的 n 为 5t 1,5t 3,5t 2,5t 4 则
0 a i a i 1 a i 2 a i 3 a i 4 a i 1 a i 2 a i 3 a i 4 a i 5 (mod 3) ，所以 a i a i 5 (mod 3) 其中当 j k (mod 2013) 时，有 a j a k ，由于 5,2013 1 ，
S 1 1 1 1 14 2(mod 4) ，所以 S 0 。
【构造法、抽屉原理、剩余系】 9. 求证对任意一个正整数，都存在一个它的倍数，这个数包含全部 10 个阿拉伯数字。
k
k
证一： 设 p 1234567890 10 ，n 为给定整数，k 使得 10 n ， 则 p 1, p 2, p n 是模 n 的一个完系，必有一个是 n 的倍数。 证二：令 a 1234567890 ，则 a , a a , , a a a a （共 n 1 个）必有两个模 n 同余，则这 两数之差是 n 的倍数，且包含所有阿拉伯数字。