第四章 同余方程

同余方程在数论中的应用解析同余方程是数论中一个重要的概念，它在解决很多数学问题中起着关键作用。

它的应用涉及到数论的诸多领域，如同余定理、模运算、密码学等。

本文将从数论的角度出发，对同余方程在数论中的应用进行一番解析。

首先，我们来了解一下同余方程的概念。

同余方程是指两个整数之间满足模同余的关系，即模一个固定的数时，它们的余数相等。

比如，对于整数a和b，若a-b能被m整除，我们可以表示为a≡b (mod m)，其中≡表示模同余关系，mod表示取模运算。

同余方程可以用来描述两个数之间的关系，并在数论中发挥重要作用。

在数论中，同余方程有很多应用。

首先，同余方程与同余定理密切相关。

同余定理是一种用于处理同余方程的重要工具。

根据同余定理，如果两个整数a和b在模m下的余数相等，则它们的和、积、幂等也在模m下具有相等的余数。

利用同余定理，我们可以解决一些整数方程、方程组以及一些特殊的数学问题。

其次，同余方程在模运算中有广泛的应用。

模运算是一种将数按照某一数值取模的运算。

同余方程可以用来求解模运算中的问题，如求模运算下的乘法逆元、模幂运算等。

模运算广泛应用于计算机科学、密码学等领域，通过同余方程的应用，我们可以实现密码的加密和解密，保证数据的安全性。

此外，同余方程也在数论中的素数检测以及素数生成中扮演着重要的角色。

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

同余方程可以用来判断一个数是否为素数。

根据费马小定理，如果p是一个素数，a是任意与p互质的正整数，则a^(p-1) ≡ 1 (mod p)。

根据这个性质，我们可以通过同余方程进行素性检测。

最后，同余方程还在数论中的循环小数表示、离散数学以及组合数学等领域发挥着重要作用。

循环小数是指一个有限小数部分和重复的无限循环部分组成的数。

同余方程可以用来分析循环小数的性质，如确定循环节的长度、循环节中的数字等。

此外，在离散数学和组合数学中，同余方程是探索数与数之间的整除关系、约数关系以及数列性质的重要工具。

同余方程化简摘要：一、同余方程的基本概念二、同余方程的化简方法1.公因式法2.公式法3.辗转相除法三、同余方程的应用举例四、总结正文：一、同余方程的基本概念同余方程，是指一组代数方程在模某个整数的意义下同时成立的方程。

这里的“同余”实际上是同余关系的一种推广，同余关系是指对于整数a 和b，如果它们除以某个整数m 的余数相同，即a≡b(mod m)，则称a 和b 是同余的。

二、同余方程的化简方法同余方程的化简方法主要有以下几种：1.公因式法如果同余方程的方程项中有公因式，那么可以先提取公因式，这样可以简化方程，便于求解。

例如，对于同余方程：x ≡2 (mod 3)x ≡5 (mod 3)我们可以提取公因式x，得到：x(1 ≡2 (mod 3))x(1 ≡5 (mod 3))这样就更容易求解了。

2.公式法对于形如ax ≡b (mod m) 的同余方程，如果a 和m 互质，那么可以使用公式：x ≡b * (mod m) / a (mod m)例如，对于同余方程：3x ≡11 (mod 7)我们可以使用公式法，得到：x ≡11 * (mod 7) / 3 (mod 7)这样就可以简化方程，更容易求解。

3.辗转相除法辗转相除法，又称欧几里得算法，是一种求解同余方程的方法。

它是基于以下性质：如果a 和b 是整数，且a 和b 的最大公约数是d，那么ax ≡b (mod m) 一定有解，解为：x ≡b * (mod m) / a (mod m)例如，对于同余方程：13x ≡23 (mod 17)我们可以使用辗转相除法，得到：x ≡23 * (mod 17) / 13 (mod 17)这样就可以简化方程，更容易求解。

三、同余方程的应用举例同余方程在密码学、数论等领域有广泛的应用。

