一次同余式与一次同余式组的解的讨论

a = −1 p
Legendre符号的几条重要的性质（p是奇素数）： ①若a≡b(mod p), 则 ≡ p不能整除 不能整除a, ②若p不能整除a, 则
a b = . p p
a2 p =1
定理 1.1.1 设(a,m)=1, m>0, 则 ax≡b(mod m) ≡ 恰有一解, 恰有一解, 且 x≡baϕ(m)-1(mod m) ≡ 定理 1.1.2 设aﾄm, 则 ﾄ ax≡b(mod m) ≡ 有解的充分必要条件是:(a,m)|b. 若有解， 若有解， 有解的充分必要条件是 则共有d个解 个解. 则共有 个解
p −1 a 2
≡ 1 (mod p )
(2). a是模 的非平方剩余的充要条件是 是模p的非平方剩余的充要条件是 是模
a
p −1 2
≡ − 1 (mod p )
勒让德(Legendre)符号
为了简化“x2≡a(mod p)有解”这一较长 a 的说法, 今引人勒让德(Legendre)符号 ,其 p 定义如下:
•雅各比符号可以看作勒让得符号的推广。
定理3.1 是奇素数, 不能整除a, 定理 设p是奇素数 若p不能整除 则 x2≡a(mod p)恰 是奇素数 不能整除 恰 有两解或无解. 有两解或无解 定理3.2（欧拉判别条件）设p是奇素数 (a,p)=1, 则 定理 （欧拉判别条件） 是奇素数, 是奇素数 (1). a是模 的平方剩余的充要条件是 是模p的平方剩余的充要条件是 是模
思考： 思考：求
(1) 21000000 (mod 77) (2) 31213 (mod 667)
3 二次同余式和平方剩余
比一次同余式更复杂的是二次同余式 Ax2＋Bx＋C≡0 (mod m) ＋ ≡ 其中模p为奇素数的基本二次同余式最实用 为奇素数的基本二次同余式最实用， 其中模 为奇素数的基本二次同余式最实用，即 x2≡a(mod p), (p,a)=1 定义3.1 的正整数, 定义 设m≥2的正整数 若二次同余 的正整数 x2≡a(mod m), (m,a)=1 有解, 则称a是模 的二次剩余(或叫平方剩余 若无解, 有解 则称 是模m的二次剩余 或叫平方剩余); 若无解 是模 的二次剩余 或叫平方剩余 则称a是模 的二次非剩余. 是模m的二次非剩余 则称 是模 的二次非剩余 例如： ， ， 是模 的平方剩余。 是模7的平方剩余 例如：1，2，4是模 的平方剩余。 因为:6 即解x=6;… 因为 2 ≡1 (mod 7),即解 即解 同样的问题：解的存在性和如何求解？ 同样的问题：解的存在性和如何求解？

一次同余方程组解法同余方程组是数论中常见的问题，解决同余方程组的方法有很多种，其中一种常见的方法是一次同余方程组解法。

本文将详细介绍一次同余方程组解法的原理和步骤。

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

一次同余方程组是指多个一次同余方程组成的方程组。

解决一次同余方程组的关键在于找出一个整数 x，使得该方程组中的每个方程都成立。

一次同余方程组解法的步骤如下：步骤一：将一次同余方程组化简为最简形式。

对于形如ax ≡ b (mod m) 的方程，可以通过对 a 和 b 取模 m，得到等价的方程a'x ≡ b' (mod m)，其中 a' = a (mod m)，b' = b (mod m)。

将方程组中的每个方程都化简为最简形式。

步骤二：使用欧几里得算法求解最大公约数。

对于一次同余方程组，如果方程组中每个方程的模 m 两两互质，则可以使用欧几里得算法求解最大公约数。

如果最大公约数为 1，则方程组有解；否则，方程组无解。

步骤三：使用中国剩余定理求解方程组的解。

如果方程组中每个方程的模 m 两两互质，并且方程组有解，则可以使用中国剩余定理求解方程组的解。

中国剩余定理的具体步骤如下：3.1 计算模数的乘积。

将方程组中每个方程的模数相乘，得到模数的乘积 M。

3.2 计算模数的乘积除以每个模数的商。

对于每个方程的模数 m，计算 M/m 的商，记为 Mi。

3.3 计算模数的乘积除以每个模数的商对应的模反元素。

对于每个方程的模数 m，计算 Mi 在模 m 下的模反元素，记为 ti。

3.4 计算解的线性组合。

将每个方程的解 x 乘以 Mi 和 ti 的乘积，再对 M 取模，得到方程组的解 y。

3.5 求解最小非负整数解。

将方程组的解 y 对 M 取模，得到最小非负整数解 x。

通过以上步骤，即可得到一次同余方程组的解。

需要注意的是，在使用一次同余方程组解法时，应确保方程组满足两个条件：每个方程的模数两两互质，方程组有解。

