初等数论§3同余

初等数论同余方程组初等数论是数学中的一个分支，主要研究自然数的性质和整数的性质。

同余方程组是初等数论中的一个重要概念，它涉及到数与数之间的整除关系。

本文将介绍同余方程组的定义、性质以及解法，并通过例题来加深理解。

一、同余方程组的定义同余方程组是由若干个同余方程组成的一组方程。

同余方程的定义如下：对于整数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章（同余方程）第 3 章同余方程（一）内容：● 同余方程概念● 解同余方程● 解同余方程组（二）重点● 解同余方程（三）应用● 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1）同余方程【定义3.1.1】（定义1）设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--Λ其中i a 是正整数（n a ≠0（mod m ）），则f (x)≡0（mod m ）（1）叫做模m 的（n 次）同余式（或模m 的（n 次）同余方程），n 叫做f(x)的次数，记为deg f 。

（2）同余方程的解若整数a 使得f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。

（3）同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。

即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。

故把这些解都看做是相同的，并说剩余类a C 是同余方程(1)的一个解，这个解通常记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程(2)的不同的解，所有对模m 的两两不同余的解的个数，称为是同余方程（1）的解数，记作()m f T ;。

显然()m f T ;≤m（4）同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数()m f T ;。

【例1】（例1）可以验证，x ≡2，4（mod 7）是同余方程15++x x ≡0（mod 7）的不同的解，故该方程的解数为2。

50＋0＋1＝1≡3 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。

第三讲：初等数论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 ===。

同余关系的概念与定理同余关系是离散数学中一个重要的概念，它在数论、代数和密码学等领域有着广泛的应用。

本文将介绍同余关系的概念和相关定理。

一、同余关系的概念同余关系是数论中的一个基本概念，它描述了两个数之间的整除关系。

具体来说，给定两个整数a和b，如果它们除以一个正整数m所得的余数相同，即a和b对m同余，记作a≡b(mod m)，则称a和b关于模m同余。

二、同余关系的性质同余关系具有以下三个性质：1.自反性：对于任意整数a，a≡a(mod m)恒成立。

即任意整数与自身关于模m同余。

2.对称性：对于任意整数a和b，若a≡b(mod m)，则b≡a(mod m)。

即若a与b关于模m同余，则b与a关于模m同余。

3.传递性：对于任意整数a、b和c，若a≡b(mod m)且b≡c(mod m)，则a≡c(mod m)。

即若a与b关于模m同余，且b与c关于模m同余，则a与c关于模m同余。

三、同余关系的定理1. 除法定理：对于任意整数a和正整数m，存在唯一的整数q和r，使得a=qm+r，其中0≤r<m。

即任意整数a可以表示为以m为模的除法形式。

2. 模运算性质：- 同余类的性质：对于任意整数a和正整数m，a关于模m的同余类可以表示为[a]m={b∈Z | b≡a(mod m)}，其中Z表示整数集合。

同余类[a]m是所有与a关于模m同余的整数构成的集合。

- 同余的运算性质：对于任意整数a、b和正整数m，若a≡a' (mod m)且b≡b' (mod m)，则有a+b≡a'+b' (mod m)，a-b≡a'-b' (mod m)，ab≡a'b' (mod m)。

3. 唯一性定理：对于给定的整数a、b和正整数m，存在整数x，使得a≡b (mod m)的充分必要条件是a和b对m的余数相同。

即a和b关于模m同余的充分必要条件是它们对m的余数相同。

4. 同余定理：对于任意整数a、b和正整数m，若a≡b (mod m)，则a^n≡b^n (mod m)，其中n是正整数。

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

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

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

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设meZ\称之为模。

若用加去除两个整数“与b所得的余数相同，则称"上对模加【可余，记作：a = b (mod /n)；若所得的余数不同，则称w,〃对模加不同余，记作："圭b(mod〃2)。

例如，8 = 1 (mod 7),:所有偶数“三0 (mod 2),所有奇数“ =1 (mod 2)。

同余是整数之间的一种关系，它具有下列性质：R a = a (mod m)；(反身性)2、若"三b (mod加)，贝肪三a (mod m)；(对称性)3、若"三b (mod m), b = c (mod m),贝h 三 c (mod 加);(传递性) 故同余关系是等价关系。

定理1整数对模加同余的充分必要条件是RP a = b + mt,r eZo证明设"=+ b = mq2 + r v 0 < r2 < m,贝l] a = b (mod m) O 打=r2 O a — b = m(q{一⑴)O I (" 一b)°性质1(1)若％三S (mod m)> a2 = b2 (mod m)> 则a x + a2 +b2 (mod /n)；(2)若"+ h = c (mod 〃?)，贝ij a = c-b (mod m)o性质2 若=/?, (mod /??), a2 =b2 (mod m),则"]5 "心(mod m)：特别地，若a = b (mod m),则畑三kb (mod加)。