例如，著名的RSA 加密算法就是基于同余方程的难解性设计的。

四、总结同余方程是代数学中的一个重要概念，它在密码学、数论等领域有着广泛的应用。

数论是研究整数性质及其相互关系的一门学科。

而同余方程作为数论中的基本概念之一，在数学领域中具有重要的地位。

同余方程可以帮助我们研究整数的行为规律，解决实际问题，并且在密码学、计算机科学等领域中也有广泛的应用。

同余方程是指满足某种特定关系的整数方程。

具体来说，对于给定的整数a，b和正整数m，如果a和b除以m所得的余数相等，即a mod m = b mod m，那么我们就称a与b在模m下同余，记作a ≡ b (mod m)。

在同余方程中，a被称作余数，m被称作模数。

同余方程在数论中的研究往往涉及到判断是否存在整数解，以及如何寻找整数解的问题。

为了解决这些问题，我们需要掌握一些重要的定理与技巧。

其中，最基本的定理就是模运算的性质：若a ≡ b (mod m) 且c ≡ d (mod m)，那么a + c ≡ b + d (mod m)，a - c ≡ b - d (mod m)，ac ≡ bd (mod m)。

这些定理使得我们在处理同余方程时，可以像处理等式一样进行运算。

而对于寻找同余方程的解，则涉及到一些更加高级的数论技巧。

其中最重要的技巧之一就是使用求解线性同余方程的方法。

对于一般形式的同余方程ax ≡b (mod m)，若gcd(a,m) | b，那么该方程存在整数解。

通过求解该方程，我们可以得到原方程的一个特解。

另外，对于m和a互质的情况，我们可以使用费马小定理或欧拉定理来求解同余方程。

同余方程的应用非常广泛。

首先，同余方程在数论领域中作为基础概念，包含了很多重要的数论定理。

例如，中国剩余定理就是基于同余方程的理论推导。

在实际问题中，同余方程也具有重要的应用。

例如，我们可以通过解决同余方程来计算某个数的阶乘的最后一位数字，或者判断一个数是否是质数等。

同样，在密码学领域中，同余方程被广泛应用于构建加密算法，特别是RSA加密算法。

综上所述，同余方程作为数论中的重要概念，具有很大的研究和应用价值。

通过研究同余方程，我们可以了解整数的行为规律，解决实际问题，并在密码学、计算机科学等领域中应用于构建加密算法等。

数论中的同余方程与模运算性质数论是研究整数性质的学科，同余方程和模运算是数论中重要的概念和工具。

同余方程是指具有相同余数的方程，而模运算是指在同余方程中，对方程中的数进行模除运算。

本文将探讨同余方程与模运算的性质及其在数论中的应用。

一、同余方程1. 同余关系的定义在整数集合中，对于给定的正整数m，若整数a和b满足a-b能被m整除，即(a-b) mod m = 0，则称a与b对于模m同余，记作a ≡ b (mod m)。

将这种关系称为同余关系。

2. 同余方程的定义同余方程是指形如ax ≡ b (mod m)的方程，其中a、b、m是已知的整数，x是未知的整数。

3. 同余方程的性质（1）同余方程的解集性质若同余方程ax ≡ b (mod m)有解，设x0是该方程的一个解，则所有解x满足x ≡ x0 (mod m)。

（2）同余方程的等价性若同余方程ax ≡ b (mod m)和ax ≡ c (mod m)的解集相等，则b ≡ c (mod m)。

（3）同余方程的合并若同余方程ax ≡ b (mod m)和cx ≡ d (mod m)的解集相等，则(a+c)x ≡ (b+d) (mod m)。

二、模运算性质1. 模运算的定义对于给定的整数a、b和正整数m，称a除以m的余数为a对于模m的模余数，记作a mod m。

2. 模运算的性质（1）模运算的基本性质若a和b对于模m同余，则a mod m = b mod m。

