一次同余式组解法

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),即解 即解 同样的问题：解的存在性和如何求解？ 同样的问题：解的存在性和如何求解？

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. 2009年第3期 牡丹江教育学院学报 No 13,2009(总第115期)　J OU RNAL OF MUDANJ IAN G COLL EGE OF EDUCA TION Serial No 1115[收稿日期]2008-12-22[作者简介]原新生(1967-),男,河南林州人,安阳师范学院副教授,主要从事初等数论、高等数学的教学与研究.。

一次同余方程的几种解法原　新　生(安阳师范学院,河南安阳455002) [摘　要]　介绍一次同余方程的几种解法,并比较它们的优劣,探讨不同情况下所应采用的不同方法,对解一次同余方程具有一定的指导作用。

[关键词]　一次同余方程;解法;完全剩余系[中图分类号]O151 [文献标识码]A [文章编号]1009-2323(2009)03-0115-01 定义1:设a ,b 为整数,m 是一个正整数且a ≠0(modm ),则称ax ≡b (mod m )为模m 的一次同余方程。

定义2:若x 0是使ax ≡b (mod m )成立的一个整数,则x ≡x 0(mod m )称为一次同余方程ax ≡b (mod m )的一个解。

定理:一次同余方程ax ≡b (mod m ),a ≠0(mod m )有解的充要条件(a ,m )|b,且有解时解数为(a ,m ).一次同余方程的理论各初等数论教材都作了详细的论述(见[1]、[2]、[3]),但对它的具体解法介绍的较少。

笔者在初等数论教学实践中,针对该方程总结了几种解法,并通过各种解法优劣的比较,探讨了在不同情况下所应采用的不同方法,这对学生学习初等数论,特别是解一次同余方程具有一定的指导作用。

方法一:验根法由定义2可以看出,求一次同余方程ax ≡b (mod m )有几个解,有哪些解,只需取模m 的一个完全剩余系(如0,1,2,…,m -1)中的每一个数,将其代入同余方程中逐一验证,即可求出其全部解。

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

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

一次同余方程是指形如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。

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

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

中国古代求解一次同余式组（见同余）的方法。

是数论中一个重要定理。

又称中国剩余定理。

注释：三数为a b c，余数分别为m1 m2 m3，%为求今年余计算，&&是“且”运算。

孙子定理孙子定理1、分别找出能被两个数整除，而满足被第三个整除余一的最小的数。

k1%b==k1%c==0 && k1%a==1;k2%a==k2%c==0 && k2%b==1;k3%a==k3%b==0 && k3%c==1;2、将三个未知数乘对应数字的余数再加起来，减去这三个数的最小公倍数的整数倍即得结果。

Answer = k1×m1 + k2×m2 + k3×m3 - P×(a×b×c);P为满足Answer > 0的最大整数；或者Answer = (k1×m1 + k2×m2 + k3×m3)%(a×b×c) ;解题思路：令某数为M，令素数为A，B，C，D，…，Z，已知M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z。

求M=？因为A，B，C，D，…，Z为不同的素数，故，B*C*D*…*Z不可能被A整除，有等差数列（B*C*D*…*Z）+（B*C*D*…*Z）N中取A个连续项，这A个连续项分别除以A的余数必然存在0，1，2，3，…，A-1，所以，从这A个连续项中能寻找到除以A余1的数。

再用除以A余1的这个数*a其积必然除以A余a，这个除以A余a 的数，为能够被素数B*C*D*…*Z整除的数，为第一个数；再按同样的道理，从A*C*D*…*Z的倍数中寻找除以B余b的数,该数具备被素数A，C，D，…，Z整除的特性，为第二个数；因为，第一个数除以A余a，第二个数能被素数A，C，D，…，Z整除，即能被A整除，所以，第一个数+第二个数之和，仍然保持除以A余a；同理，第二个数除以B余b，因第一个数能被B整除，所以，第二个数+第一个数之和，仍然保持除以B余b。

