当前位置：文档之家 › 一次同余式与一次同余式组的解的讨论

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

  • 格式：doc
  • 大小：720.50 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

3.同余式

3.同余式

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

【doc】同余方程

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

一次同余式与一次同余式组的解的讨论摘 要: 这篇文章先给出有关同余式、同余式的解的概念，并在Euler 定理及孙子定理的基础上,详细地讨论了一次同余式、一次同余式组的是否有解的条件，若有解，则给出了求解方法. 一次同余式和一次同余式组的相关知识是学习数论过程中必须要掌握的知识，它在数学领域内有着及其广泛的应用。

关键词: 一次同余式; 一次同余式组;孙子定理;Euler 定理1引言南北朝时期的数学著作《孙子算经》中“物不知数”是这样的“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”解法和答案用算式表示为：702213152105223⨯+⨯+⨯-⨯=，即得到适合题意的最小正整数是23。

《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但真正从完整的计算程序和理论上解决这个问题的是南宋时期的数学家秦九韶。

秦九韶在他的《数书九章》不仅给出了一次同余式的解，而且用“大衍求一术”数学方法给出了一次同余式组的最小正整数解。

2基本定义和定理定义2.1 设1110()n n n n f x a x a x a x a --=++++ 是整系数多项式，m 是一正整数，称()0(mod )f x m ≡ (1)是模m 的同余式，若0(mod )n a m ≡/，则n 叫做同余式(1)的次数。

定义2.2 若a 是整数，且使得()0(mod )f a m ≡成立，则(mod )x a m ≡叫做同余式(1)的一个解。

即把适合(1)式且对模m 相互同余的一切数叫做同余式(1)的一个解。

定义2.3 欧拉函数()a ϕ是定义在正整数上的函数，它在正整数a 上的值等于序列0,1,2,,1a - 中与a 互质的数的个数。

定理2.1(Euler) 设1m >，(,)1a m =，则()1(mod )m a m ϕ≡。