（2）模运算的运算性质设a1和a2对于模m同余，b1和b2对于模m同余，则有：a1 + b1 ≡ (a2 + b2) (mod m)；a1 - b1 ≡ (a2 - b2) (mod m)；a1 · b1 ≡ (a2 · b2) (mod m)。

（3）模运算的幂运算对于给定的整数a和正整数m，有：a^k mod m ≡ (a mod m)^k (mod m)，其中k为非负整数。

三、同余方程与模运算的应用1. 方程求解通过对同余方程进行变形和运算，可以解决一些实际问题，例如日历计算、时间转换等。

同余方程的解法
同余方程是一个古老的数学问题，即求解这样一个数学性质：给定两个正整数a和m，存在一个整数x，满足x除以m余a，即x=am+a。

这样的整数x叫做同余数，以am+a形式表示的方程叫作同余方程。

例如：求解x除以7余3，即求解7x＝3(mod 7)，则x=7*1+3=10。

二、如何求解同余方程
1、约分同余方程，当m和a互质时，则有x=a*(m^(-1))+a，m^(-1)叫做逆元，记作m^(-1)=y，则x=ay+a。

2、用乘法逆元的原理求解逆元：已知a、m互质，m,y非零且ay ≡1（mod m），则y就是m的乘法逆元。

3、用欧几里得最大公约数求解逆元：已知a、m互质，则用欧几里得最大公约数求解ay+b=1，则y即可作为m的乘法逆元。

4、用因子分解求解：将m分解质因子，将a分解质因子。

然后
将m分解得到质因子，使和a的质因子相乘，计算出ay+b，即可将y 作为m的乘法逆元。

三、应用
同余方程的解法所解决的问题在实际生活中具有重要的应用。

例如，密码学领域，大多数采用RSA加密方案，该方案中，m、a、y这三个值都需要用到同余方程的解法，来保证运算的安全性。

此外，同余方程的解法也可以用于求解模等式组（即统计意义上的等式组），
并广泛应用于偏微分方程、几何有理函数及局部多多边形等数学领域。

四、结论
从上文可以看出，同余方程的解法仍然具有很强的实用性，能够解决数学和工程领域中的许多问题，且解决的结果均有可靠的理论支撑。

同余方程的解法具有重要的应用价值，并且具有广泛的应用前景，值得深入研究。

同余方程的解法同余方程是数论中的重要内容，研究同余方程的解法对于解决一些数学问题具有重要的意义。

本文将介绍同余方程的求解方法及其应用。

一、基本概念在开始讨论同余方程的解法之前，我们先来了解一些基本概念。

1. 同余关系：设a、b、m是整数，如果m能整除(a-b)，即(a-b)是m 的倍数，则称a与b同余，记作a≡b(mod m)。

2. 同余方程：形如ax≡b(mod m)的方程称为同余方程，其中a、b、m是已知整数，x是待求的整数。

二、同余方程的解法解同余方程的关键是找到满足条件的整数解。

下面将介绍三种常见的解法。

1. 试错法：通过尝试不同的整数值，检验是否满足同余关系来求解同余方程。

当方程较简单时，这种方法可以很快得到解。

但对于复杂的方程，试错法并不是一个高效的解题方法。

2. 求模逆法：对于一些特定的同余方程，可以通过求解模逆来得到解。

若a存在模逆，即存在整数a'，使得aa'≡1(mod m)，则同余方程ax≡b(mod m)的解为x≡ba'(mod m)。

3. 扩展欧几里德算法：对于一般的同余方程，可以利用扩展欧几里德算法来求解。

该算法可以求解形如ax+my=gcd(a,m)的线性方程，进而得到同余方程的解。

三、同余方程的应用同余方程是数论的重要工具，在密码学、编码理论、计算机科学等领域有广泛的应用。

1. 密码学：同余方程在RSA加密算法中起到了关键作用。

RSA算法依赖于大素数因子分解的困难性，而同余方程的求解正是对此问题的解答。

2. 编码理论：同余方程可以用于解码、纠错码的设计以及信息传输中的误差检测和纠正等方面。