4) 如果a是可逆的,则其逆元是唯一的,记为a–1。 5) Zn中共有Φ(n)个可逆元。
练习：试求Z18中的可逆元个数。 Zn中元素逆元的求法：
dx+ny=1 dx≡1 (mod n) x≡d-1 (mod n)
回忆 辗转相除法：
设a0=n,a1=d，辗转做带余除法得 ai-1=qiai+ai+1，i=1,,k
第三讲 同余式（2）
教师：李艳俊 联系方式：13810350384
本讲内容
一 d-1(mod n)的解法 二 一次同余式求解 三 线性方程组求解
一、d-1(mod n)的解法 一次同余式 ax b mod n
首先考虑b=1的情形，即 ax 1mod n x是Zn中与a互逆的值，记为 x a1 mod n
其中k使0=ak+1<ak<<a1。
方法1 推导出求{vi}的递推关系：
注意到ai+1= ui+1n+vi+1d，又 ai+1=ai-1-qiai=(ui-1-qiui)n+(vi-1-qivi)d
可见
vi+1=vi-1-qivi，
且必要的初值是： v0=0,v1=1。
89
例：求39-1mod89。
1 qi
1
0 1
1 qi
n
d
ui vi
于是，可设ai=uin+vid，i=1,,k。 由辗转相除过程可知，ak=(d,n)。如果(d,n)=1，则
ukn+vkd=1，由此即得 vkd 1(mod n)
因此，d-1(mod n)=vk(mod n)。
例：7-1mod26=-11mod26=15。

一元一次同余方程组一个一元一次同余方程的一般形式可以表示为ax ≡ b (mod m)，其中 a、b 和 m 分别是整数，且 m 大于零。

这个方程可以解释为“a 与 x 模 m 同余于b”。

方程中的 x 是未知数，它的值满足方程的条件。

解决一元一次同余方程组的过程需要使用一些数论中的基本概念和性质。

首先，我们必须了解模运算的性质。

当我们将一个数除以一个模数时，得到的余数是模运算的结果。

例如，对于 17 除以 4，商是 4，余数是 1，我们可以表示为17 ≡ 1 (mod 4)。

这意味着 17 与 1 模 4 同余。

为了解决一元一次同余方程组，我们可以使用如下的步骤：1. 将每个方程写成标准形式ax ≡ b (mod m)。

2.检查每个方程的模数是否互素（即最大公因数为1）。

如果模数不互素，则方程组无解。

3.如果模数互素，则可以使用中国剩余定理来求解。

该定理说明了如果方程的模数互素，那么方程组一定存在解，并且有唯一解。

4.使用中国剩余定理的算法来计算解。

该算法可以通过计算模数的乘积来简化解的计算。

解决一元一次同余方程组的例子如下：解方程组：x ≡ 2 (mod 3)，x ≡ 3 (m od 4)，x ≡ 5 (mod 7)。

首先，将方程组写成标准形式：x ≡ 2 (mod 3)x ≡ 3 (mod 4)x ≡ 5 (mod 7)第一步，检查模数是否互素。

3、4和7互素，所以我们可以继续。

第二步，使用中国剩余定理。

根据该定理，我们可以将方程组的模数的乘积 m = 3 * 4 * 7 = 84，然后依次计算余数 a 和乘积除以模数 m_i。

对于方程组的第一个方程，a_1 = 2，m_1 = 84 / 3 = 28，然后计算乘积对 m_1 求模的逆元 b_1 = 28^(-1) ≡ 1 (mod 3)。

对于方程组的其他两个方程也一样。

第三步，使用计算所得的a和b来计算解。

根据中国剩余定理的算法，解x=(a_1*b_1*m_1+a_2*b_2*m_2+a_3*b_3*m_3)%m。

一次同余式组解法摘 要:同余式定义 同余式组有解条件 同余式组解法关键词:同余式;孙子定理;同余式组有解条件;同余式组解法引言在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数.例如问我们现在几点钟，就是用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。

