初中数学竞赛讲座——数论部分8(同余系的应用)

华杯赛数论专题：余数及同余一、带余除法的定义：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q…r，也就是a＝b×q＋r, 0≤r＜b；我们称上面的除法算式为一个带余除法算式.这里：（1）当时：我们称a可以被b整除，记作b|a，q称为a除以b的商或完全商（2）当时：我们称a不可以被b整除，记作，q称为a除以b的商或不完全商二、同余的概念两个整数被同一个大于1的整数m除，所得的余数相同，就说这两个整数对于除数m来说是同余的.也可以换句话来说这个概念，如果两个整数的差能被大于1的整数m整除，那么这两个整数对于除数m来说是同余的.同余的概念和符号都是德国伟大数学家高斯引进的.一般地，两个整数a和b，除以大于1的正整数m，如果所得的余数相同，就说a、b对于模m同余，记作a≡b（mod m）.由于一个整数被m除的余数只能是0、1、2、3、…、m-1这m个数，所以全体整数可按被m除的余数分类，凡是余数相同的归为一类，全体整数就被划分成了m类，同一类中的任何两数被m除的余数都相等，即同一类中任何两数的差都能被m整除，不同类的任何两数被m除的余数都不相等.三、同余的性质1.如果a≡b（mod m），那么m|（a-b）；如果整数a和b对于模m是同余的，那么a 与b的差能被m整除.2.a≡a（mod m），即任何整数都与自身同余.3.若a≡b（mod m），则b≡a（mod m）.4.若a≡b（mod m），b≡c（mod m），则a≡c（mod m）.5.若a≡b（mod m），c≡d（mod m），则a+c≡b+d （mod m），a－c≡b－d （mod m），a×c≡b×d （mod m）.6.若a≡b（mod m），则an≡bn（mod m）。

（其中n为正整数）.例1.用一个两位数除708，余数为43，求这个两位数.【答案】95【解答】根据被除数-余数=商×除数，可知，所求两位数一定是707-43=665的大于43的约数，所以所求的两位数是95.例2.数713、1103、830、947被一个数除所得余数相同（余数不为0），求这个除数.【答案】39，13或3.【解答】1103－713=390=3×13×2×5，947－830=117=3×13×3，1103－947=156=2×13×3×2，除数为39，13或3.例3.从1、2、…100中最多能选出多少个数，使选出的数中每两个的和都不能被3整除？【答案】35【解答】1、2、…100中，除以3余1的数共34个，即1、4、7、10、…、100.除以3余2的数共33个，选出的数中，如果有除以3余1的，就一定不能有除以3余2的；如果有除以3余2的，也就不能有除以3余1的。

初中数学竞赛讲座——数论部分9（费马⼩定理）第9讲费尔马⼩定理⼀、基础知识：法国数学家费尔马在1640年提出了⼀个有关整数幂余数的定理，在解决许多关于某个整数幂除以某个整数的余数问题时⾮常⽅便有⽤，在介绍这个定理之前，我们先来看⼀些具体的同余式，请同学们注意观察，发现这些同余式符合什么规律．3≡1（mod 2），5≡1（mod 2），7≡1（mod 2）…22≡1（mod 3），42≡1（mod 3），52≡1（mod 3）…24≡1（mod 5），34≡1（mod 5），44≡1（mod 5）…26≡（23）2≡1（mod 7），36≡（33）2≡1（mod 7），46≡（43）2≡1（mod 7）…这些同余式都符合同⼀个规律，这个规律就是费尔马⼩定理．费尔马⼩定理：如果p是质数，（a，p）=1，那么a p－1≡1（mod p）与费马⼩定理相关的有⼀个中国猜想，这个猜想是中国数学家提出来的，其内容为：当且仅当2p-1≡1(mod p)，p是⼀个质数。

假如p是⼀个质数的话，则2p-1≡1(mod p)成⽴（这是费马⼩定理的⼀个特殊情况）是对的。

但反过来，假如2p-1≡1(mod p)成⽴那么p是⼀个质数是不成⽴的（⽐如341符合上述条件但不是⼀个质数）。

如上所述，中国猜测只有⼀半是正确的，符合中国猜测但不是质数的数被称为“伪质数”。

对于中国猜测稍作改动，即得到判断⼀个数是否为质数的⼀个⽅法：如果对于任意满⾜1 < b< p的b下式都成⽴：b p-1≡1(mod p)，则p必定是⼀个质数。

实际上，没有必要测试所有的⼩于p的⾃然数，只要测试所有的⼩于p的质数就可以了。

这个算法的缺点是它⾮常慢，运算率⾼；但是它很适合在计算机上⾯运⾏程序进⾏验算⼀个数是否是质数。

（⼀）准备知识：引理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,a1,a2,a3,a4,…a m为m个整数，若在这m个数中任取2个整数对m不同余，则这m个整数对m构成完全剩余系。