3. 计算机科学：同余方程在计算机科学中有着广泛的应用，例如在计算机图形学中用于生成伪随机数、在计算机网络中用于数据包分组与重组等。

四、总结同余方程作为数论中的一个重要内容，具有重要的理论和应用价值。

本文介绍了同余方程的基本概念、解法以及一些应用领域。

了解并掌握同余方程的求解方法，对于深入理解数论以及解决实际问题具有重要的意义。

第四章 同余式§1 基本概念及一次同余式作为一个解。

中的一切数，即成立，故把都能使中的任意整数，则剩余类的合理性：若定义的一个解。

叫做成立的一个整数，则是使若称为次数。

，则的同余式。

若称为模，则，其中，设余方程）的求解问题。

课题是研究同余式（同初等数论中的一个基本)(m od )(m od 0)()(m od 0)(2)(m od 0)()(m od )(m od 0)()(m od 0)(m od 0)()(011m a x K m a f a K m a f m x f m a x m a f a n m a m m x f a a x a x a x f m a a n i n n n n ≡≡''≡≡≡≡≡/≡∈+++=∈--+定义2定义1Z Z 。

，解数为，的解为同余式，所以，，的一切整数解为因为不定方程。

有解不定方程有解同余式的任一个解。

是同余式其中，，个解，它们是余式共有。

当此条件成立时，同有解的充分必要条件是，则一次同余式设d d k m dmk x x m b ax t t dmx x b my ax b d b my ax m b ax m b ax x d k m dmk x x d b d m b ax d m a 1,,1,0)(m od )(m od )2(|)(m od )1()(m od 1,,1,0)(m od |)(m od ),(0000-=⋅+≡≡∈+==+⇔=+⇔≡≡-=⋅+≡≡= Z 证明定理。

解时，一次同余式有唯一当)(m od 1),(1)(m b a x m a m -≡=ϕ注同余式的解法1、代入法（适用于模较小时） 。

，得的完全剩余系逐一代入以，，所以同余式有唯一解因为解同余式)17(m od 6171)17,3()17(m od 13≡=≡x x 解例12、公式法（适用于模较小时）。

从而，，，所以同余式有唯一解因为解同余式)11(m od 8656)2()2()3(98981)11,8()11(m od 98491101)11(≡⋅≡⋅-≡-⋅-≡⋅≡⋅≡=≡--ϕx x 解例23、变换系数法 。

第 4 章 二次同余方程与平方剩余 内容 1. 二次同余方程，平方剩余2. 模为奇素数的平方剩余3. 勒让德符号、雅可比符号4. 二次同余方程的求解要点 二次同余方程有解的判断与求解4.1 一般二次同余方程(一) 二次同余方程2ax ＋bx ＋c ≡0（mod m ），（a 0（mod m ））（1） (二) 化简设m ＝k k p p p ααα 2121，则方程（1）等价于同余方程⎪⎪⎩⎪⎪⎨⎧≡++≡++≡++）（）（）（k k p c bx ax p c bx ax p c bx ax αααmod 0mod 0mod 02221221问题归结为讨论同余方程2ax ＋bx ＋c ≡0（mod αp ）， （p a ）（2） (三) 化为标准形式p ≠2，方程（2）两边同乘以4a ，422x a ＋4abx ＋4ac ≡0（mod αp ）()22b ax +≡2b －4ac （mod αp ）变量代换，y ＝2ax ＋b（3）有2y ≡2b －4ac （mod αp ） （4）当p 为奇素数时，方程（4）与（2）等价。

即● 两者同时有解或无解；有解时，对（4）的每个解()p y y mod 0≡，通过式（3）（x 的一次同余方程，且（p , 2a ）＝1，所以解数为1）给出（2）的一个解()p x x mod 0≡，由（4）的不同的解给出（2）的不同的解；反之亦然。

● 两者解数相同。

结论：只须讨论以下同余方程2x ≡a （mod αp ）（5）【例】化简方程7x 2＋5x －2≡0（mod 9）为标准形式。

（解）方程两边同乘以4a ＝4×7＝28，得196x 2＋140x －56≡0（mod 9）配方 (14x ＋5) 2－25－56≡0（mod 9）移项 (14x ＋5) 2≡81（mod 9）变量代换 y ＝14x ＋5得 y 2≡0（mod 9）（解之得y ＝0, ±3，从而原方程的解为x ≡114-(y －5)≡15- (y －5)≡2(y －5)≡2y －10≡2y －1≡－7, －1, 5≡－4, －1, 2（mod 9））(四) 二次剩余【定义4.1.1】设m 是正整数，a 是整数，m a 。

数论是数学中的一个分支，研究的是整数及其性质。

同余方程是数论中的一个重要概念和研究对象。

同余方程是一个关于整数的等价关系，通过同余方程我们可以更好地理解整数的性质和特点。

同余方程的定义非常简单，如果两个整数a和b除以一个正整数m所得的余数相等，即a mod m = b mod m，我们就说a和b对于模m同余，记作a ≡ b (mod m)。

换句话说，如果a和b除以m所得的余数相等，即它们与m的除法不同余，我们就说它们对于模m同余。

通过同余方程，我们可以获得一些有意义的结论和性质。

比如，如果a ≡ b (mod m)，那么a和b对于模m的各种运算都是等价的。

例如，如果a ≡ b (mod m)和c ≡ d (mod m)，那么a + c ≡ b + d (mod m)，a - c ≡ b - d (mod m)，ac ≡ bd (mod m)等等。

这为我们在数论中的一些运算提供了便利，可以通过计算模m的余数来简化运算过程。

同余方程不仅可以用来研究整数的运算性质，还可以在密码学中发挥重要作用。

比如，著名的RSA加密算法就是基于同余方程的。

RSA加密算法使用两个不同的素数p和q作为加密密钥的一部分，通过这两个素数的乘积生成的同余方程来加密和解密信息。

由于质因子分解是一个非常耗时的过程，对于大的质数p和q，求解这个同余方程时需要耗费大量的计算时间，从而保证了RSA加密算法的安全性。

此外，同余方程还可以用来求解一些实际问题。

比如，我们可以通过同余方程来求解一些数学问题中的未知数。

例如，假设我们有一组同余方程x≡ x_1 (mod x_1)，x≡ x_2 (mod x_2)，… x≡ x_x (mod x_x)，其中b1，b2，…，bn和m1，m2，…，mn都是给定的整数。

如果这组同余方程满足一定的条件，我们可以通过一定的方法求解出x的值。

这个过程叫做求解同余方程组，是数论中的一个重要问题。

总之，同余方程是数论中的一个重要概念，通过对整数的模m余数的等价关系进行研究，我们可以得到一些有意义和有用的结果。

同余1. 定义：若整数a,b 被整数m(m≥1)除的余数相同,则称a 同余于b 模m,或a,b 对模m 同余.记为a≡b(modm).余数r:0≤r<1.2. 性质：(ⅰ)a≡b(modm)⇔m|a-b,即a=b+mk,k ∈Z.(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).(ⅲ)若a 1≡b 1(modm),a 2≡b 2(modm)，则a 1±a 2≡b 1±b 2(modm),a 1a 2≡b 1b 2(modm); (ⅳ)设f(x)=a n x n +a n-1x n-1+…+a 1x+a 0,g(x)=b n x n +b n-1x n-1+…+b 1x+b 0是两个整系数多项式,满足a i ≡b i (modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)⇔a≡b(mod ),(m c m ), (ⅵ)若m≥1,(a,m)=1,则存在整数c 使得ac≡1(modm).称c 为a 对模m 的逆或倒数,记为c=a -1(modm);(ⅶ)⎩⎨⎧≡≡)(mod )(mod 21m b a m b a 同时成立⇔≡a b (mod[m 1,m 2]);(ⅷ)若a≡b(modm 1),a≡b(modm 2),且(m 1,m 2)=1,则a≡b(modm 1m 2).3. 剩余类：设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r≤m -1}称为模m 的一个剩余类。