k.
k
则(1)的解为
x
ai
M
i
M

i
(mod
m
)
(2)
i 1
其中，整数Mi（1 i k），满足MiMi 1 (mod mi).
2019/9/15
22
证明： 由 (Mi, mi) = 1，利用辗转相除法可以求出
Mi与yi ，使得 MiMi yimi = 1，
Mi Mi ' 1(mod mi )
另外，显然有 5 | x1 , 3 | x2 ,
从而有 x1 x2 2(mod 3), x1 x2 3(mod 5).
2019/9/15
20
问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。〔《孙子算经》〕
记 x1 5 7n1 2,且5 7n1 1(mod 3), 则x1 2(mod 3)； 记 x2 3 7n2 3,且3 7n2 1(mod 5), 则x2 3(mod 5). 记 x3 3 5n2 2,且3 5n2 1(mod 7), 则x3 2(mod 7). 另外，显然有 5 7 | x1 , 3 7 | x2 , 3 5 | x3 , 令x x1 x2 x3 , 则有x 2(mod 3), x 3(mod 5), x 2(mod 7).
例2 解同余方程 325x 20 (mod 161)
解 d=1,原同余方程即是 3x 20 (mod 161)。
解同余方程
161y 20 (mod 3)，
2y 1 (mod 3)， 得到y 2 (mod 3)，因此原方程的解是
x 20 2 161 114mod(161) 3

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存在。

一元一次同余方程组在解决一元一次同余方程组时，一般使用中国剩余定理。

中国剩余定理是由数学家孙子在中国古代数学著作《孙子算经》中提出的。

它的具体内容是：如果给出了同余方程组某≡ a(mod m) 的一组解，其中m1,m2,…,mk 互质，那么对于任意的整数c1,c2,…,ck，同余方程组。

某≡ c1(mod m1),某≡ c2(mod m2),...某≡ ck(mod mk)必然存在一个解，并且这个解是模 M = m1 某 m2 某… 某 mk 的一个周期。

中国剩余定理的证明也是比较简单的。

假设某 = a1某M1某t1 + a2某M2某t2 + ... + ak某Mk某tk 是满足同余方程组的解，其中 M = m1 某 m2 某… 某 mk，Mi = M/mi，ti 为 Mi 的乘法逆元。

通过比较同余方程两边的模 M 可以得到方程组的通解。

在实际应用中，解决一元一次同余方程组一般需要求解 Mi 和 ti。

计算 Mi 的方法是使用扩展欧几里得算法，求解 ti 的方法是使用逆元的概念。

逆元指的是对于给定的数 a 和模数 m，存在一个数 b，使得 a某b ≡ 1 (mod m)。

求解逆元可以使用欧拉定理，其中 Euler(m) = m-1。

在密码学中，一元一次同余方程组的求解是非常重要的。

例如，在RSA加密算法中，求解一元一次同余方程组可以用来生成密钥。

同时，在解密过程中也需要通过求解一元一次同余方程组来还原明文。

总结来说，一元一次同余方程组是数论中的重要内容，并且在密码学等领域有着广泛应用。

通过中国剩余定理可以求解一元一次同余方程组，并且在实际应用中可以使用扩展欧几里得算法和逆元等方法进行计算。

⼀次同余⽅程的解法及应⽤2019-07-04初等数论是数学基础理论的⼀个分⽀，它主要研究的是整数的性质和⽅程的整数解。

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

在⽇常⽣活中，我们所要注意的常常不是某些整数，⽽是这些数⽤某⼀固定的数去除所得的余数。

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

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

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

在代数⾥⾯⼀个主要的问题就是解代数⽅程，⽽同余⽅程是同余理论的核⼼内容。

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

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

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

这实际上是把同余类cmodm看作是满⾜同余⽅程（2）的⼀个解。

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

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

