一次同余式与孙子定理

厦门大学教案学年度第学期院（系）数学科学学院任课教师祝辉林课程名称初等数论授课章节：第4.3节一次同余方程组和孙子定理授课教材：《初等数论》，北京大学出版社授课对象：数学类专业一年级本科生【教学要求】1. 了解孙子定理的历史背景和起源出处，理解用孙子定理求解一次同余方程组的思想方法和公式，掌握求解一次同余方程组的计算步骤；2. 掌握一次同余方程组的模两两不互素时，应当如何转化成模两两互素时的等价一次同余方程组，再用孙子定理求解；3. 理解一次同余方程组的意义，并能用孙子定理的方法解决一些实际应用问题。

【教学重点】1. 孙子定理的思想方法和计算步骤；2. 如何应用孙子定理解决实际应用问题。

【教学难点】理解孙子定理的思想方法。

【教学内容】第三节一次同余方程组和孙子定理本节主要讨论一次同余方程组的解法。

为了解决这类同余方程组，我们需要弄清楚剩余系的结构。

孙子定理(又称中国剩余定理)就是解决这类实际问题的有力工具。

一、“物不知其数”问题及其解法1.1问题的提出例1：（“物不知其数”问题）大约在公元四世纪，我国南北朝时期有一部著名的算术著作《孙子算经》，其中就有一个“物不知其数”问题：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三”。

1.2 问题的解法及理由明朝程大位编著的《算法统宗》里记载了此题的解法，他是用一首歌谣叙述出来的：三人同行七十稀，五树梅花廿一枝。

七子团圆正月半，除百零五便得知。

这首诗翻译成数学算式就是：702213152233⨯+⨯+⨯=，233105223-⨯=。

解题步骤及理由如下：（1）先在5和7的公倍数中找除以3余1的数，进而找到除3余2的数。

因为[5,7]35=，35311÷=(余2)，(352)323⨯÷=(余1)，而(702)346⨯÷=(余2)，所以140符合条件。

（2）在3和7的公倍数中找除以5余1的数，进而找到除5余3的数。

中国余数定理公式中国余数定理，也称为孙子定理，是一种基于模运算的经典数学定理。

它能够将一个同余方程组转化为一个单同余方程，从而大大简化问题的求解。

这个定理在代数学、计算机科学、密码学等领域都有广泛的应用。

中国余数定理的原理假设给定两个正整数m1和m2，他们互质，对于任意两个整数a1、a2，下面的同余方程：x ≡ a1 (mod m1)x ≡ a2 (mod m2)都有一个解x在模m1m2下唯一确定。

特别的，当给定n个正整数m1、m2、...、mn，它们两两互质时，对于任意n个整数a1、a2、...、an，下面的同余方程组：x ≡ a1 (mod m1)x ≡ a2 (mod m2)...x ≡ an (mod mn)都有一个解x在模M=m1m2...mn下唯一确定。

中国余数定理的应用场景1. 线性同余方程组的求解中国余数定理可以将多个线性同余方程组转化为一个单一的同余方程，从而简化了求解问题。

在密码学领域中，线性同余方程组的求解常常涉及多个密码学密钥的计算和变换。

2. 数论问题的求解中国余数定理在数论领域中有广泛的应用。

它可以用来求解大量数据的最小公倍数，检测质数的性质，以及判断两个数是否是互质的。

3. 数据加密和解密中国余数定理可以用来设计和实现许多加密算法和协议，例如RSA加密算法和离散对数算法。

这些算法和协议通常需要利用中国余数定理来处理数字的加密和解密过程。

4. 编程语言中的应用在计算机科学领域，中国余数定理被广泛应用于编程语言中。

Java语言中可以利用中国余数定理来计算大型整数的模运算，而C++语言中则可以利用中国余数定理解决多项式求值问题。

总结：中国余数定理是一种重要的数学定理，常常在代数学、计算机科学、密码学等领域中得到广泛应用。

它能够将一个同余方程组转化为一个单同余方程，从而大大简化问题的求解。

在实际应用中，中国余数定理被广泛用于线性同余方程组的求解、数论问题的求解、数据加密和解密、以及编程语言中的应用等方面。