定理2若比…亞三〃叶・％(mod/),兀三片(mod皿)，j = 1,2,…人则艺比…致坊‘…場三另3时灼)吓…yj (mod/)；特别地,若％三化(mod加),i = OJ2・・・，n，则心* +"心]北1 + - - +u()=b n x n +/>n_|x71'1 + …+ "o (mod 加)。

千里之行，始于足下。

同余问题学问点讲解同余问题是数论中的一个重要概念，它在数学中有着广泛的应用。

同余问题的定义是：对于给定的整数a、b和正整数m，假如a-b能够被m整除，则称a与b对于模m同余，记作a≡b(mod m)。

同余问题的本质是数的剩余，即两个数除以某个正整数得到的余数相等。

通过同余问题的争辩，可以得到一些有关数的性质和关系。

同余问题有一些基本性质：1. 若a≡b (mod m) ，则对于任意的正整数k，有 a+k*m≡b+k*m (mod m) ，即同余关系对加法成立。

2. 若a≡b (mod m) ，则对于任意的正整数k，有 a*k≡b*k (mod m) ，即同余关系对乘法成立。

3. 若a≡b (mod m) ，且b≡c (mod m) ，则 a≡c (mod m) ，即同余关系对传递成立。

4. 若a≡b (mod m) ，则 a^n ≡ b^n (mod m) ，即同余关系对幂运算成立。

基于同余性质，我们可以进行一系列的运算和推导。

首先，同余问题可以用来简化计算。

例如，对于不便利计算的大数，可以通过取模运算将其转化为较小的数进行计算，而不转变其同余关系。

第1页/共2页锲而不舍，金石可镂。

同余问题还可以用来求解方程。

例如，对于形如ax≡b (mod m) 的方程，可以通过同余性质进行变形和推导，得到方程的解。

同余问题在密码学中也有重要应用。

例如，RSA算法中的模运算就是基于同余问题的。

同余问题还可以用来进行数字签名和数据加密等操作。

同余问题还与模运算有亲密的关系。

模运算是将一个数除以另一个数得到的余数，而同余问题是比较两个数的余数是否相等。

通过同余问题，可以推导出一些模运算的性质和规章。

最终，同余问题还有一些重要的定理，如中国剩余定理、费马小定理等。

这些定理在数论和密码学中有广泛的应用。

总结起来，同余问题是数论中的一个基本概念，它争辩的是两个数取模后的余数是否相等。

通过同余问题的争辩，可以推导出一些有关数的性质和关系，用来简化计算、求解方程、进行密码学操作等。

数论中的同余关系数论作为数学的一个分支，研究的是整数及其性质。

其中，同余关系是数论中一个重要的概念。

本文将就数论中的同余关系进行探讨，以便深入理解这一概念。

1. 引言在数论中，同余是指两个整数除以一个给定的正整数所得的余数相等。

形式化定义为：对于整数a、b和正整数m，如果m|(a-b)，即m能被a-b整除，那么就称a与b对模m同余，记作a≡b(mod m)，读作“a 同余于b模m”。

同余关系具有如下性质：(1) 自反性：对于任意整数a和正整数m，a≡a(mod m)；(2) 对称性：对于任意整数a、b和正整数m，如果a≡b(mod m)，那么b≡a(mod m)；(3) 传递性：对于任意整数a、b、c和正整数m，如果a≡b(mod m)且b≡c(mod m)，那么a≡c(mod m)。

2. 同余关系的性质同余关系具有一些重要的性质，这些性质对于解决数论问题非常有用。

(1) 同余的基本性质：- 同余关系是等价关系。

即满足自反性、对称性和传递性。

- 设a≡b(mod m)，那么对于任意的整数k，a+km≡b(mod m)。

- 设a≡b(mod m)，c≡d(mod m)，那么a+c≡b+d(mod m)和ac≡bd(mod m)。

(2) 同余的运算性质：- 加法性质：设a≡b(mod m)，c≡d(mod m)，那么a+c≡b+d(mod m)。

- 减法性质：设a≡b(mod m)，c≡d(mod m)，那么a-c≡b-d(mod m)。

- 乘法性质：设a≡b(mod m)，c≡d(mod m)，那么ac≡bd(mod m)。

(3) 欧拉定理：欧拉定理是数论中的一个重要结果，描述了同余关系与指数运算之间的关系。

- 设a和m是两个互质的正整数，那么a^φ(m) ≡ 1(mod m)，其中φ(m)表示小于m且与m互质的正整数的个数。

3. 同余方程同余关系在解决某些问题时，经常涉及到同余方程的求解。

同余方程是指形如ax ≡ b(mod m)的方程，其中a、b和m都是整数，求解的目标是找到整数x满足这个方程。

第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．。

第三章同余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 )。