性质：(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i≠j).(ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a≡b(modm).4. 完全剩余系：设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系。

第四章 同余式三、解答题1、设(,)1a m =，k 与m 是正整数，又设0(mod )k x a m ≡，证明同余方程(mod )kx a m ≡的一切解x 都可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡。

解：设1x 是0(mod )kx a m ≡的任意一个解，则一次同余方程01(mod )yx x m ≡有解y ，再由001()(mod )k k k k ky a y x yx x a m ≡≡≡≡得1(mod )ky m ≡，即1x 可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡； 反之，易知如此形式的x 是(mod )kx a m ≡的解。

2、解同余方程组()()31mod1047mod15x x ≡⎧⎪⎨≡⎪⎩解：这同余方程组的解与同余方程组()()()()31mod 2,31mod5,47mod3,47mod5x x x x ≡⎧⎪≡⎪⎨≡⎪⎪≡⎩的解相同，但第二个同余方程()31mod5x ≡可化为()2mod5x ≡, 第四个同余方程()47mod5x ≡可化为()2mod5x ≡-, 与()2mod5x ≡矛盾，所以原同余方程组无解.3、设素数2p >,求同余方程()21mod lx p ≡的解 解：同余方程可写为()()()110mod lx x p-+≡由于()1,1|2x x -+,所以上式等价于()10mod lx p -≡或()10mod lx p+≡因此，对任意的1l ≥解为()1,1mod l x p ≡- 解数为2.4、求同余式32()4560(mod 27)f x x x x =-+-≡ 解：∵()0(mod3),()0(mod3)f x f x '≡≡无公解∴20有唯一解0(mod3)x ≡以13x t =代入()0(mod9)f x ≡得1(0)3(0)0(mod9)f t f '+≡ 但(0)3(mod9)f ≡，(0)5(mod9)f '≡故1360(mod 9)t +≡，2120(mod 3)t +≡，11(mod 3)t ≡ 因此12213,39t t x t =+=+是()0(mod9)f x ≡的唯一解将239x t =+代入()0(mod 27)f x ≡得2(3)9(3)0(mod 27)f t f '+≡ 但(3)0(mod 27)f ≡，(3)8(mod 27)f '≡故2890(mod 27)t ⋅≡，280(mod 3)t ≡，20(mod3)t ≡设2333,327,3(mod 27)t t x t x ==+≡是()0(mod 27)f x ≡的唯一解。

§4同余式1 基本概念及一次同余式定义 设()110nn n n f x a x a xa --=+++ ，其中()0,0,1,,i n a i n >= 是整数，又设0m >，则()()0mod f x m ≡ （1）叫做模m 的同余式.若()0mod n a m ≡，则n 叫做同余式（1）的次数. 如果0x 满足()()00mod ,f x m ≡则()0mod x x m ≡叫做同余式（1）的解.不同余的解指互不同余的解.当m 及n 都比较小时，可以用验算法求解同余式.如 例1 同余式()543222230mod 7x x x x x +++-+≡仅有解()1,5,6mod 7.x ≡例2 同余式()410mod16x -≡有8个解()1,3,5,7,9,11,13,15mod16x ≡例3 同余式()230mod 5x +≡无解。

定理 一次同余式()()0mod ,0mod ax m a m ≡≡ （2）有解的充要条件是(),.a m b若（2）有解，则它的解数为(),d a m =. 以及当同余式（2）有解时，若0x 是满足（2）的一个整数，则它的(),d a m =个解是()0mod ,0,1,,1mx x k m k d d≡+=- （3） 证 易知同余式（2）有解的充要条件是不定方程ax my b =+ （4）有解. 而不定方程（4）有解的充要条件为()(),,.a m a m b =-当同余式（2）有解时，若0x 是满足（2）的一个整数，则()0mod ,0,1,, 1.m a x k b m k d d ⎛⎫+≡=- ⎪⎝⎭下证0,0,1,,1mx k k d d +=- 对模m 两两部同余. 设 ()00mod ,01,1m mx k x k m k d k d d d ''+≡+≤≤-≤≤-则()mod ,mod ,.m m m k k d k k d k k d d d ⎛⎫'''≡≡= ⎪⎝⎭再证满足（2）的任意一个整数1x 都会与某一个()001mx k k d d+≤≤-对模m 同余. 由()()01mod ,mod ax b m ax b m ≡≡得()101010mod ,mod ,.a a m m ax ax m x x x x d d d d ⎛⎫⎛⎫≡≡≡ ⎪ ⎪⎝⎭⎝⎭故存在整数t 使得10.mx x t d=+由带余除法，存在整数,q k 使得 ,0 1.t dq k k d =+≤≤-于是()()100mod .m mx x dq k x k m d d=++≡+故（2）有解时，它的解数为(),d a m =. 以及若0x 是满足（2）的一个整数，则它的(),a m 个解是()0mod ,0,1,,1mx x k m k d d≡+=- (5) 例1求同余式 ()912m o d 15x ≡ （6）的解. 解 因为()9,15 3.=又因312,故同余式（6）有解，且有三个解.先解()5mod 43≡x , 得().5mod 3≡x 故同余式（6）的三个解为()158mod15,0,1,2.3x k k ≡+= 即 ()3,8,13m o d 15.x ≡ 例2 求同余式 ()6483mod105x ≡ （7）的解. 解 ()831,1105,64= ,同余式有一个解. 将同余式表为21051921916152161054716476418864105836483+≡≡≡+≡≡≡+≡≡x ().105mod 622124≡≡例3 解同余式 325x ≡ 20 (mod 161) 解 ()1161,325= 同余式有一个解, 同余式即是3x ≡ 20 (mod 161) 即.161203y x +=解同余式 161y ≡ -20 (mod 3)， 即2y ≡ 1 (mod 3)， 得到y ≡ 2 (mod 3)，因此同余式的解是x ≡3161220⋅+= 114 (mod 161). 例4 设(a , m ) = 1，并且有整数δ > 0使得 a δ ≡ 1 (mod m )， 则同余式(2)的解是x ≡ ba δ - 1 (mod m ). 解 直接验证即可.注：由例4及Euler 定理可知，若(a , m ) = 1，则x ≡ ba ϕ(m ) - 1 (mod m ) 总是同余式(2)的解.注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用. 例5 解同余方程组⎩⎨⎧≡-≡+)7(mod 232)7(mod 153y x y x (8) 解 将(8)的前一式乘以2后一式乘以3再相减得到19y ≡ -4 (mod 7)，5y ≡ -4 (mod 7)， y ≡ 2 (mod 7).再代入(8)的前一式得到3x + 10 ≡ 1 (mod 7)，x ≡ 4 (mod 7)即同余方程组(8)的解是x ≡ 4，y ≡ 2 (mod 7).例6 设a 1，a 2是整数，m 1，m 2是正整数，证明：同余方程组⎩⎨⎧≡≡)(mod )(mod 2211m a x m a x (9) 有解的充要条件是a 1 ≡ a 2 (mod (m 1, m 2)). (10)若有解，则对模[m 1, m 2]是唯一的，即若x 1与x 2都是同余方程组(9)的解，则x 1 ≡ x 2 (mod [m 1, m 2]) (11)解 必要性是显然的.下面证明充分性.若式(10)成立，由定理2，同余方程m 2y ≡ a 1 - a 2 (mod m 1)有解y ≡ y 0 (mod m 1)，记x 0 = a 2 + m 2y 0，则x 0 ≡ a 2 (mod m 2)并且x 0 = a 2 + m 2y 0 ≡ a 2 + a 1 - a 2 ≡ a 1 (mod m 1)，因此x 0是同余方程组的解。