140+63 233+30 2×105 =23 =233
2015/11/17
为什么啊？
19
问题1：今有物不知其数，三三数之剩二，五五数之 剩二，七七数之剩二，问物几何。 x-2是3、5、7的公倍数。 问题2：今有物不知其数，三三数之剩二，五五数之 剩三，问物几何。
3|x 2, 5|x 3 x 3k1 2 5k2 3
2015/11/17
13
例3 解同余方程6x 7 (mod 23)。
m ax b (mod m) a1 x b[ ](mod m ) a
解 由定理4，依次得到
6x 7 (mod 23) 5x 73 2 (mod 23)
3x 24 8 (mod 23)
则(1)的解为
x ai M i M i (mod m )
i 1
k
(2)
其中，整数Mi（1 i k），满足MiMi 1 (mod mi).
2015/11/17
22
证明： 由 (Mi, mi) = 1，利用辗转相除法可以求出 Mi与yi ，使得 MiMi yimi = 1，
rm sm rm sm 注：x0 x0 (mod m ) (mod m ) r s d d d d
解方程(2)的方法： 先求出相应不定方程 ax my = b的一个特解
m 再代入 x x0 r (mod m ), 0 r d 1. d
2015/11/17
（3）设m是素数，f(x) = g(x)h(x)，g(x)与h(x)都是 整系数多项式，又设x0是同余方程(1)的解， 则x0必是同余方程 g(x) 0 (mod m) 或 h(x) 0 (mod m)的解。

ｍ ａ ｘ ｂ［ ］（ ｍ ｏ ｄ ｍ） ． １ ０ ≡－ ａ
因为

ｍ ｍ ＝ ａ［ ］ ＋ａ １， ａ
也即
ｍ］ ［ ， ａ １ ＝ ｍ －ａ ａ
从而有
ｍ ） ｍ （ ， ｍ －ａ［ ］ ｘ ｂ［ ］（ ｍ ｏ ｄ ｍ） ０ ≡－ ａ ａ
所以
ｍ ｍ ｘ ｂ［ ］（ ｍ ｏ ｄ ｍ） ． －ａ［ ］ ０ ≡－ ａ ａ
； 收稿日期 ： 修改日期 ： ２ ０ １ ０ ０ ４ ０ ５ ２ ０ １ ２ ０ ６ ０ ４ － － － － ， 作者简介 ： 刘耀斌 （ 男， 山东德州人 ， 硕士 ， 讲师 ， 主要从事代 １ ９ ６ ８－） ： 数学方面的研究 ． Ｅ ｍ ａ ｉ ｌ ｌ ｂ ｃ ｈ ８ ９ ８ ５＠ｓ ｏ ｈ ｕ． ｃ ｏ ｍ ｙ ｇ
） ， ， 对 于一次同余式 （ 若ｄ ＝ （ 且ｄ｜ 则 １ ａ， ｍ） ｂ， ， ， ， 将 ａ ｂ ｍ 同除以ｄ 总可以化为如下的一次同余式 ， ， ａ ｘ ≡ｂ （ ｍ ｏ ｄ ｍ） ａ ０ （ ｍ ｏ ｄ ｍ） （ ａ， ｍ）＝ １． （ ） ２
ａ
ｍ） φ（
， ａ ｘ ≡ｂ （ ｍ ｏ ｄ ｍ） ｍ） １ － φ（ （ ， ｘ ≡ｂ ａ ｍ ｏ ｄ ｍ）
［ １］ （ 定理 １ Ｅ ｕ ｌ ｅ ｒ定理 ） 设 ｍ 是大于 １ 的整数 ，
（ 则 ａ， ｍ）＝ １， （ ） １
φｍ ， ａ ｍ ｏ ｄ ｍ） ≡１ （ 其中 φ（ ｍ）是正整数 ｍ 的欧拉函数值 ． 因为 （ 由最大公因数的性质可知 ａ， ｍ）＝ １， ｍ） φ（ （ ， ａ ｍ）＝ １，
又因为
ｍ］ （ ［ ， ｍ）＝ （ ｍ， ａ ＝ １， １） ａ
于是 ， ｘ０ ≡－ｂ （ ｍ ｏ ｄ ｍ） －ａ （ ） （ ） 也即 ｘ ≡ ｘ ｏ ｄ ｍ 是同余式 ６ 的解 ． ０ ｍ

本科毕业论文题目：同余方程的解法学生姓名：学号：专业：数学与应用数学班级:指导教师：二〇一年四月摘要：本文论述了同余方程的基本概念及同余方程的一些基本性质与解法，主要对一次同余方程的解法进行了探讨，特别是对一次同余方程的欧拉定理算法，欧几里德算法等七种解法进行了比较与分析，并介绍了同余方程组、孙子定理、素数模的同余方程，模p 的同余方程的解法。

关键词：同余同余方程孙子定理Abstract：This paper mainly discusses the basic concepts of congruence equations and congruence equation some of the basic nature of solution,and highlights the Remainder Theorem,solution of the congruence equation,mod p congruence equation solution,congruence equation of primes mode solution,etc.Key words:Congruence Congruence equation Remainder Theorem目录引言 (1)1.同余与同余方程的基本性质 (2)1.1 同余的概念与基本性质 (2)1.2同余方程的概念与性质 (3)2.一次同余方程的解法 (4)2.1 ()a=的情况 (4), m 12.2 ()=≠的情况 (7),1a m d3.同余方程组的解法 (8)3.1简单同余方程组的解法 (8)3.2 孙子定理 (9)4.高次同余方程的的解法 (11)4.1素数模的同余方程 (11)4.2模pα的同余方程 (12)总结： (17)参考文献 (18)致谢： (19)引言对于同余方程的解法国内外的数学家们均对其做出了非常全面与细致的研究。