显然，模m的同余⽅程的解数⾄多为。

例1: 求同余⽅程4x2+27x-120（mod 15）的解。

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

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

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

例2: 求同余⽅程4x2+27x-90（mod 15）。

直接计算知这个⽅程⽆解。

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

一次同余式与一次同余式组的解的讨论摘 要: 这篇文章先给出有关同余式、同余式的解的概念，并在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)的解。

例 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. 大衍求一术大衍求一术是孙子算经中的经典算法。

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

3.2 一次同余方程
人教B版数学选修4-6《初等数论初步》
一次同余方程 一次同余方程的一般形式为 ax≡b(mod m)， a 0(modm) 有
定理：a,b为整数，a 0(modm)，则
ax≡b(mod m)有解的充要条件是(a,m)|b,若有解 则有d=(a,m)个关于模m的解
证明：由同余的定义知ax≡b(mod m)等价于 不定方程ax=b-my，而此不定方程有解的充 要条件是(a,m)|b。在有解的情况下，设不定 方程的解为
m m1m2 mk
(mi , M i ) 1 证明：因为 m1 , m2 ,mk 两两互素，
, M M 所以有 i i 1(modmi )
， M i 存在，又对 中的 任意的 i j 有 (mi，mj ) 1, i j 有mj | Mi
所以
, , M M b M M j j j i i bi bi (modmi ) j 1
9 9 4
6 （ 2） 30 8(mod11)
4
(3)用形式分数
定义1：当（a，m）=1时，若ab 1(modm)， 则记b 1 a (modm)称为形式分数。
1 c 根据定义和记号， 有性质 a (modm) c a
1、
c c m t1 (modm), t1 , t2 Z a a m t2
次数大于1的同余方程称为高次同余方 程，一般地高次同等方程可转化一系列的高 次同余方程组。然后将每一个高次同余方程 的解都求出，最后利用孙子定理可求出原高 次同余方程的解。
想想我们本节讲了什么？
我们再解不定方程15x-44y=7,得到一解(21,7).,
方程3个解为 x 21,21 44,21 2 44(mod132)

学院学术论文一次同余式组的解法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）的解。

一次同余方程组的一般形式为：a1x ≡ b1 (mod m1)a2x ≡ b2 (mod m2)...anx ≡ bn (mod mn)若存在正整数解x，则称这个方程组有解。

为了求解这个方程组，我们可以使用扩展欧几里得算法（Extended Euclidean Algorithm）。

首先，我们求出mi与mi-1的最大公约数d，然后求出最大公约数d 与mi-2的最大公约数，以此类推。

当求出最大公约数d与m1的最大公约数后，我们就可以得到一个方程：dx + my = gcd(d, m)其中，x和y是未知数。

我们求出这个方程的一组特解（particular solution）后，就可以得到一组通解（general solution）：x = x0 + k(m/gcd(d,m))其中，x0是特解，k是任意整数。

我们可以用这个通解来解决一次同余方程组。

例如，设有方程组：3x ≡ 2 (mod 5)7x ≡ 3 (mod 8)我们可以依次求出8与5的最大公约数d=1，以及1与3的最大公约数d=1。

因此，我们可以得到方程1x + 5y = 1。

我们求出这个方程的特解x0=1，y0=-2，则通解为x = 1 + 5k，其中k是任意整数。

我们把上面的方程组带入通解，得到：3(1 + 5k) ≡ 2 (mod 5)7(1 + 5k) ≡ 3 (mod 8)令k=0，得到特解x0=1。

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

我们可以用这个通解来解决原来的方程组。

例如，当k=0时，x=1，这是一个合法的解。

当k=1时，x=6，这也是一个合法的解。

当k=-1时，x=-4，这也是一个合法的解。

我们可以看到，对于一次同余方程组，我们可以使用扩展欧几里得算法来求解。

通过求出最大公约数和方程的特解，我们可以得到一组通解，然后通过通解来求出方程组的解。