225 ≡5 ≡- 636 (mod 641)
Ζ 29 ≡- 129 ≡512 = 29 (mod 641) .
证明 :由 29 ≡512 ≡- 129 (mod 641) ,则
211 ≡- 516 ≡125 (mod 641)
Ζ 213 ≡500 ≡- 141 (mod 641)
Ζ 215 ≡- 564 ≡77 (mod 641)
(1) m | ( a - b) ; (2) 存在整数 k ,使得 a - b = mk . 性质 2 若 a ≡x (mod m) , b ≡y (mod m) , 则 a + b ≡x + y (mod m) , ab ≡xy (mod m) ; 若 a ≡b (mod m) ,则 ak ≡bk (mod m) ; 更一般地 ,若 ai ≡bi (mod m) , x ≡y (mod m) , 则 ak xk + ak - 1 xk - 1 + …+ a1 x + a0 ≡bk yk + bk - 1 yk - 1 + …+ b1 y + b0 (mod m) . 性质 3 (1) 若 ac ≡bc (mod m) ,则
≡0
,1 ,3 (mod
5) .
这表明 ,棋子永远不能到达编号为 2 、4
的方格.
又第一次移动后到达方格 1 中 ,第二次
移动后到达方格 3 中 ,第四次移动后到达方
格 0 中 ,则棋子在移动过程中能到达编号为
0 、1 、3 的三个方格中.
2. 3 质数的判定
对于指数形式的数 ,或是用含有字母的
式子表示的数 ,判断其是否为质数 ,可选择适
4
对任何正整数 n ,设 n ≡r (mod 5) (0 ≤r

同余理论在数学竞赛中的运用同余理论是数论中的一个重要分支，是指两个整数间差是一些给定的模数的倍数。

同余理论在数学竞赛中的运用非常广泛，无论是解题方法还是抽象思维训练都有涉及。

首先，同余理论可以用于解决一类问题，即同余方程问题。

同余方程是指一个未知数与模数之间具有其中一种特定关系的方程。

在数学竞赛中，我们经常会遇到需要求解同余方程的问题。

通过应用同余理论，可以利用模数的性质，简化问题的计算过程，从而较快地得到解。

举一个例子，假设一个问题是求解方程7x ≡ 6 (mod 5) 的整数解。

这个问题可以通过同余理论快速解决。

首先，我们可以观察到7 ≡ 2 (mod 5)。

因此，方程可以变形为2x ≡ 6 (mod 5)。

接下来，我们可以计算出 2 的逆元，即找到一个整数 a，满足2a ≡ 1 (mod 5)。

通过观察，我们可以发现 a = 3 是满足此条件的整数。

因此，将方程两边同时乘以 3，得到6x ≡ 18 (mod 5)。

再简化一步，可以得到x ≡ 3 (mod 5)。

因此，方程的整数解为 x = 3 + 5k，其中 k 是任意整数。

除了解同余方程的问题，同余理论还可以应用于解决循环问题。

在数学竞赛中，我们常常会遇到需要求循环节或重复周期的问题。

通过使用同余理论，我们可以很方便地进行分析和计算。

举一个例子，假设一个问题是求证序列{1^2, 2^2, 3^2, …,(p−1)^2} 在模 p 下的循环节长度。

首先，我们可以利用模数的性质，观察到对于任意整数 a 和 m，(a+m)^2 ≡ a^2 (mod m)。

因此，在这个问题中，我们只需要分析序列的前 p 个项即可。

进一步观察，我们可以发现p^2 ≡ 0 (mod p)，因此 p^2 不在序列中。

又因为 p-1 是模 p 的逆元，所以 (p-1)^2 ≡ 1 (mod p)。

因此，序列{1^2, 2^2, 3^2, …,(p−1)^2} 在模 p 下的循环节长度为 p-1此外，同余理论还可以用于计算和判定整数的性质。

初一竞赛班讲义——同余式（一）【数论背景】数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯． 先看一个游戏：有n ＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？同余，顾名思义，就是余数相同．【定义讲解】定义1 给定一个正整数m ，如果用m 去除a ，b 所得的余数相同，则称a 与b 对模m 同余，记作(mod )a b m ≡并读作“a 同余b ，模m ”或读作“a 与b 对模m 同余”。

若a 与b 对模m 同余，由定义1，有12,a mq r b mq r =+=+所以 a -b=m(q 1-q 2)， 即 ()m a b - 反之，若()m a b -，设112212,,0,1a mq r b mq r r r m =+=+≤≤-则有12()m r r -．因｜r 1-r 2｜≤m -1，故r 1-r 2=0，即r 1＝r 2．于是，我们得到同余的另一个等价定义：定义2 若a 与b 是两个整数，并且它们的差a-b 能被一正整数m 整除，那么，就称a 与b 对模m 同余．同余式的写法，使我们联想起等式．其实同余式和代数等式有一些相同的性质，最简单的就是下面的定理1．定理1 (1)a ≡a(modm)．(2) 若a ≡b(modm)，则b ≡a(modm)．(3) 若a ≡b(modm)，b ≡c(modm)，则a ≡c(modm)．在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立．定理2 若a ≡b(modm)，c ≡d(modm)，则a ±c ≡b ±d(modm)，ac ≡bd(modm)．证 由假设得m ｜a -b ，m ｜c -d ，所以m ｜(a ±c)-(b ±d)， m ｜c(a -b)＋b(c -d)，即a ±c ≡b ±d(modm)，ac ≡bd(modm)．由此我们还可以得到：若a ≡b(modm)，k 是整数，n 是自然数，则a ±k ≡b ±k(modm)，ak ≡bk(modm)，a n ≡b n (modm)．★★★ 对于同余式ac ≡bc(modm)，我们是否能约去公约数c ，得到一个正确的同余式a ≡b(modm)？在这个问题上，同余式与等式是不同的．例如25≡5(mod 10)，约去5得5≡1(mod 10)．这显然是不正确的．但下面这种情形，相约是可以的．定理3 若ac ≡bc(modm)，且(c ，m)=1，则a ≡b(modm)．证 由题设知ac-bc=(a-b)c=mk．由于(m，c)=1，故m｜a-b，即a≡b(modm)．应用同余式的性质可以简捷地处理一些整除问题．若要证明m整除a，只需证a≡0(modm)即可．【例题分析】求余数是同余的基本问题．在这种问题中，先求出与±1同余的数是一种基本的解题技巧．例1(1)求33除21998的余数．(2)求8除72n+1-1的余数．例2求证：(1)8｜(551999＋17)；(2) 8(32n＋7)；(3)17｜(191000-1)．证例3求使2n-1为7的倍数的所有正整数n．例4 对任意的自然数n，证明A=2903n-803n-464n＋261n能被1897整除．例5任意平方数除以4余数为0和1(这是平方数的重要特征)．例6任意平方数除以8余数为0，1，4(这是平方数的又一重要特征)．。

第8讲数论（余数问题）1、带余除法的定义及性质：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≢r＜b；我们称上面的除法算式为一个带余除法算式。

这里：(1)当0r=时：我们称a可以被b整除，q称为a除以b的商或完全商；(2)当0r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商。

余数一定要比除数小。

2、三大余数定理：（1）余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。

当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

（2）余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。

（3）同余定理若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m 整除用式子表示为：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整数，即m|(a－b)。

3、弃九法：任何一个整数模9同余于它的各数位上数字之和。

以后我们求一个整数被9除的余数，只要先计算这个整数各数位上数字之和，再求这个和被9除的余数即可。

（思考：有没有求一个整数被11除的余数的快速方法呢？）4、同余同补问题：例1：（1）用某自然数a去除1992，得到商是46，余数是r，求a和r。

（2）有两个自然数相除，商是17，余数是13，已知被除数、除数、商与余数之和为2113，则被除数是多少？练习：（1）甲、乙两数的和是1088，甲数除以乙数商11余32，求甲、乙两数；（2）用一个自然数去除另一个自然数，商为40，余数是16.被除数、除数、商、余数的和是933，求这2个自然数各是多少？例2：三个不同的自然数的和为2001，它们分别除以19,23,31所得的商相同，所得的余数也相同，这三个数是_______，_______，_______。

故有 f ( k + 1) ≡f ( k + 21) ( mod 10) . 这说明猜想是成立的 .
2. 5 证明有关重点定理
余数 , 即 rl + 1 = rl + k , 由题设条件 ②可知
r l + 1 与 r l + 1 - k 同色 , 即 r l + 1 与 r l 同色 .
例 5 ( 欧拉定理 ) ( a , m ) = 1 ] aφ( m ) ≡ 1 ( mod m ) . 证 设 a1 , a2 , …, aφ( m ) 是 m 的缩系 , 因为 ( a , m ) = 1 , 所 以 aa1 , aa2 , …,
由于 1978 = 1976 + 2 ≡ 2 ( mod 8) ] 2n ≡ 2 m ( mod 8) 又由于 n > m ≥ 1 , 显然 m = 1 , 2 时 ( 3 ) 式不 成 立 , 所 以 m ≥3 , 再 由 ( 2 ) 式 , ( 53 ,
1978 m ) = 1 . 1978 n = 1978 m ( mod 125)
k
可令 19784 = 5 t + 1 , 则
0 ≡ 19784 k - 1 = ( 5 t + 1 )
k ( k - 1)
- 1 ≡
2
(5 t) 2 + k・ ・ 5 t ( mod 125) .
于是 k 应含 52 作为因子 , 其最小为 25 . 因此 n - m = 4 × 25 = 100 最小 , 而 n + m = ( n - m) + 2 m , n - m > 0 ,
2. 2 求最值方面
例3 给集 M = { 1 , 2 , …, n - 对 i ∈M , i 与 n - i 同

初中数学竞赛：数的整除（同余）【内容提要】一. 同余的概念 两个整数a 和b 被同一个正整数m 除，所得的余数相同时，称a, b 关于模m 同余.记作a ≡b(mod m).如：8和15除以7同余1，记作8≡15(mod 7), 读作8和15关于模7同余.∵2003=7×286+1，∴2003≡1 (mod 7)；∵－7和6对于模13同余6（余数是非负数）∴－7≡6（mod 13）；∵35和0除以5，余数都是0（即都能整除）∴35≡0（mod 5）.二. 用同余式判定数的整除若a ≡b(mod m)， 则m|(a －b).即a －b ≡0(mod m)⇔m|(a －b).例如：11≡25(mod 7)⇔7|(25－11)； 或 7|(11－25).∵25+35≡2+3≡0 (mod 5)，∴5|25+35.三. 同余的性质 (注意同余式与等式在变形中的异同点)1. 传递性： )(m o d )(m o d )(m o d m c a m c b m b a ≡⇒⎭⎬⎫≡≡. 2. 可加可乘性：⎩⎨⎧≡+≡+⇒⎭⎬⎫≡≡).(mod )(mod ).(mod )(mod m bd ac m d b c a m d c m b a ；， 推论 可移性：a ≡b+c (mod m)⇒(a －b)≡c(mod m).可倍性：a ≡b(mod m)⇒ka ≡kb(mod m) (k 为正整数).可乘方：a ≡b(mod m)⇒ a n ≡b n (mod m) (n 为正整数).3. 当d 是a, b, m 的正公因数时， a ≡b(mod m)⇒d b d a ≡(mod dm ). 如：2是20，26，6的正公因数， 20≡26(mod 6)1310≡⇒(mod 3).四. 根据抽屉原则：任给m+1个整数，其中至少有两个数对于模m 同余.即至少有两个，其差能被m 整除.例如：任给5个数a,b,c,d, e.其中至少有两个，它们的差能被4整除.∵除以4的余数只有0，1，2，3四种.∴5个数除以4至少有两个同余.【例题】例1.已知：69，90，125除以正整数n有相同的余数.求：n的值解：∵69≡90(mod n)，90≡125(mod n).∴n|(90－69)，n|(125－90).而21,35的最大公约数是7，记作(21,35)=7 (7是质数).∴n=7例2.求388除以5的余数.解：∵38≡3 (mod 5)，∴388≡38≡(32)4≡(－1)4≡1 (mod 5).(注意9除以5余4，－1除以5也是余4，∴32≡－1 (mod 5)例3.求997的个位数字.解：∵74k+n与7n的个位数字相同，且9≡1 ( mod 4)，∴99≡19 ≡1(mod 4).∴997与71的个位数字相同都是7.例4.求证：7|(22225555+55552222).证明：∵22225555+55552222=(22225)1111+(55552)1111∵2222=7×317+3 ，5555=7×793+4.∴2222≡3 ( mod 7)；5555≡4 (mod 7).∴22225≡35≡5(mod 7)；55552≡42≡2 (mod 7).∴22225+55552≡5+2≡0 ( mod 7).即22225≡－55552 (mod 7).∴(22225)1111≡(－55552)1111≡－(55552)1111 (mod 7).∴22225555+55552222≡0 (mod 7).∴7|(22225555+55552222).例5.求使32n－1能被5整除的一切自然数n.解：∵32≡－1 (mod 5) ，∴(32)n≡(－1)n (mod 5).32n－1≡(－1) n－1 (mod 5)∵当且仅当n为偶数时，(－1) n－1=0.∴使32n－1能被5整除的一切自然数n是非负偶数例6.已知：a,b,c是三个互不相等的正整数.求证：a3b－ab3,b3c－bc3,c3a－ca3三个数中，至少有一个数能被10整除.证明：用同余式判定整除法证明当正整数n的个位数是0，1，4，5，6，9时，n3的个位数也是0，1，4，5，6，9.∴这时n3≡n (mod 10)；当正整数n的未位数为2，3，7，8时，n3的个位数分别是8，7，3，2.∵8与－2，7与－3，3与－7，2与－8，除以10是同余数，∴这时n3≡－n (mod 10)；把三个正整数a,b,c按个位数的情况，分为上述两类时，则至少有两个属于同一类.设a,b的末位数是同一类，那么a3b－ab3≡ab－ab≡0 (mod 10)；或a3b－ab3≡(－a)b－a(－b)≡0 (mod 10).∴10| (a3b－ab3)【练习】1.三个数33，45，69除以正整数N有相同余数，但余数不是0，那么N=_______.2. 求777的个位数字.3. 求379245除以19的余数； 41989除以9的余数.4. 求19891990÷1990的余数.5. 四个数2836，4582，5164，6522都被同一个正整数除，所得的余数都相同且不是 0，求除数和余数.6. 求证：7|(33334444+44443333).7. 已知：正整数n>2 . 求证：31111≡ 个n (mod 4).8. 任给8个整数，其中必有两个，它们的差能被7整除，试证之.9. 求使2n +1能被3整除的一切自然数n.10. 已知 69，90，125除以N (N>1) 有同余数，那么对于同样的N ，81同余于() （A ）3. （B ）4. （C ）5. （D ）7. （E ）8.【答案】1. N=12，6，2.(舍去3，∵余数是0).解法仿例1.2. 个位数字是3.∵7≡－1(mod 4), ∴ 777≡(－1)77(mod 4)……仿例33. 余数是18和1. ∵37≡－1 (mod 19) ∴原式≡－1 ≡18 (mod 19)；41989=(43)663 64≡1(mod 9) 64663≡1663 ≡1.4. 余数是1. ∵1989≡－1 (mod 1990) ∴19891990≡(－1)1990≡1 (mod 1990).5. 根据题意 2836≡4582≡5164≡6522≡r (mod m)而且4582－2836=1746, 6522－5164=1358.∴ m| 1746, 且m|1358， (1746，1358)=2×97∴m=194, 97, 2 (2不合题意.舍去)答：除数为194， 余数是120或除数为97， 余数是236. ∵ 33334444+44443333≡14444+(－1)3333≡0 (mod 7).7. 个个211111111-=n n 00+11≡11≡3 (mod 4).8. 8个正整数分别除以7，必有两个或两个以上是同余数9. ∵2≡－1 (mod 3) ∴2n ≡(－1)n (mod 3)2n +1≡(－1)n +1 (mod 3)当且仅当n奇数时, (－1)n+1≡0∴能被3整除的一切正整数n是奇数10. (B).。

第7讲同余的概念及基本性质数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯．先看一个游戏：有n＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格．最后只剩4个空格时，你的对手就必输无疑了．因此，若n除以4的余数是1，2或3时，那么先走者甲胜；若n除以4的余数是0的话，那么后走者乙胜．在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么．又例如，1999年元旦是星期五，1999年有365天，365=7×52＋1，所以2000年的元旦是星期六．这里我们关心的也是余数．这一讲中，我们将介绍同余的概念、性质及一些简单的应用．同余，顾名思义，就是余数相同．一、基础知识定义1 给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作a≡b(mod m)，并读作a同余b，模m．否则，就称a与b对于模m不同余，记作a≡b（mod m），根据定义，a与b是否同余，不仅与a、b有关，还与模m有关，同一对数a和b，对于模m同余，而对于模n也许就不同余，例如，5≡8（mod 3），而5≡8（mod 4），若a与b对模m同余，由定义1，有a=mq1＋r，b=mq2+r．所以a-b=m(q1-q2)，即m｜a-b．反之，若m｜a-b，设a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2．于是，我们得到同余的另一个等价定义：定义2 若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a 与b对模m同余．另外，根据同余的定义，显然有以下几种关系是成立的：⑴a≡a（mod n）⑵a≡b（mod m）⇔b≡a（mod n）⑶a≡b（mod n）⇒a≡c（mod m）b≡c（mod m）由此可见，同余是一种等价关系，以上这三条分别叫做同余的反射性，对称性和传递性，而等式也具有这几条性质．二、典型例题;例1．如果a≡b（mod m），以下命题正确的有哪些？请说明理由？⑴m | a－b⑵a = b+mt⑶a = k1m+ r1，b = k2m+ r2（0≤r1，r2＜m）⇔r1= r2解：⑴因a≡b（mod m），所以可得a = k1m+ r，b = k2m+ r，那么a－b=（k1－k2）m，由于k1－k2是整数，因此m | a－b是正确的．⑵根据⑴可得a－b= mt，即a= b+mt⑶根据⑴可得，m | r1－r2，又因为0≤| r1－r2 |＜m，所以| r1－r2 |=0，故r1= r2．例2．判断正误，并说明理由．⑴如果a≡b（mod m）那么ka≡kb（mod m）⑵如果a≡b（mod m），c是整数，那么a±c≡b±c (mod m)⑶如果a1≡b1（mod m），a2≡b2（mod m），那么a1±a2≡b1±b2 (mod m)，a1a2≡b1b2 (mod m)．⑷如果3a≡3b(mod 6 )，那么a≡b (mod 6 )解：⑴∵a≡b（mod m），∴m | a－b，∴m | k (a－b)即m | (ka－kb)∴ka≡kb（mod m）⑴成正确⑵∵a≡b（mod m），∴m | a－b又因为c是整数，所以m | a－c－b+c，即m | (a－c) －(b－c)即a－c≡b－c（mod m）同理可得，a+c≡b+c（mod m）⑶仿照上面的两个小题的方汪，可以判定这个命题也是正确的⑷显然6≡12(mod 6)，而2≡ 4 (mod 6)，因此，这个命题不正确说明：⑶的结论可以得到同余的另一条性质，即a≡b（mod m）⇒a n≡b n（mod m）此题说明两个同余式能够象等式一样进行加、减、乘、乘方，但同余式两边却不能除以同一数，那么，同余式的两边在什么情况下可以同除以一个数呢？我们先看下面的例题．例3．由下面的哪些同余式可以得到同余式a≡b（mod 5）①3a ≡3b （mod 5） ②10a ≡10b （mod 5）③6a ≡6b （mod 10） ④10a ≡10b （mod 20）解：①因3a ≡3b （mod 5），所以5 | 3（a －b ），而5 | 3 ，因此5 | a －b ，故a ≡b （mod 5）②由10a ≡10b （mod 5）可以得到5 | 10（a －b ），而5 | 10，因此5不一定整除a －b ，故a ≡b （mod 5）就成立③由6a ≡6b （mod 10）可得10 | 6（a －b ），而10=2×5，6=2×3，因此5 | a －b ， 故a ≡b （mod 5）成立④由10a ≡10b （mod 20）可得到20 | 10（a －b ），而20= 4×5，4 | 10，因此5 | (a －b )故a ≡b （mod 5）不成立综上所述，由3a ≡3b （mod 5）或6a ≡6b （mod 10）都可以得到a ≡b （mod 5）说明：在①中，因为（3，5）=1，因此由5 | 3（a －b ）一定可以得到5 | a －b ，进而得到a ≡b （mod 5），一般地，如果（k ，m ）=1，ka ≡kb （mod m ），那么a ≡b （mod m ）在③中，因（6，10）=2，因此由10| 6（a －b ）一定可以得到5 | a －b ，进而得a ≡b （mod 5），一般地，如果（k ，m ）= d ，ka ≡kb （mod m ），那么a ≡b )(mod dm ．例4．如果a ≡b （mod 12）且a ≡b （mod 8），那么以下同余式一定成立的是哪些？①a ≡b （mod 4） ②a ≡b （mod 24） ③a ≡b （mod 20） ④a ≡b （mod 48） 解：正确的有①和②①由题中的条件可得12 | a －b ，又因4 | 12，所以4 | a －b ，故a ≡b （mod 4）． ②因12 | a －b ，8| a －b ，所以a －b 是12和8的公倍数，又因为[8，12]=24，因此 a －b 必是24的倍数，即24 | a －b ，故a ≡b （mod 24）．③显然，当a = 26，b = 2时满足条件a ≡b （mod 12）和a ≡b （mod 8），但却不满足 a ≡b （mod 20）．④同③，用a = 26，b = 2验证即可．【说明】：⑴一般地，若a ≡b （mod m ）且n | m ，那么a ≡b （mod n ）⑵若a ≡b （mod m ），a ≡b （mod n ），那么a ≡b （mod [m ，n ]），它的一个特殊情况就是：如果a ≡b （mod m ），a ≡b （mod n ）且（m ，n ）=1，那么a ≡b （mod m n ）【一些结论】1.同余定义的等价形式①a ≡b （mod m ）⇔m | a －b②a ≡b （mod m ）⇔a = b +mt2．同余式的同加、同乘性如果a 1≡b 1（mod m ），a 2≡b 2（mod m ）那么⑴a 1±a 2≡b 1±b 2（mod m ）⑵ka 1≡kb 1（mod m ）（k ∈Z ）⑶a 1a 2≡b 1b 2（mod m ）⑷a 1n ≡b 1n （mod m ）（n 是整数）．3．如果（k ，m ）=d ，ka ≡kb （mod m ），那么a ≡b )(mod dm ． 这条性质的直接推论就是：如果（k ，m ）=1，ka ≡kb （mod m ），那么a ≡b （mod m ）4．如果a ≡b （mod m ）且n | m ，那么a ≡b （mod n ）5．如果a ≡b （mod m ），a ≡b （mod n ），那么a ≡b （mod [m ，n ]）这条性质的一个推论就是：如果a ≡b （mod m ），a ≡b （mod n ）且（m ，n ）=1，那么a ≡b （mod m n ）例5．⑴求19992002除以9的余数；⑵求1010除以7的余数解：⑴∵9 | 1999－1000，∴1999≡1000≡1（mod 9）∴19992000≡12002≡1（mod 9），∴19992000除以9的余数是1⑵∵10≡3（mod 7），∴103≡33≡－1（mod 7）∴106≡（－1）2≡1（mod 7），∴1010≡104（mod 7）又∵102≡9≡2（mod 7），∴102≡10 4≡22≡4（mod 7）所以1010除以7的余数是4．说明：求较大数的余数时，可先设法找到与±1同余的数，然后利用同余式的性质，求出所求数的余数．例6．求14589+32002除以13的余数．解：∵145≡2（mod 13），∴1456≡26≡－1（mod 13）∴（1456）14≡（－1）14≡1（mod 13）即14584≡1（mod 13）又∵1455≡25≡6（mod 13）所以14589≡14584·1455≡6×1≡6（mod 13）又∵33≡1（mod 13），∴（33）667≡32001≡1（mod 13），∴32002≡3（mod 13） 所以，14589+32002≡6+3≡9（mod 13）即14589+32002除以13的余数是9例7．求19982002的十位数字分析：此题可以通过19982002的末两位数来求解，与前面的方法类似解：∵199898≡－2（mod 100），∴19982002≡（－2）2002≡22002≡41001（mod 100） 因为4≡4（mod 100），42≡16（mod 100），43≡64（mod 100），44≡56（mod 100），45≡24（mod 100），46≡96（mod 100），47≡84（mod 100），48≡36（mod 100）， 49≡44（mod 100），410≡76（mod 100），411≡4（mod 100）…所以4 n 除以100的余数是以4、16、64、56、24、96、84、36、44、76周期性出现的，因41001=410×100+1，所以41001≡4（mod 100），因此19982002≡4（mod 100），故19982002的十位数字是0．说明：正整数幂的末位数、末两位数、末三位数都具有周期性．例8（1998年匈牙利奥林匹克竞赛题）求使2n +1能被3整除的一切自然数n . 解∵ ∴则2n +1∴当n 为奇数时，2n +1能被3整除；当n 为偶数时，2n +1不能被3整除.例9 求证31980+41981能被5整除.证明 ∵∴∴∴例10．求20032002的末位数字．分析：此题就是求20032002除以10的余数解：∵2003≡3（mod 10），∴20034≡34≡1（mod 10），∴20032002≡（20034）500·20033≡1500·33≡27≡7（mod 10）∴20022002的末位数字是7． 说明：对于十进制的整数011a a a a n n -有如下性质：)10(mod 0011a a a a a n n ≡- 例11．已知n 是正整数，证明48 | 72n ―2352n ―1证明：∵48=3×16，（3，16）=1∴只需证明3| 72n ―2352n ―1且16 | 72n ―2352n ―1即可∵7≡1（mod 3），2352≡0（mod 3）∴72n ―2352n ―1≡12n ―2352×0－1≡0（mod 3）∴3 | 72n ―2352n ―1，又∵2352=16×147，∴2352≡0（mod 16）∴72n ―2352n ―1≡49n －1≡1n －1≡0（mod 16）∴16 | 72n ―2352n ―1，所以48| 72n ―2352n ―1．说明：当模很大时，可以用本题的方法把问题化为较小的模来求解，请同学位用这个方法重解例8．例12．已知n是任意的正整数，且m | 7n+12n―1，求正整数m的最大值．解：设a n=7n+12n―1，那么，a1=7+12―1=18，a2=72+24―1=72∴（a1，a2）=（18，72）=18，∴m≤18，下面证明对任何正整数n，都有18 | 7n+12n―1又因为18=2×9，所以只须证明2 | 7n+12n，9 | 7n+12n―1即可．∵7≡1（mod 2），∴7n+12―1≡1n+0―1≡0（mod 2）即2 | 7n+12n―1，对n进行分类讨论，⑴若n≡0（mod 3），则n=3k（k为正整数）7n+12n―1≡73k+36k+1≡（―2）3k+0―1≡（―8）k―1≡1k―1≡0（mod 9）⑵若n≡1（mod 3），则n=3k+1（k为非负整数）7n+12n―1≡73k+36k+127+12―1≡0（mod 9）⑶若n≡2（mod 3），则n=3k+2（k为非负整数）7n+12n―1≡73k·72+36k+24―1≡72+24―1≡0（mod 9）因此，对一切自然数n，都有9 | 7n+12n―1．综上所述，18 | 7n+12n―1，因此m的最大值为18．例13 把1，2，3…，127，128这128个数任意排列为a1，a2，…，a128，计算出｜a1-a2｜，｜a3-a4｜，…，｜a127-a128｜，再将这64个数任意排列为b1，b2，…，b64，计算｜b1-b2｜，｜b3-b4｜，…，｜b63-b64｜．如此继续下去，最后得到一个数x，问x是奇数还是偶数？解因为对于一个整数a，有｜a｜≡a(mod 2)，a≡-a(mod 2)，所以b1＋b2＋…＋b64=｜a1-a2｜+｜a3-a4｜+…+｜a127-a128｜≡a1-a2＋a3-a4+…+a127-a128≡a1＋a2＋a3＋a4+…+a127＋a128(mod 2)，因此，每经过一次“运算”，这些数的和的奇偶性是不改变的．最终得到的一个数x≡a1＋a2＋…＋a128＝1＋2＋…＋128＝64×129≡0(mod 2)，故x是偶数．例14 求证：一个十进制数被9除的余数等于它的各位数字之和被9除的余数．10≡1(mod 9)，故对任何整数k≥1，有10k≡1k＝1(mod 9)．因此即A被9除的余数等于它的各位数字之和被9除的余数．说明(1)特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除．(2)算术中的“弃九验算法”就是依据本题的结论．三、模拟训练1求证：(1)8｜(551999＋17)；(2) 8(32n ＋7)；(3)17｜(191000-1)．证 (1)因55≡-1(mod 8)，所以551999≡-1(mod 8)，551999＋17≡-1＋17=16≡0(mod 8)，于是8｜(551999＋17)．(2)32=9≡1(mod 8)，32n ≡1(mod 8)，所以32n ＋7≡1＋7≡0(mod 8)，即8｜(32n ＋7)．(3)19≡2(mod 17)，194≡24=16≡-1(mod 17)，所以191000=(194)250≡(-1)250≡1(mod 17)，于是17｜(191000-1)．2．求20032002的末位数字分析：此题就是求20032002除以10的余数解：∵2003≡3（mod 10），∴20034≡34≡1（mod 10），∴20032002≡（20034）500·20033≡1500·33≡27≡7（mod 10）∴20022002的末位数字是7说明：对于十进制的整数011a a a a n n -有如下性质：011a a a a n n -)10(mod 0a ≡． 3求2999最后两位数码.解 考虑用100除2999所得的余数. ∵∴又∴∴ ∴2999的最后两位数字为88.4．求证：22000+1不能被7整数．分析：只需证明22000≡－1（mod 7）即可证明：∵26≡1（mod 7），∴22000≡（26）333·22≡1·22≡4（mod 7），∴22000+1≡5（mod 7）所以7 | 22000+15 对任意的自然数n，证明A=2903n-803n-464n＋261n 能被1897整除．证1897=7×271，7与271互质．因为2903≡5(mod 7)，803≡5(mod 7)，464≡2(mod 7)，261≡2(mod 7)，所以A=2903n-803n-464n+261n≡5n-5n-2n+2n=0(mod 7)，故7｜A．又因为2903≡193(mod 271)，803≡261(mod 271)，464≡193(mod 271)，所以故271｜A．因(7，271)=1，所以1897整除A．6 任意平方数除以4余数为0和1(这是平方数的重要特征)．证因为奇数2=(2k＋1)2=4k2＋4k+1≡1(mod 4)，偶数2=(2k)2=4k2≡0(mod 4)，所以7 任意平方数除以8余数为0，1，4(这是平方数的又一重要特征)．证奇数可以表示为2k＋1，从而奇数2=4k2＋4k+1=4k(k＋1)+1．因为两个连续整数k，k＋1中必有偶数，所以4k(k＋1)是8的倍数，从而奇数2=8t+1≡1(mod 8)，偶数2=(2k)2=4k2(k为整数)．(1)若k=偶数=2t，则4k2=16t2＝0(mod 8)．(2)若k=奇数=2t+1，则4k2=4(2t＋1)2=16(t2＋t)+4≡4(mod 8)，所以求余数是同余的基本问题．在这种问题中，先求出与±1同余的数是一种基本的解题技巧．8 形如F n＝22n+1，n=0，1，2，…的数称为费马数．证明：当n≥2时，F n的末位数字是7．证当n≥2时，2n是4的倍数，故令2n=4t．于是F n=22n＋1=24t+1=16t＋1≡6t＋1≡7(mod 10)，即F n的末位数字是7．说明费马数的头几个是F0＝3，F1＝5，F2＝17，F3＝257，F4＝65537，它们都是素数．费马便猜测：对所有的自然数n，F n都是素数．然而，这一猜测是错误的．首先推翻这个猜测的是欧拉，他证明了下一个费马数F5是合数．。

同 余同余是数论中的重要概念，也是一种方便有力的工具。

它主要涉及同余式、剩余类及鸥拉函数等内容。

一、 基本理论：1.同余式：a ≡b(modm) ⇔a=1q m+r 且b=2q m+r ⇔m ∣a-b （1） 自反性：a ≡a(modm)（2） 对称性：a ≡b(modm) ⇔b ≡a(modm)（3） 传递性：a ≡b(modm)且b ≡c(modm)，则a ≡c(modm)（4） a ≡b(modm)，c ≡d(modm)，则a ±c ≡b ±d(modm)，ac ≡bd(modm)（5） a ≡b(modm)，n +∈Z ，则nn b a ≡ (modm) （6） a ≡b(modm)，m=qn ，n +∈Z ，则a ≡b(modn)（7） a ≡b(mod i m )，i =1、2、…k ，则a ≡b(mod[k m m m ,,21])（8） m ≥1，m +∈Z ，(a,m)=1，则∃c ，使ac ≡1(modm)2．剩余类i M ={i+km ∣i=1,2,…m-1,k ∈ Z}称为模m 的剩余类（同余类），表示为imodm.(1) 在任意给定的m+1个整数中，必有两个对模m 同余。

(2) 存在m 个数，两两对模m 不同余。

(3) n ∣m ，则Z r ∈∃，有rmodm ⊆rmodn(4) 1a modm=2a modm ，则(1a ，m)=(2a ，m)(5) f(x)=011a x a x a n n n n +++-- ， g(x)= 011b x b x b n n n n +++-- ，是两整系数多项式，若满足i i b a ≡(modm)(i=1,2…n)，则当a ≡b(modm)时，f(a)=g(b)(modm)。

（上述多项式叫同余多项式，记为f(x) ≡g(x)(modm)3．鸥拉函数(r,m)=1，则称rmodm 为模m 的既约（互素）同余类，模m 的所有既约同余类的个数记作Ф(x),叫鸥拉函数。

第十三讲同余在日常生活中,有时我们感兴趣的不是某些整数,而是这些整数去除以某一个正整数所得的余数．例如：(1) 从甲地开往乙地的火车,全程运行时间是34小时15分,如果火车20点55分从甲地开出,问到达乙地的时间是几点？答案不是55点10分,而是7点10分,即用55小时10分去除以24小时所得的余数．(2) 已知1990年的元旦是星期一,问1991年的元旦是星期几？因为1990年有365天,而365除以7所得的余数是1,所以,1991年的元旦是星期二．由于同是几点钟或同为星期几,常常在生活中有同样的意义,这样就在数学中产生了“同余”的概念．可以说,“同余”这个概念的产生,大大地丰富了数学的内容．所谓“同余”,顾名思义,就是“余数相同”．由此,我们可以这样来定义,“同余”这个概念：设a,b都是整数,m是正整数,如果a,b除以m所得的余数相同,则称a,b对模m同余．上述定义具有直观、明瞭的优点,同学们很容易理解,但它不便在理论上进行推导,运用起来也不太方便,为此,我们需要将它进行改进．设a,b都是整数,m是正整数,如果已知a,b除以m所得的余数相同,则可设：a＝ms＋r, b＝mt＋r,其中s,t,r都是整数,且0≤r＜m, 所以a－b＝m(s－t),从而m|(a－b)．反之,如果已知m|(a－b),则a,b除以m所得的余数相同．否则,若a＝ms＋r1, b其中s,t,r1,,r2都是整数,0≤r1<m,0≤r2<m,且r1a－b＝m(s－t)＋(r1因为－m<r1－r2<m且r1－r2≠0,所以m盾．由此知：a,b除以ma,b除以m所得的余数相同,给“同余”定义设a,b都是整数,m是正整数,如果m果m不整除(a－b),则称a,b对模m不同余,由定义可知：①a≡b(mod m)⇔m|(a－b),特别地a≡②设1≤b＜m,则a≡b(mod m)⇔a被m除由同余的定义,表示整数,性质1a≡a (mod m)．性质2a≡b (mod m)⇒b≡a (mod m)．性质3 a≡b (mod m),b≡c (mod m)⇒a≡c性质4a≡b (mod m)⇒a＋c≡b＋c (mod推论1 若a≡b (mod m),c≡d (mod m推论2 若a1≡b1 (mod m),a2≡b2a1＋a2＋…＋a n＝b1性质5 a≡b (mod m)⇒ac≡bc(mod m)．推论1 若a≡b (mod m),c≡d (mod m),则ac≡bd (mod m)．推论2 若a1≡b1 (mod m),a2≡b2 (mod m), …,a n≡b n (mod m),则a1·a2…a n＝b1·b2…b n(mod m)．推论3 a≡b (mod m)⇒a n≡b n(mod m)．我们上面谈到的同余的性质,和等式的性质是完全类似的,因此,结合等式的性质,容易理解、掌握和运用同余的性质．但是,同余和等式毕竟是两个不同的概念,因此,它们的性质并不完全相同．例如,已知ac＝bc,c≠0,则a＝b．但是,如果已知ac≡bc(mod m),c≠0,却不能得到a≡b (mod m)．例如10×3≡4×3 (mod 18),但10≡4 (mod 18)．因此,我们在利用同余的概念及性质解题时,要特别注意不能和等式的性质混淆．例1．设a,b都是正整数,且a被7除余数是2,b被7除余数是5,求a2＋4b和a2－4b被7除的余数．(3) 17| (191000－1)．例6．求证：7|(22225555＋55552222)．例7．求证：1990|(996996－994994)．例8．一个正整数的个位数字是7,上述条件的最小正整数．例9．设n是正整数,求证：7不整除(4n＋练1．求证：(1) 7|(501990－1)；(2) 17|(502．求余数：(1) 471990除以5；(2) 471991除以5；(3) 1011990除以11；(4) 1011991除以11；(5) 10n除以13．3．求证；(1) 7|(21990＋5)；(2) 33|(21990－1)；993＋991991).,所得到的数是原数的4倍,求满足上,所得到的数是原数的3倍,求满足上7．在七位数30003x y．x y中,当x, y为何值时,13|300038．有40个整数,其中每一个都不能被5整除,求证：这40个数的40次幂的和能被5整除．9．设a,b,c都是正整数,且：a2＋b2＝c2,10．设n是正整数,求证：(1) 6不整除(5n＋3)；。

第8讲剩余系及其一次同余方程一、基础知识：（1）剩余系对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2, …,n-1中的某一个。

依次可将整数分成n个类（例如n＝2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。

定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,...,n-1），那么就被称为是模n的一个完全剩余系。

定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]，这m个数{0,1,2,…m-1}称为一个完全剩余系，每个数称为相应类的代表元。

例如：当m=10则,{0,1,2,3,4,5,6,7,8,9}最小非负完全{-5,-4,-3,-2,-1,0,1,2,3,4}绝对值最小{-4,-3,-2,-1,0,1,2,3,4,5}绝对值最小（一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质：①每一个整数一定包含在而且仅包含在模m的一个剩余类中②整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是p mod m= {p+km（k是整数）}③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。

这条性质用数学符号就可表示为：p mod m= q mod m p≡q（mod m）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。

这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是：0mod m，1 mod m，2 mod m，…（m―1）mod m。

在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。

∴

(
pk k
)

pk k
[
pk k p
]
pk k

pk 1 k
∴

(m)


(
p1 1
)
(
p2 2
)

(
pk k
)

(
p1 1

p1 1
1
)(
p2 2

p2 2
1
)
(
pk k

pk k
1
)

p1 1
(1

p11
)
p2 2
(1

p21)
pk k
(1
又 p 为奇素数， p 1为偶数，∴ ( p 1)!1 0(mod p) ，得证．
6、设 a 为整数， p 为正整数，若存在 x Z ，使得 x2 a(mod p) ，则称 a 为模 p 的二
次剩余，否则，称 a 为模 p 的二次非剩余．
p1
设 p 为奇素数，a Z 且 p a ，证明：a 是模 p 的二次剩余充要条件是 a 2 1(mod p) ；
若 a b(mod m) ， c d(mod m) ， n N* 则 a c b d(mod m) ， a c b d(mod m) ac bd(mod m) ， an bn (mod m) ．
3）除法运算：
ac bc(mod m) ，则 a b(mod m ) ． (c, m)
(1)k m p1 p2 pk
k
m(1
1
1 (1)k 1 )
p p p i1 i 1i jk i j

数论中的同余关系与应用数论是数学的一个重要分支，研究整数及其性质。

其中，同余关系是数论中的一个重要概念，它在密码学、模运算等领域中有着广泛的应用。

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

设a、b为整数，m为正整数，则a与b对模m同余，记作a≡b (mod m)。

简单来说，如果两个数除以同一个数所得的余数相等，那么它们满足同余关系。

例如，10除以4和14除以4的余数都为2，所以10≡14 (mod 4)。

同余关系在数论中有许多重要的性质。

首先，同余关系是一种等价关系，满足自反性、对称性和传递性。

即对于任意整数a，有a≡a (mod m)，对于任意整数a、b，若a≡b (mod m)，则b≡a (mod m)，对于任意整数a、b、c，若a≡b (mod m)且b≡c (mod m)，则a≡c (mod m)。

其次，同余关系还满足加法与乘法的性质。

即对于任意整数a1、a2、b1、b2，若a1≡b1 (mod m)且a2≡b2 (mod m)，则a1+a2≡b1+b2 (mod m)，a1a2≡b1b2 (mod m)。

同余关系在密码学中有着广泛的应用。

其中一个重要的应用是在信息加密中的模运算。

模运算是指将一个数除以另一个数后得到的余数。

在密码学中，常常用模运算来对信息进行加密和解密。

通过选择合适的模数和密钥，可以实现信息的安全传输。

同时，同余关系还应用于素数的判断。

素数是指只能被1和自身整除的正整数。

利用同余关系可以判断一个数是否为素数。

若n为一个正整数，若对于任意小于n的整数a，a的n次方减去a除以n所得的余数等于0，即a^n ≡ a (mod n)，则n有可能是一个素数。

除了密码学和素数判断，同余关系还有许多其他的应用。

例如，在日历计算中，可以利用7的同余关系来确定星期几；在校园卡计算机系统中，可以利用同余关系来进行余额判断和消费记录查询；在电子电路中，可以利用同余关系来确定电压与电流之间的关系。

数论讲义定义（欧拉(Euler)函数）对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n )（1）对于给定的一个素数 p ， φ(p) = p -1。

（2）则对于正整数 n = p k ，φ(n) = p k - pk -1欧拉(Euler)函数公式： kk p p p n n p p p n n k 11()11)(11()(212121---== ϕααα，则的标准分解为：若 例1 与300互素且不超过300的自然数的个数。

解 所求的数即80)511)(311)(211(300)300(=---=ϕ例2 1到1001这1001个数中，是7,11或13的倍数的有多少个？解：由于7,11,13均为质数，所有不是它们的倍数的数都是和它们互素的，而与它们互素就意味着和1001互素，且这些数都是比1001小的数。

所以我们可以直接使用 111(1001)1001(1)(1)(1)71113ϕ=⨯-⨯-⨯-61012=⨯⨯720=定理1：（欧拉（Euler ）定理）设),(m a ＝1，则)(mod 1)(m am ≡ϕ。

分析与解答：要证)(mod 1)(m a m ≡ϕ，我们得设法找出)(m ϕ个n 相乘，由)(m ϕ个数我们想到m ,,2,1 中与m 互质的)(m ϕ的个数：)(21,,,m a a a ϕ ，由于),(m a ＝1，从而)(21,,,m aa aa aa ϕ 也是与m 互质的)(m ϕ个数，且两两余数不一样，故)(21m a a a ϕ⋅⋅⋅ ≡)(21,,,m aa aa aa ϕ ≡)(m a ϕ)(21m a a a ϕ⋅⋅⋅ （m m od ），而（)(21m a a a ϕ⋅⋅⋅ m ）＝1，故)(mod 1)(m a m ≡ϕ。

这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。

例3.设1),91(=ab ，求证：)(|911212b a-。

. -同余的性质及应用1 引言数论的一些基础内容的学习，一方面可以加深对数的性质的了解，更深入的理解某些其他邻近学科，另一方面，可以加强数学训练.而整数论知识是学习数论的基础，其中同余理论有时整数论的重要组成部分，所以学好同余理论是非常重要的.在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数；问现在是星期几，就是问用7去除某一个总的天数所得的余数，假如某月2号是星期一，用7去除这月的号数，余数是2的都是星期一.我国古代孙子算经里已经提出了同余式11(mod )xb m ,22(mod )xb m ,…,(mod )k k xb m 这种形式的问题，并且很好地解决了它.宋代大数学家秦九韶在他的《数学九章》中提出了同余式1(mod )i i x M m ≡,1,2,...,i k =,i m 是k 个两两互质的正整数，12...k m m m m =,i i m m M =的一般解法.同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆内格点问题，等差级数问题中的质数分布问题，2an bn c ++形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题.数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论的一些方法和基础知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余基本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.2 同余的概念给定一个正整数m，把它叫做模，如果用m去除任意两个整数a与b所得的余数相同，我们就说对模m同余，记作(mod)≡,如果余数不同，就说对模m不同余.a b m由定义得出同余三条性质：（1）(mod)≡；a a m（2）(mod)≡；b a ma b m≡,则(mod)（3）(mod)a c m≡.≡,则(mod)b c m≡,(mod)a b m定义也可描述为:整数a,b对模m同余的充分必要条件是m a b-,即a b mt=+,t是整数.3 同余的八条基本性质由同余的定义和整数的性质得出[1]：（1）若(mod)≡,则(mod)a cb d m+≡+c d m≡,(mod)a b m若(mod)≡-a cb ma b c m+≡, 则(mod)（2）若(mod)ac bd m≡≡, 则(mod)a b m≡,(mod)c d m特别地,若(mod)≡ak bk m≡,则(mod)a b m（3）若11......(mod )k k A B m ∂∂∂∂≡,(mod )i i x y m ≡,0,1,...,i n =则1111...1...1......(mod )k k k k k k A x x B y y m ∂∂∂∂∂∂∂∂≡∑∑（4）若1a a d =,1b b d =,(,)1d m =,(mod )a b m ≡,则11(mod )a b m ≡ （5）若(mod )a b m ≡,0k >, 则(mod )ak bk m ≡；若(mod )a b m ≡,d 是a ,b 及m 任一正公因数,则(mod )a b m d d d≡ （6）若(mod )i a b m ≡,1,2,...,i k =,则12(mod[,,...,])k a b m m m ≡其中12[,,...,]k m m m 是12,,...,k m m m , k 个数最小公倍数 （7）若(mod )a b m ≡,d m ,0d >,则(mod )a b d ≡（8）(mod )a b m ≡,(,)(,)a m b m =,若d 能整除m 及a ,b 两数之一,则d 必整除a ,b 另一个.4 同余性质在算术里的应用4.1 检查因数的一些方法例1 一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除. 证:按照通常方法,把任意整数a 写成十进位数形式,即1101010...n n n n a a a a --=+++, 010i a ≤<.因101(mod3)≡, 所以由同余基本性质,即3a 当且仅当3ia ∑；同法可得9a 当且仅当9ia ∑，0,1,...,i n =.例2 设正整数11010001000...n n n n a a a a --=+++，01000i a ≤<，则7（或11或13）整除a 的充要条件是7（或11或13）整除0213(...)(...)(1)i i a a a a a ++-++=-∑，0,1,...,i n =.证：1000与-1对模7（或11或13）同余，根据同余性质知，a 与(1)i i a -∑对模7（或11或13）同余即7（或11或13）整除a 当且仅当7（或11或13）整除(1)i i a -∑，0,1,...,i n =. 例3 a =5874192，则587419236i a =++++++=∑，0,1,...,i n =能被3，9整 除，当且仅当a 能被3，9整除 解：由例1证法可知，该结论正确.例4a =435693，则43569330i a =+++++=∑，0,1,...,i n =能被3整除，但ia ∑不能被9整除当且仅当3是a 的因数，9不是a 的因数. 解：由例1的证法可得.例5 a =637693，则6371000693a =⨯+，69363756i a =-=∑，0,1,...,i n =能被7整除而不能被11或13整除当且仅当7是a 的因数但11，13不是a 的因数. 解：由例2的证法可知，该结论正确.例6 a =75312289，27510003121000289a =⨯+⨯+2893127552i a =-+=∑，0,1,...,i n =能被13整除，而不能被7，11整除当且仅当13是a 的因数，而7与11不是a 的因数. 解：由例2的证法可知.例7 应用检查因数的方法求出下列各数标准分解式1535625 ②1158066解：①65432115356251105103105106102105=⨯+⨯+⨯+⨯+⨯+⨯+，153562527ia =++++++=∑，927∴91535625，21535625110005351000625=⨯+⨯+，021()625153591a a a +-=+-=，由例2得1391，791，∴71535625，131535625，又51535625，951374095⨯⨯⨯=，15356253754095=， 5375，375755=，25， ∴54153562535137=⨯⨯⨯.②6543111580661101105108106106=⨯+⨯+⨯+⨯+⨯+，11586627ia =+++++=∑，927∴91158066，2115806611000158100066=⨯+⨯+，021()66115891a a a +-=+-=-，由例2得791，13∴71158066，131158066，又21158066，971321638⨯⨯⨯=，11580667071638=，7707，∴2115806629713101=⨯⨯⨯⨯.4.2 弃九法（验证整数计算结果的方法）我们由普通乘法的运算方法求出整数a ，b 的乘积是P ，并令1101010...n n n n a a a a --=+++，010i a ≤< 1101010...n n n n b b b b --=+++，010i b ≤<， 1101010...n n n n P c c c --=+++，010i c ≤<，如果()()i j a b ∑∑与k c ∑对模9不同余，那么所求得的乘积是错误的.特别的，在实际验算中，若i a ，j b ，k c 中有9出现，则可去掉（因90(mod9)≡）.例1 a =28997，b =39495，按普通计算方法算得a ，b 乘积是P =1145236515， 按照上述弃九法8(mod9)a ≡，3(mod9)b ≡，5(mod9)P ≡. 但83⨯与5对模9不同余，所以计算有误.例2 若a =28997，b =39495，P =1145235615，那么P a b =⨯？ 解：按照上述弃九法，8(mod9)a ≡，3(mod9)b ≡，6(mod9)P ≡.虽然83⨯与6对模9同余，但是由通常乘法计算得到1145236515a b ⨯=， 故P a b =⨯不成立.注：当使用弃九法时，得出的结果虽然是()()i j a b ∑∑(mod9)k c ≡∑也还不能完全肯定原计算是正确的.4.3 同余性质的其他应用 例1 求7除5047的余数.解：由147(2)2(mod7)≡-≡-，2247(2)4(mod7)≡-≡，5547(2)1(mod7)≡-≡-，∴50516247(47)47144(mod7)≡⨯≡⨯≡， 即5047除以7余数为4.例2 试证：形如87()k k N +∈的整数不能表为三个平方数之和.证：假定22287(,,)N k a b c a b c Z =+=++∈，则2227(mod8)a b c ++≡，但这不可能.因为对模8而论.每一个整数最小非负余数只能是0，1，2，3，4，5，6，7中的一个数.而200(mod8)≡，211(mod8)≡，224(mod8)≡，231(mod8)≡，240(mod8)≡，251(mod8)≡，264(mod8)≡，271(mod8)≡.因此，任一整数平方对模8必与0，1，4三个数之一同余，而从｛0，1，4｝中任取三个数，其和都不可能与7对模8同余，所以对于任何整数a ，b ，c 都有222a b c ++与7对模8不同余.即形如87()k k N +∈的整数不能表为三个平方数之和. 例3 试证：53335333-能被10整除.证：由已知条件有533(mod10)≡，225339(mod10)≡≡，555337(mod10)≡≡，445331(mod10)≡≡，∴5341541553(53)53(3)3133(mod10)≡⨯≡⨯≡⨯≡ 又333(mod10)≡，223339(mod10)≡≡，553337(mod10)≡≡，443331(mod10)≡≡，∴33484833(33)33(3)3133(mod10)≡⨯≡⨯≡⨯≡∴53335333(mod10)≡，即533310(5333)- 也就是说，53335333-能被10整除.例4 设,,a b c N ∈且6()a b c ++，求证：3336)a b c ++证：对模6来说每一个整数的最小非负数余数为0，1，2，3，4，5300(mod6)≡，311(mod6)≡，322(mod6)≡，333(mod6)≡，344(mod6)≡，355(mod6)≡，即对任何整数k ，3(mod6)k k ≡∴3(mod6)a a ≡，3(mod6)b b ≡，3(mod6)c c ≡ ∴333()()(mod6)a b c a b c ++≡++又()0(mod6)a b c ++≡∴333()0(mod6)a b c ++≡ 故3336()a b c ++例5 若(5,)1n =，证明5n n -能被30整除. 证：设n N ∈，(mod6)n k ≡则0,1,2,3,4,5k =由500(mod6)≡，511(mod6)≡，522(mod6)≡，533(mod6)≡，544(mod6)≡，555(mod6)≡，∴5(mod6)k k ≡即55(mod6)n k k n ≡≡≡，56)n n - 同理可知55()n n - 又(5,6)1=∴530()n n - 故5n n -能被30整除.5 同余性质在数论中的应用：求简单同余式的解5.1一次同余式、一次同余式解的概念在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解.一次同余式的定义：若用()f x 表示多项式110...n n n n a x a x a --+++，其中i a 是整数，又设m 是一个正整数，则()0(mod )f x m ≡ 叫做模m 的同余式.若n a 与0对m 不同余，则n 叫做()0(mod )f x m ≡的次数.定义：若a 是使()0(mod )f a m ≡成立的一个整数，则(mod )x a m ≡ 叫做同余式()0(mod )f x m ≡ 的一个解.定理 一次同余式(mod )ax b m ≡,a 与0对模m 不同余,它有解充要条件是(,)a m .[3]5.2 孙子定理解一次同余式组引例 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何? 解:设x 是所求物数，则依题意有，2(mod3)x ≡,3(mod5)x ≡,2(mod7)x ≡ 孙子算经里介绍用下列方法求解由表格知，所求物数是23.孙子定理：设1m ,2m ,…,k m 是k 个两两互质的正整数，12...k m m m m =，i i m m M =，1,2,...,i k =,则同余式组11(mod )x b m ≡,22(mod )x b m ≡,... ,(mod )k k x b m ≡的解是111111222...(mod )k k k x M M b M M b M M b m ≡+++,其中11(mod )i i i M M m ≡,1,2,...,i k =[4]用表格形式概括如下例1 解同余式组1(mod5)x b ≡, 2(mod6)x b ≡，3(mod7)x b ≡，4(mod11)x b ≡. 解：此时567112310m =⨯⨯⨯=,16711462M =⨯⨯=,25711385M =⨯⨯=，35611330M =⨯⨯=, 4567210M =⨯⨯=.解11(mod )i i i M M m ≡,1,2,3,4i = 得113M =,121M =,131M =,141M = 即12341386385330210(mod2310)x b b b b ≡+++.例2 韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？ 解:由题意，有1(mod5)x ≡，5(mod6)x ≡，4(mod7)x ≡，10(mod11)x ≡3462385533042101067312111(mod 2310)x ≡⨯+⨯+⨯+⨯≡≡.5.3 简单高次同余式组()0(mod )i f x m ≡, 1,2,...,i k =及()0(mod )f x p ∂≡,p 为质数，0∂>的解数及解法的初步讨论定理1 若1m ,2m ,…,k m 是k 个两两互质的正整数,12...k m m m m =,则同余式()0(mod )f x m ≡与同余式组()0(mod )i f x m ≡,1,2,...,i k =等价.若用i T 表示()0(mod )i f x m ≡,1,2,...,i k =,对模i m 的解数, T 表示()0(mod )f x m ≡对模m 的解数，则12...kT TT T =.[5]例1 解同余式()0(mod35)f x ≡，43()289f x x x x =+++.解: 由定理1知()0(mod35)f x ≡与同余式()0(mod5)f x ≡ ,()0(mod7)f x ≡等价.同余式()0(mod5)f x ≡有两个解，即1,4(mod5)x ≡ 同余式()0(mod7)f x ≡有三个解，即3,5,6(mod7)x ≡ 即()0(mod35)f x ≡有六个解，即1(mod5)x b ≡,2(mod7)x b ≡ 由孙子定理有，122115(mod35)x b b ≡+即得()0(mod35)f x ≡的解为31,26,6,24,19,34(mod35)x ≡.定理2 设1(mod )x x p ≡,即11x x pt =+,10,1,2,...t =±±是()0(mod )f x p ≡的一解，并且p不整除1()f x ,(1()f x 是()f x 的导函数),则11x x pt =+刚好给出()0(mod )f x p ∂≡，p 为质数，0∂>的一解x x p t ∂∂∂=+,0,1,2,...t ∂=±±, 即(mod )x x p ∂∂≡, 其中1(mod )x x p ∂≡.[6]例2 解同余式3262717200(mod30)x x x +++≡.解: 由定理1知()0(mod30)f x ≡与()0(mod 2)f x ≡,()0(mod3)f x ≡,()0(mod5)f x ≡等价.显然，()0(mod 2)f x ≡有两解0,1(mod 2)x ≡()0(mod3)f x ≡有一解2(mod3)x ≡()0(mod5)f x ≡有三解0,1,2(mod5)x ≡同余式()0(mod30)f x ≡有六个解即1(mod 2)x b ≡,2(mod3)x b ≡,3(mod5)x b ≡,10,1b =；22b =；30,1,2b = 由孙子定理得12315106(mod30)x b b b ≡++,以1b ,2b ,3b 值分别代入，得()0(mod30)f x ≡全部解为20,2,26,5,11,17(mod30)x ≡.例3 解同余式()0(mod 27)f x ≡，4()74f x x x =++.解:()0(mod3)f x ≡有一解1(mod3)x ≡，并且3不整除1(1)f ，以113x t =+ 代入()0(mod9)f x ≡得11(1)3(1)0(mod9)f t f +≡但(1)3(mod9)f ≡，1(1)2(mod9)f ≡即13320(mod9)t +⨯≡即1210(mod3)t +≡因此1213t t =+而2213(13)49x t t =++=+是()0(mod9)f x ≡的一解；以249x t =+代入()0(mod 27)f x ≡即12(4)9(4)0(mod27)f t f +≡,2189200(mod 27)t +⨯≡即2220(mod3)t +≡, 2323t t =+即3349(23)2227x t t =++=+为所求的解.5.4 简单二次同余式2(mod )x a p ∂≡,0∂>,(,)1a p =解的判断二次同余式一般形式为20(mod )ax bx c m ++≡,a 与0对模m 不同余，由上面所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判断形如2(mod )x a p ∂≡,0∂>有解与否问题.先讨论单质数模同余式2(mod )x a p ≡,(,)1a p =有解与否问题若它有解，则a 叫做模p 的平方剩余，若它无解，则a 叫做模p 的平方非剩余.定理1 若(,)1a p =,则a 是模p 的平方剩余的充要条件是121(mod )p ap -≡且有两解；而a 是模p 的平方非剩余充要条件是121(mod )p a p -≡-.[7]()a p是勒让得符号，它是一个对于给定单质数p 定义在一切整数a 上的函数，它的值规定如下:当()1a p=时，a 是模p 的平方剩余； 当()1a p=-时，a 是模p 的平方非剩余； 当（pa ）=0时，p a .[8]讨论质数模同余式2(mod )x a p ∂≡,0∂>,(,)1a p =有解与否问题定理22(mod )x a p ∂≡,0∂>,(,)1a p =有解的充要条件是()1a p=，并且在有解情况下，解数是2.[9]讨论合数模同余式2(mod 2)x a ∂≡,0∂>,(2,)1a =有解与否问题定理3 设1∂>,当2∂=,1(mod 4)a ≡时，2(mod 2)x a ∂≡,0∂>,(2,)1a =有解，且解数是2；当3∂≥，1(mod8)a ≡时，上式有解，解数是4.[10]例 解257(mod64)x ≡.解: 因571(mod8)≡故有4个解.把x 写成3(14)x t =±+代入原同余式,得到23(14)57(mod16)t +≡, 由此得 31(mod2)t ≡, 故44[14(12)](58)x t t =±++=±+是适合257(mod16)x ≡的一切整数，再代入原同余式得到24(58)57(mod32)t +≡, 由此得40(mod 2)t ≡, 故55(582)(516)x t t =±+⨯=±+是适合257(mod32)x ≡的一切整数,再代入原同余式得到25(516)57(mod64)t +≡, 由此得51(mod2)t ≡, 故66[516(12)](2132)x t t =±++=±+是适合257(mod64)x ≡的一切整数，因此21,53,21,53(mod64)x ≡--是所求四个解.6 结论本文从同余概念及其基本性质出发，通过实例概括总结出同余性质在算术及数论中的一些简单应用.同余性质在算术中的应用主要是通过检查因数和弃九法验算结果的实例作出阐述;数论中同余性质的应用主要体现在简单一次同余式组及高次同余式的求解,以及二次同余式是否有解的判断.参考文献[1]闵嗣鹤,严士健编. 初等数论(第二版)[M].:高等教育,1982.9:37-93.[2]余元希等.初等代数研究(上)[M].:高等教育,1988:53-82.[3]赵振成.中学数学教材教法(修订版)[M].:华东师X大学,1999.12:53-56.[4]王书琴，X晓卫.剩余定理及一次同余式组[J].XX师X大学自然科学学报, 2002-1-17.[5][法]C.布尔勒，X广才译. 代数[M].:XX科技,1984.3:72-121.[6]曹才翰，沈伯英. 初等代数教程[M].:师X大学,1987:76-85.[7]X合义.谈数论中的同余及其应用[J].XX学院学报,2007:2-6.[8]H.B.勃罗斯库列亚柯夫，X品三译. 数与多项式[M].:高等教育,1980:42.[9]林国泰,司徒永显. 初等代数研究教程[M].:暨南大学,1996:81-96.[10]林六十. 初等代数研究[M].:中国地质大学,1989:145-158.致在大学的生活和学习中, 一直得到应用数学系领导和老师们的关心和帮助, 是在他们的谆谆教导下, 我在专业知识的学习中打下了坚实的基础, 在个人修养方面我从他们身上看到了“学高为师、身正为X”的教师风X, 吸取了踏实、严谨、刻苦、认真的治学精神, 以及正直、诚实、守信的人格魅力, 并且在日常生活中身体力行, 以他们为榜样, 加强教师道德修养, 努力丰富自己、完善自己.我在大学期间取得的所有成绩都是和系领导以及老师们的帮助和教诲分不开的, 在此向他们致以衷心的感谢和良好的祝愿.在这学期撰写毕业论文的过程中, 得到了孙善辉老师的悉心指导, 熟悉了撰写论文的一般格式和许多注意事项, 这对于我以后的学习和生活都具有很好的示X作用. 感谢孙善辉老师的帮助和指导！在我论文的撰写和校对过程中, 还得到了许多同学的帮助, 是他们帮助我发现论文里的某些小小的错误, 这使我节省了时间去完成其他的工作, 在此向他们表示感谢.最后, 再次感谢孙善辉老师的辛勤指导！。

同余定理的定义与应用同余定理（Congruence theorem）是数论中一种重要的工具，用于描述整数之间“除以某个数的余数相同”的关系。

它在密码学、代数、组合数学等领域都有广泛的应用。

本文将从同余定理的定义和基本性质入手，介绍其在数论和应用领域的具体应用。

一、同余定理的定义在数论中，同余定理指的是：对于任意整数a、b和正整数n，如果a与b除以n的余数相同，即a ≡ b (mod n)，则称a与b在模n下是同余的。

同余关系具有以下几个性质：1. 自反性：a ≡ a (mod n)；2. 对称性：若a ≡ b (mod n)，则b ≡ a (mod n)；3. 传递性：若a ≡ b (mod n)，b ≡ c (mod n)，则a ≡ c (mod n)。

二、同余定理的基本性质1. 同余的运算性质（1）同余的和与差性质：若a ≡ b (mod n)，c ≡ d (mod n)，则a+c ≡ b+d (mod n)，a-c ≡ b-d (mod n)；（2）同余的积性质：若a ≡ b (mod n)，c ≡ d (mod n)，则a·c ≡ b·d (mod n)。

2. 模运算的唯一性对于每一个正整数n，模n同余关系分割整数集合Z成了n个完全的互不相交的子集，即[Z] ≡ [0],[1],[2],...,[n-1]。

任何整数都可以唯一地属于其所对应的整数集合。

三、同余定理在数论中的应用1. 同余方程的求解对于形如ax ≡ b (mod n)的同余方程，可以利用同余定理来求解。

设d是a与n的最大公约数，若b能被d整除，方程有解；否则方程无解。

若方程有解，则可以使用扩展欧几里得算法求出方程的一组特解，并通过枚举生成其他所有解。

2. 质数测试同余定理在质数测试中有着重要的应用。

费马小定理和欧拉定理就是同余定理在质数测试中的两个重要应用。

根据费马小定理，若p为质数且a是整数，则a^(p-1) ≡ 1 (mod p)。