一次同余式组解法摘 要:同余式定义 同余式组有解条件 同余式组解法关键词:同余式;孙子定理;同余式组有解条件;同余式组解法引言在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数.例如问我们现在几点钟，就是用24去除某一个总的时数所得的余数.又如问现在是星期几,就是问用问7去除某一个总的天数所得的余数,同是几点钟或同为星期几,常常生活中有所同样的意义.这样,就在数学中产生了同余的概念.1预备知识定义 1 若用f(x)表示多项式011a x a x a n n n n +++-- ,其中i a 是整数;又设m 是一个正整数, 则 f(x)≡0(mod m) (1) 叫做模m 的同余式.若0(mod m),则n 叫做(1)的次数.2 若a 是使f(a) ≡0(mod m)成立的一个整数,则 x ≡a (mod m) 叫做(1)的一解.定理 1 一次同余式 ax ≡b(mod m)，a 不同余零模m (2)有解的充分与必要条件是 (a ,m)|b. 且若(2)有解，则(2)的解数（对模m 来说）为 d=(a ,m).证明 易知(2)有解的充分与必要条件是 ax-my=b 有解.从而由第二章第一节定理2即知(2)有解的充分与必要条件是(a ,m)|b.设d=(a ,m).若(2)有解,则由第二章第一节定理1知适合（2）式的一切整数可以表成 x=1m t+0x ,1m =dm ,t=0,1,-1,2，-2,… 此式对模m 来说,可以写成 x ≡0x +k 1m (mod m),k=0,1, …,d-1.(3) 但0x +k 1m ,k=0,1, …,d-1 是对模m 两两不同余的,故（2）有d 个解,即(3). 证完 定理2(孙子定理) 设1m ,2m ,…,k m 是k 个两两互质的正整数,m=1m 2m …k m ,m=i M i m ,i=1,2,…,k,则同余式组(1)的解是X ≡()m b M M b M M b M M k k k mod '22'211'1+++ , 其中i i M M '≡1(mod i m ) i=1,2,…,k.证明 由(i m ,j m )=1,i ≠j 即得(i M ,i m )=1,故有第一节定理即知对每一i M ,有一'i M 存在,使得 i i M M '≡1(mod i m ).另一方面m=i M i m ,因此j m |i M ,i ≠j,故 ()i i i i j j k i j j m b M M b M M mod ''≡∑= 即为(1)的解. 若21,x x 是适合(1)式的任意两个整数，则 (),,,2,1,mod 21k i m x x i =≡因(i m ,j m )=1,于是),(mod 21m x x ≡故(1)式的解只有(2).证完 一次同余式组解法 1 孙子定理2 算术解法例题 1有三位数的奇妙数字.加上1后可被2整除,加上2后可被3整除,加上3后可被4整除,加上4后可被5整除,加上5后可被6整除,加上6后可被7整除.试问该数是多少?解 解法1(孙子定理) 设该数为x,则由题意有一次同余组 )7(mod 06),6(mod 05),5(mod 04),4(mod 03),3(mod 02),2(mod 01≡+≡+≡+≡+≡+≡+x x x x x x又因).6(mod 1),4(mod 1),2(mod 1≡≡≡x x x而[],126,4,2=故有).12(mod 1≡x则有,1+105t=12s+1,有12s-105t=0.解4s-35t=0,有s=35a,t=4b,则x 可表示为x=420a+1.又所求数为三位数,则x=421或x=841.解法 2 （算术解法）能被由2到7为止的任何数均可整除的数为 2*3*4*5*6*7=5040 .但是,其中4可能被2整除,6可被2和3整除,故 3*4*5*7=420 也具有相同的性质.我们再来看1,它加上1的数可被2整除,加上2的数可被3整除,加上3的数可被4整除,加上4的数可被5整除,加上5的数可被6整除,加上6的数可被7整除.于是,1加上420的若干倍的数也具有相同的性质, 故在3位数中有1+420=4211+420*2=841这两个数,就是所求的数. 此外,末尾的数字为1可由x+1=偶数x+4=5的倍数导出.结论一次同余式组解法可由多种方法解得,孙子定理可以求解但较为繁琐其过程有时还需利用二元一次不定方程求解.而利用算术求解则较为简单.故在求解时应首先观察一次同余式组特征性质以便选取简单方法求解.参考文献：(1)(闵嗣鹤,严士键).初等数论.高等教育出版社,2003(2)[]日中村义作著.鲍重光译.数学谜题的20种解法.北京理工大学出版社,2007。

§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是同余方程组的解。

同余方程1997年第3期高等函授(自然科学版)同余彭敦刚(湖北大学)同余方程是初等数论中一个重要的问题.其内容包括一次同余方程(组),高次同余方程,二次同余方程等.如去掌握这些内容呢?下面就其特征分述如下,供复习时参考.l一次同余方程(组)在这个问题中,主要讨论的是含有一个未知数的一次同余方程和含有一个未知数的一次同余方程组.1.1一次同余方程如果口,b都是整数,而T/l是一个正整数,当口≠0(modm)时,我们把口+6三0(modm)(1)叫做模.的一次同余方程.对这一类方程的求解,主要应该掌握:设有方程(1),当(口.)一1时,则方程(1)有唯一的解;--6t~(一.b(modm)(2)当(口,)=>1时,则方程(1)有解的充分和必要条件是}b,这时方程(1)有d个解是三+.(modm),t=O,1,…,一1(3)这里x~a(modm)是把第二种情形化为第一种情形时,所得到的唯一解.要注意的是:对于第一种情形,在实际求解时,不常用公式,因为用公式一般比较麻烦,应该灵活地运用已有的知识去寻找新的简便的求解方法.后面将举例说明.对于第方程李德水(武汉电视大学)二种情形是把它化成第一种情形求解来处理的,求出唯一解后,再代入公式(3)求得它的d个解.对于方程(1)除了上述方法求解外.主要的还有如下两种解法.第一种解法因(口,z)一1,由(n,)一1的充分必要条件:存在s,t,使口s+bt一1知. 必有二数,t,使-口s+mt1即口s三I(modm)故由asx~bs(modm),得三(modm)为同余方程(1)的解.第二种解法先把方程(1)写成;一b(mod0)一——L,n的形式,然后用与z互质的整数陆续乘以右端的分子和分母,目的在于把分母的绝对值变小,直到变成1为止.下面举例说明上述三种解法的应用.例1解方程286x~121(mod341).解法1因(286,341)一11,11I121,故26三11(mod31)(*)因为口一26,6—11,(31)一30故方程(*)的解是;一n…一'6三一261.?11三4(mod31)将三4(mod31)代入公式(3),因此,原方程的解是z_二4.35.66.97.】28,】59.于是z[N(E+)]≥nl[EN+]:z[En]>2()>2()收稿日期:1997一O4—29这与前面",[n(E+jt)]<1",(』)产生矛盾故命题得证.原方程有解,并且有11个解. 将原方程写成1997年第3期高等函授(自然科学版)25 190,221,252,283,314(mod341)解法2由(286,341)一ll得到(26,31)一1,这样就存在两个整数,t,使26s+3It一1由观察方法可知:26?6+31?(一5):1即26?6兰1(mod31)又由同余性质,(*)式可写成26?6x=11?6(mod31)即x-~-66=4(mod31)将兰4(mod31)代入公式(3)即可得到原方程的解.2-三4,35,66,97,128,159,190,221,252,283,314(rood341)解法3把(*)式写成兰11三兰一4三4(m.d31)1561—26……将兰4(rood31)代入公式(3)即可得到原方程的解:兰4,35,66,97,128,1S9,190,221,252,283,314(mod341)在此应该注意的是:以上3种解法各有各的优点.在模很大时,第1种解法较好;而当模不太大时,第2种解法比较简捷;若模较小时.第3种解法较方便.总之,在解题时,要根据具体情况选择其方法.1.2一次同余方法组在这里所讨论的一元一次同余方程组,主要的是形如f~2.61.2?,)j.2?;6(modm.)的同余方程组.在我国古代的孙子算经》里就提出了这种形式的问题,并且很好地解决了.这个问题的解法主要依靠下面的定理.定理设11ll,11l?,…川z女是是个丽两互质的正整数,z一Ⅲ2…11l女.11l一111M,i一1, 2,…,正,则同余方程组(4)对于模z一z.?兰-+.+..?+b(modz)(5)这里,三1(m.d).x=l(mod7);再由兰1(modz)可以求得261997年第3期高等函授(自然科学版)高次同余方程分两种情形,一是质数模的高次同余方程,另一是合数模的高次同余方程,而合数模高次同余方程是把它化成质数模高次同余方程进行处理的(这里应掌握转化方法).对这两种类型的高次同余方程应掌握:1)如何对()进行化简;2)求解的基本方法:将P的完全剩余系10,±1,…,±÷(p一1)中的每一个数一一代厶人进行验证的方程;3)在合数模的高次同余方程中有一种特殊的质数幂模的高次同余方程,这种类型的方程在求解时应严格按照求解步骤进行.例3解同余方程6x.+27x+17x+20三0(mod30)解由30—5×6,所以同余方程与同余方程组f6+27x+17+20三0(mod5)(6)l6+27x+17+20三0(rood6)(7)等价.直接验算得:(6)式有3个解:三0,1,2(mod5);(7)式有2个解:三一1,2(mod6).故原方程有3×2:6个解.设三b(moA5),三62(mod6),其中bl一0,1,2,b2一一1,2.由孙子定理可得原方程的解丁三6bl+25b:(mod30)以b一0,1,2,b:一一1,2代入上式,即可得原方程的6个解是-『三三三2,5,11,17,20,26(mod30)当然也可把30—2×3×5,得到三个方程组成的方程组与原方程等价,同样得到原方程的6个解,请读者自行完成.3二次同余方程二次同余方程的求解问题是二次同余方程与平方剩余的一个中心问题.这个问题中也是分质数模二次同余方程和合数模二次同方程两种情形来讨论的.3.1奇质数模的二次同余方程的求解设.三口(modp),户,P是奇质数(8)当(詈)一1时,说明n是P的平方剩余,方程(8)有解.这时方程(8)的解分下面4种情形:p=l(mod8),pz3(mod8)p=5(mod8),p=7(mod8)当p=3或户三7(mod8)时,方程(8)有解,即三±口寺'p(mod)当p=5(mod8)时,若口}(p-1)三1(modp),则方程(8)的解是三±口音'p.(mod)若口}(p--1)三一1(modp),则方程(8)的解三±2}(p—1).口告(p+3(mod3)例4求同余方程三19(mod31)的解.解因为(19)一1,所以同余方程有解.又因为31=8×3+7,所以三±19}.件"三三三±19三±19(mod31)故原同余方程的解是三士19(mod31)例5求方程3x.+7x一6三0(modl3)的解.解因为(3,13)一1,所以3+13N一1.因此,3三1(modl3).由M三9(mod13), 以9乘原方程两边得.r.+63.r一54三0(mod13)上式中63不是偶数.因此上式可以写成.7/-?+(63+13)一54三0(mod13)即3/0+24:r一2三0(mos13)配方得(j-+12)三12+2-----1463(mod13) 令—J'+12即y三3(rood13)又()一1,所以上面方程有解.又13—8X1+5,所以3{'.一三3三1(mod13),上面方程1997年第3期高等函授(自然科学版)27的解为兰_--4-3言'...兰±3.三±9(modl3)将代入—+12,即得z=---5,10(modl3)故原方程的解为z三5,10(mod13)在这里要说明的是,在求z.三口(modp)方程解时,首先要用()符号进行判断,看该p方程是否有解;其次如果该方程有解,再用P 三3,户兰5,p~7(modp)判断,才能确定该方程其解的形式;再次,如果二次同余方程是以口.+bx+c三0(modp)形式出现的,要把它化成:兰(modp)形式,再按前面二步进行求解.上面我们就户三3,户兰5,户三7(modp) 三种情形进行了介绍,但对P三1(modp)情形未进行讨论.这里要说明的是这种情形要比前面三种情形要复杂得多,没有一般结论, 请在复习时按书上的要求进行复习.3.2合数模二次同余方程在这里要明确合数模二次同余方程z:三Ⅱ(modm),(口删)一1,竹l为合数(9有解的条件及解的个数.对于这类方程我们是先把写标准分解形式,即17'1—2opi'…声.由定理:若一I'H!…I'H,且,…,17'1女是k个两两互质的jE整数,则同余方程厂()~O(modm)与方程组f(x)~O(modm,)一1,2,…,是等价.有解的必要和充分条件是z.三口(mod2.)z.三口(modt),一1,2,…,k(10)有解,并且在有解的情况下,(9)的解数是(1O)的解数的积.在这里主要是讨论形如z.三口(modp.),a>0且(口,户)一1(11)的方程,在求解方程(11)时,所用的方法是质数幂模的高次同余方程求解方法.例6解方程z.~7(mod27).解因7三7r兰1(rood3),即.三1(mod3)有解为三1(mod3).再从(1+3t1).三7(rood3.)得6tI三6 (mod3.),因此t三1(mod3).于是1+3t,三4(mod3:)是三7(mod3:)的解.又从(4+32t2)三7 (mod30)得8t2三一1(mod3)即可得t2E1(mod3),所以z三4+3zt2三13(mod3)是所给方程的一个解.于是所求方程的解是z三±13(mod27)至于同余方程z0三口(moda),口>0且(2,")=1的求解,按照书上要求即可.(上接第17页)有nt肌B.E一exp[Sc肿B.E/k3(31)将(29)式的代入(31)式,并令s一Nk(1nZ一』9茄nzI)(32)(这是未考虑波函数的对称性时算得的熵,即玻耳兹曼系统的熵)便可得到c¨B,E一exp[S【肿B.E,/忌]一【,,,'^exp[丢(+是ln1j一斫es'Ik—(33)可见(3)式中的因子1/Ⅳ!也来源于波函数的交换对称性.参考文献l曾谨言.量子力学(上册).北京:科学出版社1981:189—2012R.K.帕斯里亚着.湛垦华,方锦清译.统计力学(上册),北京:商等教育出版社1985:1743Kerr:mHuang,StatisticalAlechanics?Ne'u~Y ork:Jobnuih:3rSons.Inc.1963:213。

关于a x≡b(modm)的解法1．当（a,m）≡1时：(1)若a,b<m,(a,b)=1且模数较大，可取余，将a变小，然后求出解。

eg:121x≡87(m0d257) 因为(121,257)=1,所以有一个解，x=194(mod257)(2)若a,b<m,(a,b)= 1且模数较小，用欧拉公式；eg: 7x≡5(mod10) 因为（7,10）所以有一个解。

（3）若（a,b ）=1,且a,b中至少有一个大于m，利用同余知识，将a,b化小再用（1）（2）式去解（4）若（a,b），≠约去两端的公因数；再用（1）（2）（3）式去解。

1Eg:58x≡87(mod47)2当（a,m）=d>1时:用d去除同于式，再用（a,m）=1去解<1>同余取倍法：（期刊-核心期刊和田师专科学校学报）JOURNAL OF HOTAN TEA CHERS COLLEGE 2009年第03期<2>一次同余式的初等变换解法：（山西大学学报：自然科学版）——袁虎延<3>一次同余式的逐级满足法<4>观察法解一次同余式<5>Euler定理解一次同余式<6>把同余式化为不定方程的解法<7>减少模数的方法解一次同余式<8>欧几里得法解一次同余式<9>分式法解一次同余式<10>威尔逊定理算法解一次同余式<下面仔细介绍>代数/数论/组合理论/《.黑龙江科技信息》2008年19期》摘要一次同余式解法的特点及其分析——作者：李婷只讨论（a,m ）=1时，同余式ax ≡b(modm)有以下七种解法（一）（1）观察法：在模m 的完全剩余系0,1，、、、，m-1中考虑同余式的解1.，当m 较小时，可用观察法，直接快速的得出方程的解eg 2x ≡1(mod3) 因为（2,3）=1所以有一个解，x ≡2(mod3)为其解2．当系数较大时，可用同余性质 ，将同余式系数减小，而且用带余除法定理，保证系数在一个固定范围内作为模m 的系数，进而用观察法，可快速得到方程的解。

1 一次同余方程组同余是数论中的一个重要运算，在许多领域都有重要的应用t。

关于同余方程的解法已有一些基本的结论。

对于一次同余式的解的问题，已有下面的结果：ax≡b（modm），a≠0（modm）（1）定理1：同余式（1）有解的充分与必要条件是gcd（a，m）/b，且在有解的情况下，方程的解为：即方程的解数为gcd（a，m），其中x0是同余式（1）的一个特解。

本文基于同余的简单性质，主要讨论的是k阶一次同余方程的解法。

在我国古代的《孙子算经》里已经提出了这种形式的问题，并且得到了验证。

这就是著名的中国剩余定理。

a1x≡b1（modm1），a2x≡b2（modm2），…，akx≡bk（modmk）定理2：（中国剩余定理[1]）：设m1，m2，…，mk是k个两两互质的正整数，令m=m1m2…mk，且m=miMi，i=1，2，…，k，若a1=a2=…=ak=1，則同余式（1）的解是：X=M1'M1b1+M2'M2b2+…+Mk'Mkbk（modm）其中M1'M1=1（modmi），i=1，2，…，k。

显然，上述中国剩余定理中a1=a2=…=ak=1和m1，m2，…，mk是k个两两互质的正整数，这两个条件比较苛刻，很多情形下难以满足。

通过因子分解等手段可以将绝大部分的一次同余方程组化为满足中国剩余定理要求的形式[2]，一次同余方程组的阶数增大，导致计算的复杂程度增加。

本文主要讨论一般情形下的同余方程组解法。

2 中国剩余定理的不足之处中国剩余定理在数论中是个很重要的定理，应用于许多领域。

但是，若从解同余方程组的角度来看，也存在一些不足之处，并非首选。

文章就中国剩余定理的不足展开探讨，体现在如下3个方面。

2.1 标准化问题在前面已经提到，求解同余方程组（1），首先要求各个元素ai（mod mi）的逆元，化成满足中国剩余定理所要求的形式，即：x=a1-1b1（modm1），x=a2-1b2（modm2），…，x=ak-1bk（modmk）根据欧几里得算法或是辗转相除法得到：若gcd（ai，mi）=1，则ak-1存在。

一
其中 （ ｍ）是正 整数 ｍ 的欧 拉 函数 值．
因为 （ ， 口 ｍ）一 １ 由最大 公 因数 的性 质可 知 ，
（ 口 ， ｍ）一 １ ，
次 同余 式 （ ）有解 的充 要 条 件 是 （ ， １ ｎ ｍ）ｌ ， ｂ
并 且在有 解 的情况 下 ， 解 的个数 为 ｄ一 （ ， （ 其 ｎ ｍ） 对
模 ｍ 来 说 ）２ ＿ ｌ． ］ 所 以 以 下 三 式
对 于一 次 同余 式 （ ） 若 ｄ一 （ ， ， ｄ Ｉ ， １， ｎ ｍ） 且 ｂ 则
ａ ２三 ｂ （ ｏ ３ ｍ ｄ仇 ） ， 口 ‘ ｚ 三 ｂ 一 （ ｄ７ ， ａ ‘ ｍｏ ） ｚ 三 ｂ Ｐ ｍｏ ａ‘ 一 （ ｄ ｍ），
ａ 三 ｂ（ ｄ ） ． Ｔ ｍｏ ，ｎ ≠ ０ （ ｏ ） ｍ ｄ （） １
２ 利 用 欧拉 定 理 求解
定 理 １ Ｅ ｌｒ （ ｕｅ 定理） ［
（ ）＝ 口， ＝ 贝 ＝１， ０
ｎ‘ ’三 １ （ ｄ ）， ｍｏ
设ｉ ｎ是大 于 １的整数 ，
的 同余式 ， 为一次 同余式 ． 称
１ｏ ６ｒ三 １ （ ｏ １ ８ ｒ ｄ １ ）， ｏ
５ 兰 ７（ ｏ １ ｘ ｏ ｒ ｄ １ ），
三 ２ （ ｏ ． ｍ ｄ ３）
（ 模 １ 来说 ） 依 次对 同余式 进行 等价变 形 ， 对 １ ． 得
取 ｙ一 ２， 知 ３Ｉ １ １ 可 （６ ×２ ２ ） 因此所 给 同余 式 ＋ Ｏ，
以下仅 就形 如（ ）的一次 同余 式 进行讨 论 ． ２
文 ［ ］给 出了利用 二元 一 次不 定 方程 求 解 一次 ２ 同余式 （ ）的方 法 ， 然具 有普 遍性 ， 在具 体 求解 １ 虽 但

例 1 求 同 余 方 程 4x2 27x -12 0 (mod 15) 的解.
解 取模15的绝对最小完全剩余系:-7,-6, , - 1 , 0 , 1 , 2 , , 7 , 直 接计算 知 x 6,3 是 解. 所以 , 这 个同 余方 程的解 是x 6,3 (mod 15),解数为 2.
公钥密码体制
9
算法描述－密钥产生
① 独立地选取两大素数p和q(各100～200位十进制数字) ② 计算 n=p×q，其欧拉函数值(n)=(p－1)(q－1) ③ 随机选一整数e，1e<(n)，gcd((n), e)=1 ④ 在模(n)下，计算e的有逆元d=e -1 mod (n) ⑤ 以n，e为公钥。秘密钥为d。(p, q不再需要，可以销毁。)
由 第 三 章 §1定 理2,若 f (a) 0 (mod m),则 剩 余 类
Ka中 任 何 整 数 a'都 能 使 f (a') 0 (mod m)成 立.
定 义 若 a 是 使 f (a) 0 (mod m)成 立 的 一 个 整 数, 则 x a (mod m)叫 做 f (x) 0 (mod m)的 一 解. 这 就 是 说 我 们 把 适 合 f (x) 0 (mod m)而 对 模 m 互 相 同 余 的 一 切 数 算 作 f (x) 0 (mod m)的 一 个 解.
定 理5
设a
p1 1
p2 2
pkk , 则
(a) a(1 1 )(1 1 ) (1 1 ).
p1
p2
pk
§4 欧拉定理.费马定理及应用
定 理 1 (Euler) 设 m 是 大 于1的 整 数 , ( a,m) 1,则
a(m) 1 ( m o d m) .

我国古代关于求解一次同余式组的解法求解一次同余式组是古代数学中的一个重要问题，并且在当今的密码学、信息加密等领域仍有广泛应用。

古代中国的数学家们也研究了这个问题，并提出了一些有用的方法。

一、同余式组的定义和基本概念同余是数学中的一个重要概念，指两个数除以同一个数所得到的余数相等。

对于任意正整数m，如果a和b满足a≡b(mod m)，则称a 和b是在模m意义下同余的。

同余式可以用符号来表示，即a≡b(mod m)。

同余式组是由若干个同余式构成的方程组。

一个同余式组的解，就是满足所有同余式都成立的整数解。

二、中国剩余定理中国剩余定理是一种求解一次同余式组的重要方法。

该定理是中国数学家孙子在《数书九章》中首先提出的，后来由天文学家朱世杰详细阐述和推广。

中国剩余定理的基本思想是将原来的同余式组转化为同余式组的简单形式，再利用简单形式求解原来的同余式组。

设n1,n2,…,nk是k个不同的正整数，且两两互质，a1,a2,…,ak是任意k个整数。

则同余式组x≡a1(mod n1)x≡a2(mod n2)…x≡ak(mod nk)有唯一解x0，且x0满足0≤x0<n1×n2×…×nk。

具体实现方法如下：1. 求出N=n1×n2×…×nk。

2. 求出Ni=N/ni，即Ni与ni互质，且Ni的逆元对于ni来说存在。

这里的逆元指的是一个正整数x，使得x与ni互质，并且$xNi\equiv 1(mod\ ni)$。

3. 求出x0=a1Ni×Ni1+…+akNik×Nik。

显然，x0是x≡ai(mod ni)的唯一解。

三、孙子算经中的方法在孙子算经中，也有一些方法可以用于求解一次同余式组。

其中最著名的是“大衍求一术”和“一元二次不定方程求解法”。

1. 大衍求一术大衍求一术是孙子算经中的经典算法。

具体思路是先求出同余式组一组非常特殊的解，再通过这个解推导出一般的解。

关于a x≡b(modm)的解法1．当（a,m）≡1时：(1)若a,b<m,(a,b)=1且模数较大，可取余，将a变小，然后求出解。

eg:121x≡87(m0d257) 因为(121,257)=1,所以有一个解，x=194(mod257)(2)若a,b<m,(a,b)= 1且模数较小，用欧拉公式；eg: 7x≡5(mod10) 因为（7,10）所以有一个解。

（3）若（a,b ）=1,且a,b中至少有一个大于m，利用同余知识，将a,b化小再用（1）（2）式去解（4）若（a,b），≠约去两端的公因数；再用（1）（2）（3）式去解。

1Eg:58x≡87(mod47)2当（a,m）=d>1时:用d去除同于式，再用（a,m）=1去解<1>同余取倍法：（期刊-核心期刊和田师专科学校学报）JOURNAL OF HOTAN TEA CHERS COLLEGE 2009年第03期<2>一次同余式的初等变换解法：（山西大学学报：自然科学版）——袁虎延<3>一次同余式的逐级满足法<4>观察法解一次同余式<5>Euler定理解一次同余式<6>把同余式化为不定方程的解法<7>减少模数的方法解一次同余式<8>欧几里得法解一次同余式<9>分式法解一次同余式<10>威尔逊定理算法解一次同余式<下面仔细介绍>代数/数论/组合理论/《.黑龙江科技信息》2008年19期》摘要一次同余式解法的特点及其分析——作者：李婷只讨论（a,m ）=1时，同余式ax ≡b(modm)有以下七种解法（一）（1）观察法：在模m 的完全剩余系0,1，、、、，m-1中考虑同余式的解1.，当m 较小时，可用观察法，直接快速的得出方程的解eg 2x ≡1(mod3) 因为（2,3）=1所以有一个解，x ≡2(mod3)为其解2．当系数较大时，可用同余性质 ，将同余式系数减小，而且用带余除法定理，保证系数在一个固定范围内作为模m 的系数，进而用观察法，可快速得到方程的解。

学院学术论文一次同余式组的解法A congruence of the solution姓名所在学院专业班级学号指导教师日期摘要:研究了有关同余式组的解法,特别是孙子定理的应用,当模不两两互质时,就不能用孙子定理来解了,那该怎么办呢?我们将在实例的求解中来揭密.[Summary] Has studied the related congruence group's solution, specially Residue theorem application, when the mold 22 are not coprime, could not use the Residue theorem to solve, how should that manage? We will reveal in the example solution.关键字:一次同余式组 模 孙子定理[Key words] A congruence group Mold Residue theorem 正文：引理 1. （孙子定理）设1m ，2m ………. km 是k 个两两互质的正数，m=12......k m m m , m=i i m M , i=1,2,…,k ,则同余式组x ≡1b (mod 1m ),x ≡2b (mod 2m )，…，x ≡k b (mod k m )的解为：x ≡`111M M b +`222M M b +…+`k k k M M b (modm ）,……(2)，其中`i M M ≡1（mod i m ）,i=1,2,…,k.证明：由（i m ，j m ）=1，i ≠j 即得（i M ，i m ）=1，故由§1定理即知对每一i M ，有一`i M 存在，使得`i i M M ≡1（mod i m ）.另一方面m=i m i M ,因此j m |i M ，i ≠j ，故`1k j j j j MM b =∑≡`i i i M M b ≡i b （mod i m ）即为（1）的解。

学院学术论文课题：姓名所在学院专业班级学号指导教师日期摘要：主要介绍了同余的概念、性质、应用以及求解多项式整除的方法和一次同余式的相关问题。

关键词：同余性质、一次同余方程With more and more about with the related problems Colleges and universities: mathematics and computer science instituteClass: mathematics (1) className: GanMenBinAbstract: this paper is mainly introduces the concept, nature of congruence, application and solve polynomial division method and a congruence of related problems. Keywords: more than once, with more than with同余的定义：给定一个正整数m，把它叫做模，如果用m 去除任意两个整数a和b所得的余数相同，我们就说a，b 对模m同余，记作a≡b（mod m）；如果余数不相同，我们就说a，b对模m不同余，记作：a b （mod m）2同余的性质定理：性质1：a≡a（mod m），（反身性）这个性质很显然.因为a-a=0=m·0性质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对mod m同余的充分与必要条件是m︱a-b，即a=b+mt，t是整数。

证：设a=mc+d，b=me+f，0d m≤ ，0f m≤ ，若a≡b（mod m），则d=f，因此a-b=m︱（c-e）；反之若m︱a-b，则m︱m（c-e）+（d-f），因此m︱e-f，但︱e-f︱m，故e=f性质4：若a≡b（mod m），c≡d（mod m），那么a±c≡b±d（mod m），（可加减性）证明：由定理1，a=b+mq，c=d+mp，因此a+c=b+d+（q+p）性质得证，同理可以证明相减的。

一次同余方程的解法及应用初等数论是数学基础理论的一个分支，它主要研究的是整数的性质和方程的整数解。

由于初等数论中的问题简明易懂，所以近代数学中许多重要的思想、方法和技巧都是从对整数性质的深入研究而丰富并发展起来的。

在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。

例如我们问现在几点钟，就是用24去除某一个总的时数所得的余数,同是几点钟或同为星期几。

常常在生活中有同样的意义，这样，就在数学中产生了同余的概念。

这个概念的产生可以说大大丰富了数学的内容。

在代数里面一个主要的问题就是解代数方程，而同余方程是同余理论的核心内容。

在这里我们所要研究的就是关于同余方程的一些基本知识、概念、术语等，以及对于一次同余方程，一次同余方程组等等的求解问题。

一、同余方程设整系数多项式f（x）=anxn+…+a1x+a0（1）我们可讨论是否有整数值x满足同余式f（x）≡0（mod m）（2）我们要求解的这个同余式（2）称为是模的同余方程。

若整数c满足f（c）≡0（mod m），则称c是同余方程（2）的解，我们把这个解记为x≡c（mod m）。

这实际上是把同余类cmodm看作是满足同余方程（2）的一个解。

当c1、c2均为同余方程（2）的解，且对模不同余时，才把它们看作是不同解，我们把所有对模m 两两不同余的（2）的解的个数（即满足“2”的模m的同余类的个数）称为是同余方程（2）的解数。

因此，我们只要在模m的一组完全剩余系中来解模m的同余方程。

显然，模m的同余方程的解数至多为。

例1: 求同余方程4x2+27x-12≡0（mod 15）的解。

解：取模15的绝对最小完全剩余系：-7，-6，…，-1，0，1，2，…，7。

直接计算知x=-6，3是解。

所以，这个同余方程的解是x≡-6，3（mod 15）。

例2: 求同余方程4x2+27x-9≡0（mod 15）。

直接计算知这个方程无解。

当f（x）的系数都是模m的倍数时，显见，任意的整数值x都是同余方程（2）的解，这样的同余方程（2）的解数为m，但并不是同余方程（2）的解数为m的必要条件，这可由下面的例子看出。