有解的充要条件是(a, m)b。 若有解，则恰有d = (a, m)个解。 特别地，若(a, m)＝1，则方程（2）有唯一解。 证明 ax b (mod m) m ax b 同余方程(2)等价于不定方程 ax my = b， (3)
因此，第一个结论可由第二章第一节定理1〔P25〕得出。
2020/12/21
则 mi x ai , mj x aj (mi , mj ) ( x ai x aj )
即 (mi , mj ) ( ai aj ) ai aj (mod (mi, mj))，1 i, j n.
2020/12/21
27
则 x1 x2 (mod [m1, m2])。
(5)
证 〔必要性〕 x a1(mod m1 ), x a2(mod m2 ) m1 x a1, m2 x a2 (m1, m2 ) a1 a2
2020/12/21
25
〔充分性〕记(m1, m2)＝d. 若式(4)成立，即d a1 a2，
19y 4 (mod 7)，
即 5y 4 (mod 7)，
y 2 (mod 7)。
再代入(*)的前一式得到 3x 10 1 (mod 7)， x 4 (mod 7)。
即同余方程组(*)的解是x 4，y 2 (mod 7)。
注：同余方程组的解法与方程组的解法相似。
2020/12/21
15
2020/12/21
12
例3 解同余方程6x 7 (mod 23)。
ax
b
(mod
m)
a1 x
b[ m ](mod m) a
解 由定理4，依次得到
6x 7 (mod 23) 5x 73 2 (mod 23) 3x 24 8 (mod 23) 2x 8×7 10 (mod 23) x 5 (mod 23)。

2020/4/1
10
例2 〔韩信点兵〕有兵一队，若列成五行纵队，则 末行1人；成六行纵队，则末行5人；成七行纵队， 则末行4人；成十一行纵队，则末行10人。求兵数。
解 ： 即 求 解 同 余 式 组
x 1 ( m o d 5 ) , x 5 ( m o d 6 ) , x 4 ( m o d 7 ) ,2 6 , m 3 7 , m 4 1 1 .
202043阜阳师范学院1247年南宋的数学家秦九韶把孙子算经中物不知其数一题的方法推广到一般的情况得到称之为大衍求一术的方法在数书九章中发表
§4.2 孙子定理
李新年
2020/4/1
1
• 看过《射雕英雄传》的同学应该记得，当年黄蓉身中奇毒 ，郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给 他们出了一题：
2020/4/1
3
中国剩余定理
➢ 1247年南宋的数学家秦九韶把《孙子算经》中“物
不知其数”一题的方法推广到一般的情况，得到称之 为“大衍求一术”的方法，在《数书九章》中发表。 这个结论在欧洲要到十八世纪才由数学家高斯和欧拉 发现。所以世界公认这个定理是中国人最早发现的， 特别称之为“中国剩余定理”
2020/4/1
12
敬请指导，谢谢！
2020/4/1
阜阳师范学院 数科院
13
感谢亲观看此幻灯片，此课件部分内容来源于网络， 如有侵权请及时联系我们删除，谢谢配合！
m i ai 51 65 74 11 10
m
Mi
462
385 2310 330
210
M i ' aiMiMi ' aiMiMi'
3
1×462×3
1 5×385×1 6731