证明 设12(),,,m r r r ϕ 是模数m 的一组简化剩余系，则由定理（若(,)1,a m x =通过m 的简化剩余系，则ax 通过模m 的简化剩余系.）可知12(),,,m ar ar ar ϕ 也是模m 的一组简化剩余系，故 12()12()()()()(mod )m m ar ar ar r r r m ϕϕ≡即 ()12()12()(mod )m m m a r r r r r r m ϕϕϕ≡ (﹡) 由于 ()i r ,1,1,2,,().m i m ϕ==故 12()(,)1.m r r r m ϕ= (﹡﹡)根据性质（若11,,(,)1,a a d b b d d m ===则11(mod ).a b m ≡） 以及 (﹡)和(﹡﹡)得 ()1(mod ).m a m ϕ≡定理2.2（孙子定理） 设12,,,k m m m 是k 个两两互素的正整数,12,(1,2,,),k i i m m m m m m M i k ===则同余式组1122(mod ),(mod ),,(mod )k k x b m x b m x b m ≡≡≡ (2)有唯一关于模m 的解111222(mod ),k k k x M M b M M b M M b m '''≡+++ (3) 其中1(mod )(1,2,,).i i i M M m i k '≡=证明 由于(,)1,i j m m i j =≠，即得(,)1i i M m =.由定理3.1知对每一i M ，有一i M '存在，使1(mod ).i i i M M m '≡由i i m m M =，知|,j i m M i j ≠. 故1(mod ),1,2,,.kjjji i i i i j M M bM M b b m i k =''≡≡=∑即(3)为(2)的解。

若12,x x 是适合(2)式的任意两个整数，则12(mod )(1,2,,).i x x m i k ≡=又由于(,)1,i j m m i j =≠，于是12(mod )x x m ≡，故(2)仅有解(3)。

3一次同余式定理3.1 若(),1,|a m d d =>,b 则(mod )ax b m ≡无解。

证明 若有解，即可得()mod .ax b m ≡而|,d a 于是有0(mod ).b d ≡而这与|,d b 相矛盾，所以同余式无解。

定理3.2 设(,)1,0a m m =>，则同余式(mod )ax b m ≡ (4)有唯一解 ()1(m o d ).m x b am ϕ-≡ 证明 由于1,2,,m 组成一组模数m 的完全剩余系，(,)1a m =，故,2,,a a m a 也组成模数m 的一组完全剩余系，故其中恰有一个数设为aj ，适合(mod ),(mod )aj b m x j m ≡≡就是(4)的唯一解。

方法一 由定理2.1知 ()()()1mod .m m a x ba m ϕϕ-≡。

从而()()1mod m x ba m ϕ-≡为所求的解。

即原命题成立。

方法二因为(),1a m =.由定理(若(),a b d=由最大公因数性质可知必有二数,s t 使 1.as bt+=)知必有二数s t ，使1as mt +=，即()1mod .as m ≡ 故由()mod asx bs m ≡知同余式(4)的解为 ()mod .x bs m ≡定理3.3 设(,),0a m d m =>，同余式(4)有解的充分必要条件是|d b ，且恰有d 个解。

证明 若(4)有解，则由|,|d a d m 推出|d b 。

如果|d b ，则,1a m d d ⎛⎫= ⎪⎝⎭，故同余式mod a b m x d d d ⎛⎫≡ ⎪⎝⎭①有一组解，即同余式(4)有一组解。

若整数c 适合(4)，c 也适合同余式①；反之，若c 适合同余式①，c 也适合同余式(4)。

设t 适合①，则①有唯一解 (m o d )mx t d≡，即全体整数,0,1,2,,mt k k d+⋅=±±对模数m 来说，恰可选出d 个互不同余的整数,,2,,(1).m m mt t t t d d d d ++⋅+- ②这是因为对于mt k d +，设,0k qd r r d =+≤<代入得()(mod ).m m m mt k t qd r t r qm t r m d d d d+⋅=++=++≡+又若 ()0,0,mod m me df d t e t f m d d≤<≤<+≡+，则推出f e =.这就证明了(4)的任一解恰与②中的某一数模数m 同余，而②中的d 个数，又模数m 两两互不同余，即知(4)恰有d 个解。

一般地，我们有定理3.4 设1k ≥，同余式110(mod )k k a x a x b m +++≡ (5)有解的充分必要条件是 ()1,,,|.k a a m b (6) 若条件(6)满足，则(5)的解数为()11,,,k k m a a m - 。

证明 现用归纳法来证明。

由定理3.2知当1k =时结论显然成立。

设()()1111,,,,,,,k k a a m d a a m d -== ，则()11,d a d =。

由定理 3.3知 ()10m o k k a x b d +≡ （ⅰ） 有d 个解()()()()11111mod mod mod 1mod k k k d dx t d x t d x t d d d d≡≡+≡+- ，，,， 从而对模数m 来说有1md d ⋅个解：1111111(mod ),(mod ),,(1)(mod ),(1)(mod ),,(1)(1)(mod )k k k k k x t m x t d m mx t d m d d x t d m d d mx t d d m d d ≡≡+≡+-≡+-≡+-+-对（ⅰ）的一个解k x ，设11n k a x bb d +=， 由归纳法假定，1111110(mod )k k a x a x b d m --+++≡的解数为 22111(,,,)k k k m a a m m d ---= ， 故(5)的解数为2111k k mm d d m d d --⋅⋅=. 例1解同余式 ()11175mod 321.x ≡解 因为()111,3213,3|75,≡故同余式有解，且化为()3725mod107.x ≡ 故 ()257532899m o d 107.371114x -≡≡≡≡-≡ 于是原同余式有三个解：()99,206,313mod321.x ≡ 例2解同余式()286121mod341.x ≡解 因为()286,34111,11|121,≡故同余式有解，且化为()2611mod31.x ≡故 ()11204m o d 31.265x -≡≡≡- 于是原同余式有三个解：()4,35,66,97,128,159,190,221,252,283,314mod341.x ≡4一次同余式组定理4.1 设12,m m 是两个正整数，同余式组()()1122mod mod x b m x b m ≡⎧⎪⎨≡⎪⎩(7) ① 若()12,|m m 12b b -，则同余式组(7)无解。

② 若()1212,|m m b b -，则同余式组(7)有以[]12,m m 为模的一类剩余解。

证明 ①满足同余式()11mod x b m ≡的数为 1,x b m t t Z ≡+∈ ⑴ 并且满足同余式 ()22mod x b m ≡， 则有 ()1122mod b m t b m +≡即 ()1212m o d m t b b m≡- ⑵ 由于()12,|m m 21b b -,所以同余式()22mod x b m ≡无解，即同余式组无解。

③ 若()1212,|m m b b -，则可设()11222112,,,, 1.m m d m m d b b bd m m ''''==-==由⑵得 ()12mod m t b m ''≡ ⑶因为()()1212m m m m dd ''==，d ，，故()121m m ''=，，所以⑶式有一个解。

设()2m o d t b m '≡ 从而⑵有d 个解()()222,,,1mod t b b m b d m m ''≡++-将2,t b m Z λλ'=+∈代入⑴有 ()1121112.x b m b m b bm m m λλ''=++=++又[]121212,m m m m m m d'== []()1112m o d ,x b b m m m ∴=+ 由于11,b m 是给定的，而且b 是唯一确定的，从而同余式组有唯一的解。