m1 24
m2 32
4 2 2 mm 1m 2m 3 2 3 5 3600
m3 52
M1 32 52 225
M11 1
M1M11 225
M 2 24 52 400
M 21 2
M 2 M 21 800
M3 24 32 144
j j
M j M j 1(mod mj ) ， (1 j k ) 。
1
证明:由于 m , , m
1
1 k
k
两两互素,所以 m [m1, , mk ] m1 mk 。
1 2 j
若一次同余方程组有解 c1 , c2 ，则 c1 c2 (modm) 。因为 m , , m 两两互素, c c (modm ),1 j k ，这就证明了同余 方程若有解,则解数为1。 显然 (m , M
三、孙子定理的应用
孙子定理是数论中最重要的基本定理之一, 它实质上刻画了剩余系的结构.它的应用是非常 广泛的,在数学计算、保密通讯、测距和日常生 活中通常会用到。 陈景润《初等数论I》中有下列趣味问题： 甲、乙两港的距离不超过5000公里， 今有三只轮船于某天零时同时从甲港开往乙港。 假定三只轮船每天24小时都是匀速航行，
此处 m1 24 , m2 32 , m3 52 ,
a1 4, a2 6, a3 0,
M1 32 52 225, M2 24 52 400, M3 24 32 144, m 24 32 52 3600.
由于 225M11 1(mod 24 ), M11 1(mod 24 ), 所以取 M11 1. 由 400M 1(mod3 ), 4M 1(mod3 ), M 2(mod3 ),

孙子定理解同余方程组（最新版）目录1.同余方程组的概念及孙子定理的背景2.孙子定理的概述3.同余方程组的求解方法4.中国剩余定理的证明5.孙子定理的应用及意义正文一、同余方程组的概念及孙子定理的背景同余方程组是数论中的一个重要概念，它是指一组包含多个同余方程的方程组。

例如，"物不知数"问题就是一道典型的同余方程组问题。

中国古代数学家孙子在《孙子算经》中提出了著名的"物不知数"问题，从而引出了同余方程组和孙子定理的研究。

二、孙子定理的概述孙子定理，又称中国剩余定理，是数论中的一个重要定理。

它是指对于一个同余方程组，如果其中某一个方程的解已知，则可以求出其他所有方程的解。

这个定理在我国古代数学中被誉为"孙子定理"，是中国古代数学的一项重要成果。

三、同余方程组的求解方法同余方程组的求解方法主要有两种，一种是基于孙子定理的解法，另一种是基于代数的解法。

基于孙子定理的解法是先求出其中一个方程的解，然后利用孙子定理求出其他方程的解。

而基于代数的解法则是利用代数的方法，通过一系列的运算和推导，求出同余方程组的解。

四、中国剩余定理的证明中国剩余定理的证明是基于数学归纳法的。

首先，对于一个简单的同余方程组，可以通过直接求解得到它的解。

然后，假设对于任意的 n-1 个同余方程，都可以通过孙子定理求出它的解，接下来需要证明当有 n 个同余方程时，也可以通过孙子定理求出它的解。

五、孙子定理的应用及意义孙子定理在数学中有着广泛的应用，它不仅被用于解决同余方程组问题，还被用于解决代数方程组、数论问题等领域。

感谢观看，欢迎指导！
x≡e（moda）， x≡f（modb），仅有一解： x≡g（modc） x≡ebcc1+facc2+gabc3（modabc），其中c1， c2，c3分别满足同余式：bcc1≡1（moda） acc2 ≡1（modb）,abc3 ≡1（moda）的整数.
课堂小结
一、一次同余式组： x≡e（moda）
设a，b，c两两不同那么满足f(a)=e，f(b)=f ， f
（c）=g的一个多项式可用
f(x)=e·p(x)+f ·q(x)+ g ·r(x) (Ⅰ)
其
中
p(x)
x a
bx ba
c c
,
q(x)
x b
a a
x b
c c
, r(x)
x c
a a
x c
（ b Ⅱ）
b
上面的公式（Ⅰ）和（Ⅱ）叫做拉格朗日公式. 用类似方法解决孙子算经的物不知其数问题. 1）求整数p,使p≡1（mod3）, p ≡0（mod5）, p≡0（mod7）.
证明：
因为 yn+1 - xn+1 = f(yn ) - f(xn )
yn - xn
yn - xn
由拉格朗日中值定理知: 总存在 (xn使, y得n )
由于 又 yn+1 - xn+1 = f'(ξ)
yn - xn
当
(
xn
,
yn
)
[0,
1] 2
f '(x故) 得3x2证 2x 1
2
1
1
x [0, ],[ f 2
过程与方法
1.先阅读案例，探究解决问题的算法. 2.研读算法，体会算法思想，能解决具体问题.

关于孙⼦定理（中国剩余定理）及其证明孙⼦定理的内容：给出以下的⼀元线性同余⽅程组：(S ):x ≡a 1(mod m 1)x ≡a 2(mod m 2)…x ≡a n (mod m n )假设整数m 1,m 2,…,m n 两两互质，则对任意的整数：a 1,a 2,…a n ，⽅程组(S )有解，并且通解可以⽤如下⽅式构造得到：设M =m 1×m 2×…×m n =∏n i =1m i ，并设M i =Mm i ,∀i ∈1,2,…n 设t i =M −1i 为M i 模m i 的数论倒数（t i 为M i 模m i 意义下的逆元），即M i t i ≡1(mod m i ),∀i ∈1,2,…,n .⽅程组(S )的通解形式为x =a 1t 1M 1+a 2t 2M 2+…a n t n M n +kM =kM +∑n i =1a i t i M i ,k ∈Z .在模M 的意义下，⽅程组(S )只有⼀个解：x =∑n i =1a i t i M i (mod M )证明：从假设可知，对任何i ∈1,2,…,n ,j ≠i ,gcd (m i ,m j )=1，所以gcd (m i ,M i )=1.这说明存在整数t i 使得t i M i ≡1(mod m i ).这样的y i 叫做M i 模m i 的数论倒数。

考察乘积a i t i M i 可知：a i t i M i ≡a i ×1≡a i (mod m i )∀j ∈1,2,…,n ,j ≠i ,a i t i M i ≡0(mod m j )所以x =a 1t 1M 1+a 2t 2M 2+…+a n t n M n 满⾜：∀i ∈1,2,…,n ,x =a i t i M i +∑j ≠i a j t j M j ≡a i +∑j ≠i 0≡a i (mod m i )这说明x 就是⽅程组(S )的⼀个解。

中国剩余定理（孙子定理）定义中国古代求解一次同余式组（见同余）的方法。

是数论中一个重要定理。

又称中国剩余定理。

编辑本段内容1、分别找出能任两个数整除，而满足被第三个整除余几的数。

2、将三个未知数加起来，减去这三个数的最小公倍数的整数倍。

N≡R1(mod d1) ≡R2(mod d2)≡R3(mod d3)则N=k1d2d3R1+k2d1d3R2+k3d1d2R3±d1d2d3P其中P为任意非负整数k1是满足k1d2d3≡1(mod d1)的最小正整数k2是满足k2d1d3≡1(mod d2)的最小正整数k3是满足k3d1d2≡1(mod d3)的最小正整数编辑本段解法解法中的三个关键数70，21，15，有何妙用，有何性质呢?首先70是3除余1而5与7都除得尽的数，所以70a是3除余a,而5与7都除得尽的数，21是5除余1，而3与7都除得尽的数，所以21b是5除余b，而3与7除得尽的数。

同理，15c是7除余c，3与5除得尽的数，总加起来 70a+21b+15c 是3除余a，5除余b ，7除余c的数，也就是可能答案之一，但可能不是最小的，这数加减105(105=3*5*7)仍有这样性质，可以多次减去105而得到最小的正数解。

附：如70，其实是要找余2的，但只要找到了余1的再乘2即余二了。

孙子问题的解法，以现代的说法，是找出三个关键数70，21，15。

解法的意思就是用70乘3除所得的余数，21乘5除所得的余数，15乘7除所得的余数，然后总加起来，除以105的余数就是答案。

即题目的答案为70×2+21×3+15×2=140+63+30=233233-2×105=23公式：70a+21b+15c-105n题中有三个数，分别为3、5、7，5*7/3余数为2，取35；3*7/5余数为1，要使余数为3，只需将3*7扩大3倍变成63即可；同样3*5/7的余数为1，要使余数为2，则将3*5扩大2倍，变成30。

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

中国剩余定理【定理概述】 中国剩余定理（孙⼦定理）是中国古代求解⼀次同余式组的⽅法。

是数论中⼀个重要定理。

⼀元线性同余⽅程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙⼦算经》卷下第⼆⼗六题，叫做“物不知数”问题，原⽂如下：有物不知其数，三三数之剩⼆，五五数之剩三，七七数之剩⼆。

问物⼏何？即，⼀个整数除以三余⼆，除以五余三，除以七余⼆，求这个整数。

《孙⼦算经》中⾸次提到了同余⽅程组问题，以及以上具体问题的解法，因此在中⽂数学⽂献中也会将中国剩余定理称为孙⼦定理。

【求逆元】逆元的含义：模p意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

ax≡1(mod p)。

⼀个数有逆元的充分必要条件是gcd(a,p)=1，此时逆元唯⼀存在，注意这⾥的唯⼀是指在群中唯⼀。

其实如果求出⼀个逆元x0，那么x0 + p*k都会满⾜上⾯的等式，但是我只取p内的正整数x0.【证明】由ax≡1(mod p)等价于这样⼀个⽅程a*x + p*y = 1 ，或者说这个⽅程x有解的话x必然满⾜ ax≡1(mod p)这个⽅程什么时候有解呢？很显然，当gcd(a,p) | 1时有解，所以gcd(a,p)只能是1，即a,p互质，证明完毕。

由此还可以得到⼀个结论，如果要求逆元，可以⽤扩展欧⼏⾥得求⼀组解（x,y），再求出x的最⼩正整数（x+p）%p,x就是a的唯⼀逆元。

⽅法1：费马⼩定理求逆元，p是，且gcd(a,p)=1在模为素数p的情况下，有费马⼩定理a p-1 ≡ 1（mod p）则a * a p-2 ≡ 1（mod p）所以a的逆元就是a p-2，⽤快速幂求即可。

#include<iostream>using namespace std;long long gcd(long long a, long long b){if(b == 0) return a;return gcd(b , a%b);}long long qPow(long long a ,long long n,long long mod){long long ans = 1;//如果n的⼆进制最后⼀位是1 结果参与运算//因为如果是0，那么幂运算之后该项是1,1乘任何数还是那个数，对结果不影响while(n > 0){if(n & 1)ans = (ans* a) % mod;a = (a*a) % mod;//底数加倍n >>= 1;//移位}return ans;}//long long invEle(long long a, long long mod){ //如果a 和模数不互质则必然不存在逆元if(gcd(a,mod) != 1 || mod < 2) return -1; return qPow(a,mod-2,mod);}int main(){long long a,b;int x,y;while(cin>>a>>b){cout<<invEle(a,b)<<endl;}}⽅法2：扩展欧⼏⾥得求逆元（⾼效）typedef long long ll;void extgcd(ll a,ll b,ll& d,ll& x,ll& y){if(!b){ d=a; x=1; y=0;}else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }}ll inverse(ll a,ll n){ll d,x,y;extgcd(a,n,d,x,y);return d==1?(x+n)%n:-1;}⽅法3：欧拉定理求逆元（很少⽤到）模p不是素数的时候需要⽤到欧拉定理逆元打表：typedef long long ll;const int N = 1e5 + 5;int inv[N];void inverse(int n, int p) {inv[1] = 1;for (int i=2; i<=n; ++i) {inv[i] = (ll) (p - p / i) * inv[p%i] % p;}}【解⽅程组】根据定理概述以及解法，得到以下⽅法int CRT(int a[],int m[],int n){int M = 1;int ans = 0;for(int i=1; i<=n; i++)M *= m[i];for(int i=1; i<=n; i++){int x, y;int Mi = M / m[i];extend_Euclid(Mi, m[i], x, y);ans = (ans + Mi * x * a[i]) % M;}if(ans < 0) ans += M;return ans;}【扩展中国剩余定理】当模数mi两两互质时有以上解法，当模数不确定是否两两互质呢？摘⾃博客:https:///acdreamers/article/details/8050018这种情况就采⽤两两合并的思想，假设要合并如下两个⽅程那么得到在利⽤扩展欧⼏⾥得算法解出的最⼩正整数解，再带⼊得到后合并为⼀个⽅程的结果为这样⼀直合并下去，最终可以求得同余⽅程组的解。

解：取模15的绝对最小完全剩余系：-7, , -1, 0,1,7,直接代入检验知x 6,3是解，
所以同余式有两个解： x 6(mod15), x 3(mod15)
注：①同余式x x 0(mod p)有p个解
p
（由Fermat小定理可得）
②同余式f ( x) ms( x) 0(mod m)与（2）等价 特别地，一个同余式中系数为模的倍数的项去掉 后，同余式的解不变。
qd k x =x0 m d m x0 mq k d m x0 k (mod m)，k 0,1, 2,, d 1 d
（3）
m 但x0 k , k 0,1, 2, , d 1是对模m两两不同余的，故 d （1）有d 个解，即（3）
例2
求解18x 30(mod 42)
一般地用数学归纳法不难证明同余方程
a1 x1 ak xk b(mod m)有解的充要条件为d b , d (a1 , , ak , m), 此时有m k 1d 个解
第二节
孙子定理
我国古代的《孙子算经》里有问题如下： “今有物不知其数，三三数之剩二，五五数之剩三， 七七数之剩二，问物几何？”“答曰二十三”. 这是一个求解同余式组的问题，《孙子算经》 已给出了求解方法，即为下面的孙子定理:
例3、求解9 x 21(mod30)
解： (9,30) 3 21， 同余式有3个解
将同余式化为9x 30 y 21 或3x 10 y 7
上述不定方程有一组解为x 1, y 1
则同余式的3个解为：x 1,9,19(mod30)
注：由ax b(mod m) 或my b(mod m)，
第三四节高次同余式一质数模的同余式其中是质数1定理同余式与一个次数不超过的质数模同余式等价xqxrx利用带余除法及费马小定理可得出结论埃菲尔铁塔的整个塔体结构高耸上窄下宽给人以平衡稳定的美感

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

. -同余的性质及应用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作用. 感谢孙善辉老师的帮助和指导！在我论文的撰写和校对过程中, 还得到了许多同学的帮助, 是他们帮助我发现论文里的某些小小的错误, 这使我节省了时间去完成其他的工作, 在此向他们表示感谢.最后, 再次感谢孙善辉老师的辛勤指导！。

数论一些基本概念定义1.设a, b是整数, b ≠0. 如果有一个整数c, 它使得a = bc, 则a叫做b 的倍数，b叫做a的因数。

我们有时说，b能整除a或者a能被b整除如果b能整除a，我们就用b|a这个符号来表示它，例如2|4，3|6，-5|20 如果b不能整除a，我们就写作b∤a，例如2∤3，3∤7，-5∤13整除的性质：(1) 若a|b, b|c，则a|c;(2) 若a|b, 那么对所有整数c, a|bc;(3) 若c|a且c|b，则c|(ma+nb) (m,n为整数）；(4) 若b|a且a!=0，则|b|<=|a|;(5) 若cb|ca, 则b|a;定义2. 一个大于1的正整数，只能被1和它本身整除，不能被其他正整数整除，这样的正整数叫做素数（也叫质数）定义3. 如果一个正整数a有一个因数b，而b又是素数，则b就叫做a的质因数引理1. 如果a是一个大于1的整数，而所有≤a的质数都除不尽a，则a是素数（希望会证明）最大公约数和最小公倍数表示法1.若d是a1,a2,a3,…,a n 的最大公约数，则表示为d = (a1,a2,a3,…,a n)引理2.假设a和b都是正整数，且a>b，a = bq +ｒ, 0 < r < b,其中q, r都是正整数，则a和b的最大公约数等于b和r的最大公约数，即：(a, b) = (b, r)我们求最大公约数就可以使用这个方法：辗转相除法（又叫欧几里德算法）int gcd(int a, int b){if(b == 0) return a;else return gcd(b, a%b);}//辗转相除法扩展欧几里德算法：//这个算法很重要，等等还要用到它，希望能够认真理解o(∩_∩)o…若(a, b) = d, 则必定存在整数x, y使得ax + by = d由于ax + by = dbx0 + (a%b)y0 = d在计算机中a%b = a – (a/b) * b所以bx0 + (a%b)y0 = bx0 + [a – (a/b) * b]y0 = a y0 + b(x0– (a/b) y0) = a x + b y 对照a, b系数，可由不定方程bx0 + (a%b)y0 = d的解x0 ,y0得ax + by = d的解x = y0 , y =x0– (a/b) y0而初始条件为ax + 0*y = d = a明显，这个不定方程的一组解为x = 1, y = 0所以我们可以把扩展欧几里德算法的代码写成这样：int extended_ gcd(int a, int b, int &x, int &y){int t, gcd;if (b == 0) {x = 1; y = 0;return a;}gcd = extended_ gcd (b, a%b, x, y);t = x;x = y;y = t – a / b * y;return gcd;}表示法2.如果m是a1,a2,a3,…,a n 的最小公倍数，则表示为m = {a1,a2,a3,…,a n} 引理3. 若a, b的最大公因数为d = (a, b)，则a, b的最小公倍数m = ab/d 我们求最小公因数就可以先求出最大公因数，再求出最小公倍数二元一次不定方程我们将讨论二元一次不定方程：ax + by = c (1)的整数解问题在这里可以看到扩展欧几里德算法的用处设a, b的最大公因数为d = (a, b), 则a = a1d, b = b1d, (a1, b1) = 1于是(1)式可以表示为：d(a1x+b1y) = c所以说只有当d|c时(1)式才有整数解这也是我们用来判断一个二元一次不定方程是否有整数解的方法定理:在二元一次不定方程ax + by = c (a > 0, b > 0, c > 0, (a, b) = 1)中，若x0, y0 是一组解, 则该方程的一切解都可以表示为x = x0– bt, y = y0 + at (t ∈Z)由上述定理可知，利用扩展欧几里德算法求解不定方程ax + by = c的方法步骤如下：1.判断是否有解，若(a, b)∤c，则无解，若有解则方程两边同除(a, b)得新的方程: a0 x + b0 y = c0其中a0 = a / (a, b), b0 = b / (a, b)，c0 = c/(a, b) 且(a0, b0) = 1;2.利用扩展欧几里德算法求解a0x0 + b0y0 = (a0, b0) = 1的解则c0x0 , c0y0 就是a0 x + b0 y = c0 的一组解3.利用上述定理，可得所有的解可以用x = c0x0 + b0t y = c0y0 - a0t (t ∈Z)来表示例题：pku1061，青蛙的约会两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。

一次同余式与孙子定理知识扫描：1:本节将讨论一次同余方程和由此引申出的重要定理一一孙子定理，首先介绍若干概念。

设整系数多项式f x二a n x n• ||| •• a0,若有整数c,满足f c三0 modm ,则称c是满足同余方程的解，记作x三c mod m .(注：这是因为除以x 余c的数都满足这样方程)。

当且仅当c!,c2都是方程的解，且G与c模m不同余时，我们称d,c2是方程的两个不同解。

一般情况，我们说同余方程的解数，即指模仃两两不同余的解的个数。

2:最简单的同余方程是一次同余方程ax三b modm , m ?a同余方程有解的充要条件是a,m /b(注：必要性，若有解，则b可用a,x的式子表达，所以a,m /b;充分性，一^互素(a,m)(a,m)a m a m则可知p q 1= b p q b = b,因为a,m /b,则可知(a,m) (a,m) (a,m) (a,m)ax三b mod m有解)。

特别地，在(a,m)=1时，同余方程必有解。

事实上：(a,m)= 1, x遍历模m 的一组完系时，aX j也遍历模m的一组完系。

因此，有且仅有一个r0 =xi使得aX i三ar0三b modm，即同余方程至多有一个解。

进一步，一定存在a■使得a[_a三1(modm \于是x三a j(m^b(modm),即为(a,m )=1时，同余方程的解。

3.设k ■1,a i,b i是整数，m j是正整数，i=1,2, ||(,k,则称下面这k个同余式r=^mod m1)』a2x +b2三0(modm2)IIIa k x +b k三0(mod m k)为一次同余方程式组，显然，其中若有一个同余方程无解。

则方程组无解。

当其中每个同余方程都有解时，可将求解转化为求若干个下述方程的解。

x 三G(mod m1)』x 三q (mod m2)IIIx 三厲(mod m k)为了讨论上式的本质，我们先来看k=2的情况。