第一讲--整数与同余理论

第一讲 整数与同余理论本讲介绍有关整数的一些基本概念、性质与定理.主要包括整数的整除性、奇偶性，以及依据整除性而产生的质数与合数、带余除法、最大公约数与最小公倍数. 同时简单介绍同余式的一些最基本的知识及有关重要定理，如欧拉定理、中国剩余定理(CTR).______________________________________________________________________________§1. 1 整数的基本概念、性质与定理自然数和它的相反数，以及零均称为整数. 定义1. 1 设a 与b 是任意两整数且0b≠，若存在整数q 使得a bq =，则称b 整除a 或a 能被b整除.记作|b a ；否则，称b 不能整除a 或a 不能被b 整除，此时记作b a Œ.如果|b a ，则称b 是a 的约数或因数，a 是b 的倍数；若b 是a 的约数但1,b a ≠±±，则称b 是a的真约数或真因数.定理1. 1 设,,,,a b c m n 是整数, 则有 i)|a a ；ii) 如果|a b 且|b a ，则b a±=；iii) 如果|a b 且|b c ，则|a c ； iv) 如果|a b 且|a c ，则|()a mb nc +.定理1. 2（带余除法定理） 对任意两整数a 与b 且b ≠0，则存在唯一的一对整数q 与r ，使得a qb r =+，其中0||r b ≤<.q 称为a 被b 除得到的商，r 称为a 被b 除得到的余数.我们借助自然数集的最小数原理来证明该定理:自然数集的最小数原理 若S 是广义的自然数集的任一非空子集，则存在a S ∈使得x ∀∈S ，有a x ≤成立，此a 称为S的最小数.定理1.2的证明 设{}S=|, 0a kb k a kb -∈-≥ ，则S 是广义自然数集的非空子集，于是存在S 的最小数r ，即存在∈ q ，使ra qb =-，亦即a qb r =+.下面证明0||r b ≤<且q 与r 是唯一的.（注：广义自然数集可包含零及正无穷大这两个元素.）若||rb >，则0||(1)r b a q b S <-=-±∈且||r r b >-，这与r 是S 的最小数矛盾.若存在两整数1q 与1r ，使得11a q b r =+，10||r b ≤<,则11q b r qb r +=+,即11()q q b r r -=-.若1q q ≠，则1||r r b -≥，这与10,||1r r b ≤<-矛盾，故1q q =，于是1r r =. ▋显然，a 被b 整除的充分且必要条件是其余数为0. 例1. 1 设89a=-,13b =, 则7q =-, 2r =.练习1. 11. 证明对任意整数n 有6(1)(21)n n n ++.2. 如果b a 32+与b a 59+中有一能被17整除，那末另一数一定也能被17整除.3. 证明：700a a ，其中00a a 表示一个四位数{1,2,,9}a ∈ .§1. 2 整数的奇偶性奇偶数的定义：能被2整除的整数称为偶数；不能被2整除的整数称为奇数. 基本性质：1）两个整数的和与差具有相同的奇偶性.2）奇数的平方被4除余1，被8除也余1，而偶数的平方能被4整除.3）如果若干个整数的乘积是奇数，则每个因数都是奇数；如果若干个整数之积是 偶数，则至少有一个因数是偶数.例1. 2 在广场上有m （奇数）个学生面向南方排成一行，命令其中n （偶数）个学生向后转，称作一次“反向运动”，证明：无论作多少次“反向运动”（转向后的学生允许再转动），都不可能使所有的学生全部面向北方.证 假设做k 次“反向运动”后，可使全体学生面向北方，又设各学生“向后转”的次数分别为1,,m x x ,而对每个学生来说，从面向南方变为面向北方，必须经过奇数次“向后转”，即1,,m x x 均为奇数，又m 为奇数，所以1m x x ++ 是奇数.另一方面，每次“反向运动”均是n 个学生的“向后转”，所以k 次“反向运动”所作的“向后转”总次数应为kn ，故有12m x x x kn +++= ，但该等式左边是奇数，而右边是偶数，矛盾. ▋练习1. 21.44⨯的方格纸上填着1,9,9,8这四个数字，如图所示，问是否可能在余下的方格内各填入一整数，使得方格纸上的每一行和每一列都构成等差数列9198表1. 12. 已知多项式32xbx cx d +++的系数均为整数，且bd cd +是奇数，证明：此多项式不可能分解成两个整系数多项式之积.3. 将下图表1.2中任何一行或一列作全部变号操作，问可否经过若干次这样的操作使表1.2变为表1.3？++-++---+ --++----+表1.2 表1.34. 若a 是奇数，且3a Œ,求证：224|(1)a -.§1. 3 最大公约数与最小公倍数本节利用带余除法，引入辗转相除法，并由此介绍最大公约数与最小公倍数.定义1. 2 设12,,,n a a a 是(2)n n ≥个整数.若整数d 是每个i a 的因数，则称d 是12,,...,n a a a 的一个公因数.定义1.3 整数12,,,n a a a 的公因数中的最大者称为它们的最大公因数，记作12(,,,)n a a a 或12gcd(,,,)n a a a .显然，若12,,,n a a a 中至少有一个非零.比如说0ia =/，则12(,,,)n a a a ia ≤，因而此时12,,,n a a a 的最大公因数存在.定义 1. 4 如果12(,,,)1n a a a = ，则称12,,,n a a a 互素（或互质）；如果i j=/时有(,)1i j a a =，则称12,,,n a a a 两两互素（或互质）.显然，若后者成立，则前者也成立，反之则不然.如(3,5,10)1=，但(5,10)1=/.性质定理1.1 设12,,,n a a a 是n 个不全为零的整数，则有 i) 12212(,,,)(,,,,)n n i i i i a a a a a a a = ，其中12,,,n i i i 是1,2,3,,n 的一个排列； ii)1212(,,,)(||,||,,||)n n a a a a a a = ；iii) 若12,,,n a a a 中有一个为1, 则它们互素； iv) 若12,,,s jj j a a a 是12,,,n a a a 中全不为零的整数，则1212(,,,)(||,||,,||)s n j j j a a a a a a = .以上性质的证明均显而易见. 定理1. 3 如果a bq r =+,则有(,)(,)a b b r =.证 设(,)a b d=及1(,)b r d =，则一方面，d a d b 且，于是由a bq r =+得|d r ，从而1d d ≤. (1.3.1)另一方面，1|d b 且1|d r ，以及a bq r =+得1|d a .从而1|d d . (1.3.2)综合(1.3.1)与(1.3.2)即得1d d =. ▋辗转相除法 设,a b 是任意两个正整数，多次利用带余除法，可得下列诸等式：111122212111111 0, 0, 0, 0.k k k k k k k k k k k a b q r r b b r q r r r r r q r r r r r q r r ----+++=+<<⎫⎪=+<<⎪⎪⎬⎪=+<<⎪=+=⎪⎭()* 由于b 是有限正整数，且1210k k b r r r r +>>>>>= ，所以()*中的正整数k 是存在的.辗转相除法()*是我国古代筹算家的一大成就，西方Euclid(欧几里德)也推得该法则，所以又称为Euclid 算法.定理1. 4 设,a b 是任意给定的两整数，则由()*式可得，(,)k a b r =.证明 反复利用定理1. 3有1121(,)(,)(,)(,)(,0)k k k k a b b r r r r r r r -====== . ▋例1. 3 设1895a =-, 1573b =, 求(,)?a b =解(,)(1895,1573)(1859,a b =-=. 反复利用定理1.3，如下面的辗转相除计算图. 再由定理1. 4即得 (,)(1859,1573)143a b ==. ▋图1.4定理1. 5a 与b 的任一公约数是(,)a b 的约数.证 设d 是a 与b 的任一公约数，则由()*知d 是b 与1r 的公约数，进而知d 是1r 与2r 的公约数，如此继续，可得d 是k r 的约数. ▋定理1. 6 （扩展Euclidean 等式）若1(,,)n a a d = ，则必存在整数(1,,)i k in = 使1122n n k a k a k a d +++= .推论1.112(,,,)1n a a a = 的充要条件是存在12,,,n t t t ∈ 使2q =51859 15731573 1430 1=1q2=3q 286=1r286 143=2r0=3r11221n n t a t a t a +++= .定理1. 7 设12,,,n a a a 是任意n 个整数.且122(,)a a d =，233(,)d a d =, ,1(,)n n n d a d -=，那么12(,,,)n n a a a d = .性质定理1.2 i) 如果(,)1a b =,则(,)(,)ac b c b =； ii) 如果(,)1a b =，且b ac ，则b c ；iii) 如果(,)1a c =，且(,)1c b =，则(,)1ab c =；iv) 如果()0cc >是a 与b 的公约数,则()(,),a b ab c cc =，进而有,1(,)(,)a b a b a b ⎛⎫= ⎪⎝⎭. 以上性质均易证明(请读者自证).以下我们讨论最小公倍数: 定义1. 5 设12,,,n a a a 是(2)n n >个整数.i) 如果d 是每个i a 的倍数，则称d 是这n 个数的公倍数； ii)12,,,n a a a 的一切公倍数中的最小正整数称为它们的最小公倍数，记为12[,,,]n a a a .由于任意正数均不是0的倍数，所以任意包含0的一组整数其最小公倍数均不存在. 性质定理1.3 设12,,,n a a a 是n 个全不为零的整数，则有 i) 12120[,,,]||n n a a a a a a <≤ . ii) 1212[,,,][||,||,,||]n n a a a a a a = . iii)1212[,,,][,,,]||n n a k a k a k a a a k = .以上性质请读者自证.定理1. 8 设,a b 是任意两个全不为零的整数，若m 是,a b 的任意一公倍数，则有 i) [,]|a b m ；ii)[,](,) (0)a b a b ab ab =>;iii),[,]m m m a b a b ⎛⎫= ⎪⎝⎭.类似于定理1. 7，我们有：定理 1. 9 设12,,,n a a a 是n 个全不为零的整数，122[,]a a m =，233[,]m a m =，…，1[,]n n n m a m -=，则有 12[,,,]n n a a a m = .例1. 4 i ）求[136,221,391]?= 解 i)[][]136221136,221,391[[136,221],391][,391]1768,39117⋅===.17683914066417⋅==. （其中因为()136,22117=）. ▋练习1. 31. 对给定正整数,,a b c ，证明1) 如果a b ，那么a bc . 2) 如果a b 且a c ，那么2a bc .3)a b 当且仅当ac bc ，其中0c ≠.2. 对于任意的正整数a ，则三个整数, 2, 4a a a ++中必有一个能被3整除.3. 对于任意的正整数a ，证明2|(1)a a +，3|(1)(2)a a a ++.4. 设n 是正整数，证明[,][,]nn n ab a b =.5. 证明121121[,,,,,,][[,,,],[,,]]k k n k k n a a a a a a a a a a ++= .6. 证明下列结论1) 如果a 是奇数，那么224|(1)a a-；2) 如果,a b 都是奇数，那么22|()a ab -；3) 对于任意的整数a ，都有222360|(1)(4)a a a --.§1. 4 质数与合数我们可以将整数分成两类，即奇数类与偶数类；当我们讨论正整数时，也可以将大于1的正整数分为两类，对于任何一个正整数a ,它至少有两个正约数，即1与a , 称a 得当然约数.有些正整数只是这两个当然约数，如3，5，7等，而另一些正整数则还有其它正约数，如6，还有约数2与3，这类约数称非当然约数或真约数.定义1. 6 设a 是一个大于1的正整数，如果a 只有当然约数，则称a 为质数或素数；若a 有真约数，则称a 为合数.于是，正整数={1} 质数集合数集. 性质定理1.4 设p 是任一质数，则有i) 对任一整数a , 有(,)1a p =或|p a .ii) 如果|p ab , 则|p a 或|p b .iii) 如果12|n p a a a 则存在某i , 使|i p a .证 i ） 因为(,)|a p p , 而p 为质数，于是(,)1a p =或p , 若(,)a p p =，即有p a .ii) 如果p a Œ, 则由（i ）知(,)1a p =，由已知p ab ，于是由性质定理1. 4知p b .iii) 此条是ii ）的推广. ▋ 例1. 5 如果m 是合数，试证11m mn = 也是合数. 证 设mab =，那么()1101(10)1(101)(10101)a b m a b a a --=-=-+++即(1)911911(10101)a b a m a -⋅=⋅⋅+++ 个个. 所以11a 个是m n 的因数. ▋ 练习1. 41. 证明奇素数可表示为两个自然数的平方差.2. 设n 是大于2的整数，则如果2121nn +-和中有一为素数，那么另一数必为合数.3. 试证正整数20001001 个是合数. 4. 设p 和n p +1均为素数，则2p =且n 为2的方幂.§1. 5 整数的分解—算术基本定理任一大于1的整数a 或者是素数，或者是合数，如果a 是一个合数，设1p 是a 的大于1的最小的正约数，则1p 是一个素数，且存在正整数1q 使111,(1)a p q q a =<<. 如果1q 是一个素数，则a 就表成了两个素数之积，如果1q 非素数，则1q 有素因数2p ，于是122a p p a =.如果2a 是素数，则就表成三个素数之积，否则2a 有素因数3p ，如此继续下去，可知a 一定可以表成若干个素数之积.算术基本定理 设a 是任一大于1的整数，则a 能表成若干个素数的积： a =12n p p p , 12n p p p ≤≤≤ . (1.5.1)其中12,,,n p p p 是素数，且表达式(1.5.1)是唯一的.算术基本定理也可以称为整数的唯一分解定理.(1.5.2)式中的素数i p 可能有相同的，我们将相同的素因数合写成方幂的形式，则有1212,0,(1,2,,)k k i a p p p i k αααα=>= ,其中()i j p p i j <<是素数.推论1.4 设a 与b 是任意两个正整数，其标准分解式为1212,0,(1,2,,),s s i a p p p i s αααα=≥= 1212,0,(1,2,,),s s i a p p p i s ββββ=≥=则1212(,),s s a b p p p γγγ= ，其中min(,)i i i γαβ= (1.5.4) 1212[,],s s a b p p p δδδ= 其中max(,)i i i δαβ= (1.5.5)及(,)[,]a b a b ab =.练习1. 51. 分别求2160及129999个的标准分解式. 2. 利用Maple 或Mathematica 函数求8203513468500的标准分解式. 3. 设,,a b c 是任意整数，则有1）max(min(,),min(,))min(,max(,))a b a c a b c =； 2)[(,),(,)](,[,])a b a c a b c =.§1. 6 Euler 函数定义1. 7 对任意正整数n , 定义()n ϕ为不超过n 且与n 互质的正整数的个数. 则()n ϕ是定义域为 的一个函数, 称为Euler(L.Euler,1707—1783)函数.如(1)1, (2)1, (4)1, (10)4ϕϕϕϕ====. 易知Euler 函数有如下性质：Euler 函数的基本性质定理1.5： i). 若p 是素数, 则()1p p ϕ=-; 反之亦成立. 即若p 为合数, 则有()2p p ϕ≤-；ii) 不超过n 且与n 互质的所有自然数的和为1()2n n ϕ；iii) 若p 是素数, 则1()(1)k k p p p ϕ-=-；iv) 若12m m m =, 且12(,)1m m =, 则12()()()m m m ϕϕϕ=； v) 若1212tt n p p p ααα=是n 的质数分解, 则12111()(1)(1)(1)tn n p p p ϕ=---11(1)tii n p ==-∏或|1(1)p n n p -∏（p 为素数）;证 i) 显然.成立. ii) 若()12,,,n a a a ϕ是不超过n 且与n 互质的所有自然数, 则()12(),(),,()n n a n a n a ϕ---亦是不超过n 且与n 互质的所有自然数, 因此必有()1212()()()()n n a a a n a n a n a ϕϕ+++=-+-++- .于是12()2()()n a a a n n ϕϕ+++=⋅ ,即ii) 成立.iii) 因为不超过kp且与kp不互素, 即与p 不互素的所有自然数为1,2,,k p p p p - , 共为1k p -个整数, 故不超过kp且与kp互素的所有正整数的个数为1k k p p --, 即1()(1)k k p p p ϕ-=-.iv) 我们运用概率知识来证明该条. 记{}1,2,,m Ω=;{}|(,)1E x x m =∈Ω=; {}|(,)1,1,2.i i E x x m i =∈Ω== 则121212,(),(),()m E m E m m E m m ϕϕϕΩ====.设事件A 指从Ω中随机取一数, 该数属于E ；事件i A 指从Ω中随机取一数, 该数属于(1,2)i E i =.因为任意的x ∈Ω,有(,)1x m =当且仅当且1(,)1x m =,2(,)1x m =, 即事件A 发生当且仅当事件1A与事件2A 同时发生. 由于12(,)1m m =, 故1A 与2A 是相互独立的. 从而1212()()()()P A P A A P A P A == .但是()()P A E m m ϕ=Ω=,112111()()()P A E m m m m m ϕϕ=Ω==, 121222()()()P A E m m m m m ϕϕ=Ω==.所以1122()()()m m m m m m ϕϕϕ=⋅.即12()()()m m m ϕϕϕ=. ▋v ）由ⅲ）有11()(1)(1)ii i ii i i ip p p p p αααϕ-=-=-, 1,2,,i t = . 从而由ⅳ）得 1212()()()()tt n p p p αααϕϕϕϕ=121212111(1)(1)(1)t t tp p p p p p ααα=--- 12111(1)(1)(1)tn p p p =--- 11(1)ti in p ==-∏ (i p 为n 的全部不同的素因子) |1(1)p nn p =-∏ (p 为素数) . ▋下面我们介绍Euler 函数的若干应用. 例1. 6 证明：素数有无穷多个. 证 设素数只有有限个12,,,n p p p .令12n a p p p = , 则在1到a 的所有正整数中与a 互素的只有一个, 即1. 因此()1a ϕ=, 但12()()n a p p p ϕϕ=12()()()n p p p ϕϕϕ=12(1)(1)(1)1n p p p =---> ,矛盾. 所以素数有无穷多个. ▋例1. 7 设1()3n n ϕ=, 求?n = 解 设1212tt n p p p ααα=是n 的素因数分解, 且12p p p t <<< , 则由1()3n n ϕ=得等式121212121111(1)(1)3t t t t t p p p p p p p p αααααα--= .即有1123(1)(1)t tp p p p p --= . (2.2.2) 因为12p p p t <<< , 且1|3(1)(1)t t p p p -- 及t p 为素数知3p t >, 从而1t =或2. 如果1t=, 则13n α=. 由(2.2.2)式得3(31)3-=, 矛盾. 故2t =. 从而122,3p p ==. 此时,1223n αα=且(2.2.2)成立. 即1()3n n ϕ=成立. 所以1223n αα=,其中1α,2α是大于0的整数. ▋练习1. 61. 计算欧拉函数值(2008)ϕ.2. 求下列数论方程的所有正整数解.1）()(2)x x ϕϕ=; 2)(3)(4)x x ϕϕ=;3. 证明分母不大于n 的既约真分数的个数等于(2)(3)().n ϕϕϕ+++§1. 7 同余的定义及性质定义1. 8设m 是一给定的正整数, a 与b 是两个整数, 如果用m 分别去除a 与b .若得到的余数相同,则称a 与b 关于模m 同余, 记作(mod ),a b m ≡并称为同余式；若得到的余数不相同, 则称a 与b 关于模m 不同余, 记作(mod )ab m ≡/.依定义,任何一个偶然与0关于模2同余,任何一个奇数与1关于模2同余, 即有20(mod 2)n ≡, 211(mod 2)n +≡()n ∈ .再如3655(mod12)7(mod12)≡≡-. 显然对任何一整数a 与b 均有(mod1)ab ≡.对任意两个不同的素数p 与q 有：(mod )q p q ≡/及(mod )p q p ≡/.关于同余的性我们有如下定理同余的性质定理1. 5 设m 是给定的正整数,111222,,,,,,,,a b c a b c a b c 是整数,则有 i)(mod ),a b m ≡成立的充要条件是|m a b -.ii) 同余是一个等价关系, 即有a)(mod ),a a m ≡ （反身性）.b) 若(mod ),a b m ≡ 则(mod )b a m ≡（对称性）.c) 若(mod )a b m ≡且(mod )a c m ≡,则(mod )a c m ≡（传递性）.iii) 若11(mod )a b m ≡,22(mod )a b m ≡, 则1212(mod )a a b b m ±≡±及1212(mod )a a bb m ≡.iv) 若(mod )a b m ≡.d 是m 的任一因数, 则(mod )a b d ≡.v) 若(mod )ab m ≡,d是,a b 及m 的任一公因数,则(mod )a b md d d≡. vi) 若()mod ac bcm ≡,则mod (,)m a b c m ⎛⎫≡ ⎪⎝⎭.特别当(,)1c m =时,有(mod )a b m ≡.vii) 若(mod ),1,2i a b m i ≡=. 则12(mod[,])a b m m ≡, 反之亦成立.特别当12(,)1m m =时,有1(mod )ab m ≡ 且2(mod )a b m ≡的充要条件是12(mod )a b m m ≡.viii) 若(,)1a m =, 则存在b使1(mod )ab m ≡.可称b为a关于模m的逆, 记为1(mod )b a m -=或1|m a -.以上性质的证明均较易,我们证明其中几条为,为方便证明,用符号“⇔”表示“当且仅当”. 证 i)(mod )a b m ≡⇔a 与b 用m 去除有相同的余数⇔a b -与0用m 去除有相同的余数|m a b ⇔-.ii)-c) 由i)(mod )a b m ≡且(mod )b c m ≡|m a b ⇔-且|m b c -|()()m a b b c ⇒-+-(mod )a c m ⇔≡.iii) 由i) 得11(mod )a b m ≡及22(mod )a b m ≡⇔11|m a b -及22|m a b -122112|(()())m a a b a b b ⇒-+-⇒1212|()m a a bb -1212(mod )a a bb m ⇔≡.vi) 由i)(mod )ac bc m ≡⇔|()m c a b -|()|()(,)(,)(,)m c m a b a b c m c m c m ⇔-⇒-（因为,1(,)(,)m c c m c m ⎛⎫= ⎪⎝⎭）mod (,)m a b c m ⎛⎫⇔≡ ⎪⎝⎭.vii) 由i) 知1(mod )ab m ≡且2(mod )a b m ≡1|m a b ⇔-且2|m a b -, 即a b -是1m 与2m 的公倍数, 从而12[,]|m m a b -. 再由i)12(mod[,])a b m m ≡此性质可推广至任意有限个模数12,,t m m m ⋅⋅⋅的情形.viii) 若(,)1a m =,则存在整数b 与c 使1ab mc +=.于是1()ab m c -=-. 即|(1)m ab -. 由i) 得1(mod )ab m ≡ . ▋以上性质形式简单, 证明容易, 但同余式类似普通等式的特点使其具有广泛的应用价值.下面是若于同余式性质的应用实例.例1. 8 求3652008的个位数字.解 即要求一个0到9之间的数a 使3652008(mod10)a ≡. 由于36533653652008(2108)108k =⨯+=+.所以36536520088(mod10)≡.又286044(mod10)=+≡,42846(mod10)≡≡.因此36549114919188(8)868688(mod10)⨯+==⋅≡⋅≡⋅≡.故8a =. ▋例1. 9 设A 是正整数,B 是A 的各数位上的数字之和, 证明(mod9)A ≡B . 证明 设101010,09nn i a a a a A =⋅+⋅⋅⋅+⋅+≤≤,0n a ≠. 则10n a a a B =+⋅⋅⋅++.由于101(mod 9)≡,1011(mod9)i i≡≡, i 为正整数. 所以 1010101011n n n a a a a a a ⋅+⋅⋅⋅+⋅+≡⋅+⋅⋅⋅+⋅+10(mod9)n a a a ≡+⋅⋅⋅++,即(mod9)A ≡B . ▋例1. 10 设正整数1010001000,01000n n i a a a a a =⋅+⋅⋅⋅+⋅+≤<.则7整除a 的充要条件是07|(1)ni ii a =-∑.证 因为10001(mod7),1000(1)(mod7)ii ≡-≡-, 所以由性质定理得10(1)(1)(mod7)n n a a a a ≡⋅-+⋅⋅⋅+⋅-+.故7|7|(1)ni i i a a =⇔-∑. ▋同样，因为10001(mod11)≡-及10001(mod13)≡-.我们可得011|11|(1)nii i aa =⇔-∑及13|13|(1)ni i i a a =⇔-∑.例1. 11 证明不定方程22286x y az -+=对任何给定的整数a 无整数解.证 设0x 、0y 及0z 是该不定方程的一组整数解, 即有22200086x y az -+=. (1.6.1)将上式关于2取模得22000(mod2)x y -≡. 因此0x 与0y 有相同的奇偶性. 再将(3.1.1)关于4取模得22002(mod4)x y -≡.因此0x 与0y 同为奇数.于是22001(mod8)x y ≡≡. 将(1.6.1)式关于8取模便得06(mod8)≡矛盾. 故原不定方程无整数解. ▋例1. 12 证明对任何整数n , 35711()1535f n n n n =++均是一个整数.证 只要证对任意正整数n 有 357530(mod15)n n n ++≡ (1.6.2)即可.由于35337532(mod3)n n n n n n n ++≡+≡-,而3(1)(1)(1)(1)n n n n n n n n -=-+=-⋅+是3的倍数, 故357530(mod3)n n n ++≡. (1.6.3)又3555753222()(mod5)n n n n n n n ++≡-≡-, 而52(1)(1)(1)n n n n n n -=-++及0n ≡或1±或2±(mod5). 当n ≡或1±(mod5)时,(1)(1)0(mod5)n n n -+≡当2(mod5)n ≡±时, 2(1)0(mod5)n +≡, 因此不论n 为何整数, 均有50(mod5)n n -≡, 故357530(mod5)n n n ++≡. (1.6.4)因为(3,5)1=,所以由性质定理vii) 及(1.6.3)与(1.6.4)即可推得(1.6.2)成立. ▋练习1.71. 1) 求3651999的最后两位数字.2) 求20001999表示成17进制数时的个位数及最后两位数.2. 证明20001999340(mod5)+≡.3. 证明若一个三位数的数字（0到9之间的数）是相邻的三个数字, 且百位上的数字大于个位上的数字, 则该位数与它的数字次序相反的三位数的差等于是198.4. 设十进制自然数21398a b （其中0,9a b ≤≤）为99的倍数, 求a 与b .5. 设n 为正整数, 证明22330|6511nn --.6. 假设131|111n, 求?n =§1. 8 同余类与剩余类定义1. 9 设m 是一给定的正整数, 则任意整数a 关于模m 同余0或1, 或2,⋅⋅⋅, 或1m -. 于是我们可将整数集划分成m 个类：所有与()01r rm ≤≤-同余的整数归为一类. 显然, 在同一类中的任两个整数关于模m 一定同余, 而不在同一类中的任两个整数关于模m 一定不同余. 每一个这样的类称之为模m 的同余类或模m 的剩余类. 从每个类中任取出一数, 则得到的这m 个数就称为模m 的完全剩余系, 又简称m 的完系.若记[]rm 为r 所在的模m 的同余类（或在明确模m 的情况下简记为r ）, 则有下列性质定理.定理1. 10 设m 是一给定的正整数, 则有 i) []{}r m r km k =+∈ . ii)[][]r m s m m r s =⇔-.iii) 对任意两整数,,r s 或者[][]r m s m =, 或者[][]r m s m =∅ .iv)k 个数12,,,k a a a ⋅⋅⋅构成的完系的充要条件是k m =,且当i j ≠时有(mod )i j a a m ≡/.以上性质由定义可直接得知.根据完系的定义, 对于给定的正整数m , 模m 的完系有无限个,下面我们给出几个常用的完系. 1) 模m 的最小非负完全剩余系：0,1,,1m - .2) 模m 的最小正完全剩余系：1,2,,m3) 模m 的最大非正完全剩余系：(1),(2),,1,0m m ----- .4) 模m 的绝对值最小完全剩余系：m 为偶然时：,,1,0,1,,122m m --- 或 1,,1,0,1,,22m m -+- .m 为奇数时：11,,1,0,1,,22m m ---- . 定理1. 11 若12,,,m a a a 是m 的一个完系,a 与b 是任意两整数且(,)1a m =, 则12,,,m aa b aa b aa b +++亦是m 的完系.证 由定理3. 2—iv), 只要证明对任何i j ≠,有(mod )i j aa b aa b m +≡+/ 即可.如果(mod )ij aa b aa b m +≡+, 则有(mod )i j aa aa m ≡. 因(,)1a m =,由定理3.2—vii)即得(mod )i j a a m ≡,这与12,,,ma a a ⋅⋅⋅为m的完系矛盾,所以(m o d )i j aa b aa b m +≡+.▋例 1. 13 若12,,,m a a a ⋅⋅⋅是m 的完系, ,a b ∈Z 且(,)1a m =, 则i aa b +除以m 的最小非负余数之和为1(1)2m m -.证 由定理3. 3知12,,,m aa b aa b aa b ++⋅⋅⋅+是m 的一个完系. 因此i aa b + （1,2i =,,m ⋅⋅⋅）除以m 而得的m 个最小非负余数构成m 的一个完系, 即它们构成m 的最小非负完全剩余系，所以它们的和为1012(1)(1)2m m m +++⋅⋅⋅+-=-. ▋ 在模m 的同余类中, 有些类中的每个数均与m 互素, 如1所在的同余类中每个数均与m 有互素. 若8m =, 则同余类1,3,5,7中的每个数均与8互素, 这样的同余类我们将给它们一个特定的名称.定义1. 10 设m 是一个大于1的正整数, 定义i ）模m 的同余类r 称为模m 的一个简化同余类；如果(,)1r m =.ii ） 在模m 的所有简化同余类中各取一数, 我们称这组数为模m 的一个简化剩余系, 又称简系. 如果r 是模m 的一个简化同余类,a 是r 中任一整数, 则0(mod )a r m -≡, 即存在整数k使a r km =+, 从而由(,)1r m =得(,)1a m =. 因此模m 的同余类是模m 的一个简化同余类的充要条件该余类中的每个数均与m 互素, 且由此可知,m 的简系中的每个数皆与m 互素, 于是我们有下列定理：定理1.12 k 个整数12,,,k a a a ⋅⋅⋅构成m 的简系的充要条件是：i)()k m ϕ=；ii) (,)1i a m =；iii) (mod ), i j a a m i j ≡≠/.证 (必要性) 由简系的定义知12,,,ka a a ⋅⋅⋅是从模m 的所有简化剩余类中各取一数而构成的.1,2,,m ⋅⋅⋅是模m 的一个完全剩余类, 于是模m 的所有简化剩余类组成的集合是{}|(,)1,1r r m r m =≤≤.由Euler 函数的定义可知：满足上面集合中条件的r 共有()m ϕ个, 因此模m 的简化剩余类共有()m ϕ, 故()k m ϕ=, 即i) 成立, 而ii) 及iii) 由简系的定义即知成立.(充分性) 由必要性证明知，模m 的简化剩余类共有()m ϕ,条件i)及ii)说明12,,a a,k a ⋅⋅⋅是模m 的简化剩余类中选取的()m ϕ个整数,再由条件iii)即知:12,,,k a a a ⋅⋅⋅是从模m 的全部()m ϕ个简化剩余类中各选取的一数而成,所以依定义,12,,,k a a a ⋅⋅⋅是的一个简系. ▋利用定理1. 12 我们便有下列结论：定理1.13 设a 与b 是满足(,)1a m =及|m b 的两整数, 若()12,,,m a a a ϕ⋅⋅⋅是m 的简系, 则()122,,,m aa b aa b aa b ϕ++⋅⋅⋅+亦是m 的一个简系.证 利用定理 1.12, 由(,)1a m =及|m b 便得(,)(,)(,)1ii i aa b m aa m a m +===. 且若当i j≠时, 有(mod )i j aa b aa b m +≡+, 则(mod )i j aa ab m ≡, 于是由(,)1a m =得,(mod )i j a a m ≡这与()12,,,m a a a ϕ⋅⋅⋅为m 的简系矛盾. 故(mod )i j aa b aa b m +≡+, 所以()122,,,m aa b aa b aa b ϕ++⋅⋅⋅+构成m 的简系. ▋定义1.11 设m 是一正整数, 则所有不超过m 且与m 互素的()m ϕ个数构成m 的一个简系, 我们称该系为m 的最小正简化剩余系（可简称最小正简系或缩系）.例如, 8的最小正简系为1, 3, 5, 7.15的最小正简系为1, 2, 4, 7, 8, 11, 13, 14.例1. 14 若p 为奇数, m 是任一正整数且满足21(mod )m p ≡, 证明12(1)0(mod )m m m p p ++⋅⋅⋅+-≡证 因p 为素数, 故1,2,,1p ⋅⋅⋅-是p 的简系, 又(2,)1p =, 从而由定理1.13知21, 22, , 2(1)p ⨯⨯⋅⋅⋅⨯-也是p 的简系, 因此得12(1)(21)(22)(2(1))(mod )m m m m m m p p p ++⋅⋅⋅+-≡⨯+⨯+⋅⋅⋅+⨯-.即有(21)(12(1))0(mod )m m m m p p -++⋅⋅⋅+-≡,亦即|(21)(12(1))m m m m p p -++⋅⋅⋅+-,但(21)m p -Œ, 所以必有|12(1)m m m p p ++⋅⋅⋅+-,于是12(1)0(mod )m m m p p ++⋅⋅⋅+-≡. ▋例1. 15 设1212,(,)1m m m m m ==, a 与b 是满足条件(,)1a b =, 1|m b 及2|m a 的任意两整数, 则i) 当x 跑遍1m 的完系,y 跑遍2m 的完系时,ax by +跑遍m 的完系. ii) 当x 跑遍1m 的简系,y 跑遍2m 的简系时,ax by +跑遍m 的简系.我们只证明ii).证 首先, 设()112,,,m x x x ϕ⋅⋅⋅是1m 的简系, ()212,,,m x x x ϕ⋅⋅⋅是2m 的简系, 则121()1(){|{,,}, {,,}}m m ax by x x x y y y ϕϕ+∈⋅⋅⋅∈⋅⋅⋅共有12()()m m ϕϕ个数, 即12()m m ϕ（()m ϕ=）个数, 定理1.12的第i) 条成立.其次, 如果12(mod )i j k ax by ax by m m +≡+ ,那么1(mod )i j k ax by ax by m+≡+ , 由1|m b 得1(mod )i ax ax m ≡ . 再由(,)1a b =知1(,)1a m =,从而有1(m od )i x x m ≡ , 即有i = . 同理可证j k =. 因此, 定理1.12的第iii)条成立.最后证12(,)1ij ax by m m +=成立.因为1(,)1i x m =, 又由(,)1a b =及1|m b 知1(,)1a m =, 故1(,1i ax m =). 再由1|m b 可得1(,)1i j ax by m +=.同理可证2(,)1i j ax by m +=.因此, 由12(,)1m m =, 即得12(,)1i j ax by m m +=.从而根椐定理1.12便知i j ax by +（11,,()i m ϕ=⋅⋅⋅,21,,()j m ϕ=⋅⋅⋅）是12m m m =的简系. ▋特殊情形, 可取21,a m b m ==.定理1. 15（Euler 定理） 设m 是任一给定的正整数，a 是任一整数且(,)1a m =, 则有()1(mo d )m a m ϕ≡. (1.8.1) 证 设12(),,,m x x x ϕ⋅⋅⋅是m 的一个简系, 则由(,)1a m =及定理1.13知()12,,,m ax ax ax ϕ⋅⋅⋅亦是m 的一个简系, 因此有12()12()(mod )m m x x x ax ax ax m ϕϕ⋅⋅⋅⋅≡⋅⋅⋅⋅.即()12()12()1()(mod )m m m a x x x x x x m ϕϕϕ⋅⋅⋅⋅≡⋅⋅⋅⋅. (1.8.2)而由于(,)1, 1,2,()i x m i m ϕ==⋅⋅⋅, 故()12(,)1m x x x m ϕ⋅⋅⋅⋅=, 于是便得()1(mod )m a m ϕ≡. ▋ 定理1. 16（Fermat 定理） 若p 是一素数, a 是任一整数, 则有(mod )p a a p ≡. (1.8.3)证 若(,)1p a =, 则由Euler 定理及()1p p ϕ=-得11(mod )p a p -≡,再由(mod )a a p ≡便有(mod )p a a p ≡.若(,)1p a ≠, 即|p a , 则0(mod )p a a p ≡≡, 即有(mod )p a a p ≡, 所以(1.8.3)成立. ▋例1. 16 求20011999除70的余数是多少？解 因(1999,70)1,= (70)(2)(5)(7)24ϕϕϕϕ=⋅⋅=, 所以由Euler 定理得2419991(mod70)≡.而200183249=⨯+及1999287039=⋅+, 故2001248391999(19991999=⋅)83911999≡⋅9919993929(mod70)≡≡≡.所以20011999除70的余数是29. ▋例1. 17 求证199819981998122000++⋅⋅⋅+是1999的倍数.证 因1999是素数, 故(1998ϕ=1999).于是由Euler 定理得19981(mod1999), 1,2,,1998,2000k k ≡=⋅⋅⋅从而1998199819981998199812199819992000++⋅⋅⋅+++1110119990(mod1999)≡++⋅⋅⋅+++≡≡.这说明199819981998122000++⋅⋅⋅+是1999的倍数. ▋例1. 18 证明对于任意整数n , 有7(mod 42)nn ≡. 证 由Fermat 定理, 7(mod7)n n ≡. 此外76242(1)(1)(1n n n n n n n n -=-=--+）42(1)(1)(1)0(mod6)n n n n n =-+-+≡，从而有 70(mod 42)n n -≡. ▋练习1.81．分别针对下列三种情况求模15的一个完系, 使i) 该完系的每个数是偶数；ii ）该完系的每个数是奇数；iii ）该完系的每个数是绝对值最小的.2．将上题1的“模15”换成“模12”后能否完成此题？3．设12,,,k a a a ⋅⋅⋅是模(2)m >的一个简系, 证明10(mod )ki i a m =≡∑.4．求模3的一个完系{}123,,a a a 及模5的一个完系{}12345,,,,b b b b b 使得 i){}|1,2,3;1,2,3,4,5i j a b i j == 构成模15的一个完系. ii ）{}|1,2,3;1,2,3,4,5i j a b i j +==及{}|1,2,3;1,2,3,4,5i j a b i j ==同时是模15的完系. 5．将题7的“完系”换成“简系”后结论仍成立吗？6．设12,m m 是正整数, 证明当x 跑遍1m 的完系及y 跑遍2m 的完系时, 则1x m y +跑遍12m m 的完系.§1. 9 一次同余方程同余方程可以说是同余理论的核心, 象著名的中国剩余定理（孙子定理）及在公钥密码学很有应用价值的Legendre 符号均源自于同余方程.定义1. 12 设m 是一个大于1的正整数，(0),a b ≠是两个整数, 称同余式0(mod )ax b m +=, 其中m a Œ. (1.9.1)为x 的模m 的一次同余方程, 简称模m 的同余方程.如果整数0x 满足00(mod )ax b m +=, 那么所有关于模m 同余于0x 的整数均满足方程(1.9.1). 由此, 我们称0(mod )x x m ≡是方程(1.9.1)的一个解.设(,)a m d =, 如果(1.9.1)有解0(mod )x x m ≡, 则00(mod )ax b m +≡,于是由d m 及0d ax 知d b .这说明d b 是(1.9.1)有解的必要条件.下面我们证明该条件也是(1.9.1)有解的充分条件, 即有定理 1. 17 同余方程(1.9.1)有解的充要条件是d b .当(1.9.1)有解时, 其解数为d ,若0(mod )x x m ≡为(1.9.1)的一个, 则其d个解为 0(mod )m k m dx x +≡, 0,1,,1k d =- . (1.9.2) 证明 必要性已经证明. 现证明充分性. 设d b , 由(1.9.1)得0mod a b m x d d d ⎛⎫+≡ ⎪⎝⎭ (1.9.1)* 因,1a m d d ⎛⎫= ⎪⎝⎭, 故由Euler 定理知1mod m d a m d d ϕ⎛⎫ ⎪⎝⎭⎛⎫⎛⎫≡ ⎪ ⎪⎝⎭⎝⎭. 将(1.9.1)*两端乘1m d a d ϕ⎛⎫- ⎪⎝⎭⎛⎫ ⎪⎝⎭便得10mod m m d d a b a m x d d d d ϕϕ⎛⎫⎛⎫- ⎪ ⎪⎝⎭⎝⎭⎛⎫⎛⎫⎛⎫+⋅≡ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭, 即 1mod m d b a m x d d d ϕ⎛⎫- ⎪⎝⎭⎛⎫⎛⎫≡- ⎪ ⎪⎝⎭⎝⎭. (1.9.3) 这说明(1.9.3)是方程(1.9.1)*的一个解.进而可以验证1mod m d b a m xd d d ϕ⎛⎫- ⎪⎝⎭⎛⎫⎛⎫≡- ⎪ ⎪⎝⎭⎝⎭是(1.9.1)的一个解, 充分性得证.若0(mod )x x m ≡是(1.9.1)的一个解, 则易证0(mod )m k m d x x +≡ (0,1,k =, 1d -) 是(1.9.1)的d 个不同的解.如果1(mod )x x m ≡是(1.9.1)的任一解, 即10(mod )ax b m +≡, 则由0(mod )x x m ≡得10()0(mod )a x x m -≡.于是10|()m a x x -, 从而10()m a x x d d -.因为,1m a d d ⎛⎫= ⎪⎝⎭, 故有10|()m x x d -, 亦即存在整数t , 使得10m x x t d=+.设t ld k =+,01k d ≤≤-, 则 1000()(mod )m m m x x ld k x k ml x k m d d d=++=++≡+, 即10(mod )m x x k m d =+,01k d ≤≤-. 所以(1.9.1)的任一解均是(1.9.2)的形式. ▋ 由定理1. 17的证明中的(1.9.3)式, 我们有下列结论:推论 当(,)1a m =时, 同余方程(1.9.1)有唯一解()1(mod )m x b m a ϕ-≡-⋅. (1.9.4)直观上看, 当模m 较大时, 由于计算()1m aϕ-不易, 所以利用(1.9.4)来求得同余方程的解一般不大实际.例1. 19 求下列同余方程的解.i) 350(mod 4)x +≡； ii) 58870(mod 47)x -≡；iii) 129831(mod1101)x ≡.解 i) 因(3,4)1=, 该方程有唯一解. 由(1.9.4)可得1(mod 4)x≡是所求方程的解. ii) 因(58,47)1=, 该方程有唯一解. 由于(47)158ϕ-不易计算, 我们不可利用(1.9.4)来求其解. 因5811(mod 47)≡, 8740(mod 47)≡, 故原方程等价于117(mod 47)x ≡-.由于(4,47)1=, 将方程两端乘4后得：4428(mod 47)x ≡-,即328(mod 47)x ≡,再由(16,47)1=, 方程两端乘16后得48448(mod 47)x ≡,即25(mod 47)x ≡.iii) 因(129,1101)3831=, 故原方程有三个解. 化简原方程得43277(mod367)x ≡. (1.9.5)因(43,367)1=, 故(1.9.5)有唯一解. 将其解形式地表为277(mod 367)43x ≡. 将分子、分母同加模数367得277367644(mod 367)43367410x +≡≡+. 再分子、分母约去2得322(mod 367)205x ≡. 将分子加上367-, 得45(mod 367)205x -≡, 约去5得9(mod 367)41x -≡. 分子、分母同乘9得81(mod 367)369x -≡. 将分子加367, 分母加367-后得286(mod 367)2x ≡. 约去2得143(mod 367)1x ≡. 即143(mod367)x ≡是同余方程(1.9.5)的解. 从而143(1101)x ≡是原方程的一个解.依据定理1.17, 原方程的三个解为143, 143367, 1433672(mod1101)x ≡++⨯,即143,510,877(mod1101)x ≡. ▋在例1.19的求解同余方程的过程中, 求解i)用的是公式法(1.9.3), 或称定理求解法.求解ii) 是用与模互素的数乘或除同余方程的两端, 使x 的系数逐渐减小, 以达到求解的目的, 此法可称为“数乘除法”.求解iii) 的方法其原理同求解i) 的方法, 只不过这里是采用一种简便的形式表达法, 均是利用同余式的性质求解, 其步骤是：先将同余方程(1.9.1)两边约去因数得同余方程.11110(mod )a x b m +≡, 11(,)1a m =. (1.9.1)**然后将(1.9.1)**的解形式地表为111(mod )b x m a ≡, 此处11a b 仅是一个分数形式的符号, 再将分子或分母减去或加上模的倍数及分子、分母乘以不为0的整数或约去一个与模数互素的数等若干次（这相当于对同余式的两边使用同余的性质）, 使分母的绝对值变小, 直至最后将“分数”变成整数, 即得(1.9.1)**的解, 由此便可求得(1.9.2)的解, 此法可称为“分式法”. 又例：例1. 20 求解同余方程15931125(mod1926)x ≡.解 因(1593,1926)91125=, 所以同余方程有九个解,将其简化得177125(mod 214)x ≡.因此125125214339113113556517717717759595295x +⨯≡≡≡≡≡≡⨯ 1371372143511313719236781818133712131+⨯≡≡≡≡≡≡≡⨯- 67147(mod 214)≡-≡.所以原方程的9个解为：147,361,575,789,1003,1217,1431,1645,1859(mod1926)x ≡. ▋ 对于给定的一个同余方程, 用何种方法求解简单方便？若模m 较小, 则用公式法直接简单. 若模m 较大, 则用“数乘除法 ” 、还是“分式法”求解简捷, 应视具体情况而定.练习1. 191. 下列同余方程有无解？有解时有几个解？1)19981999(mod 2000)x ≡; 2) 1111110(mod1011)x ≡; 3)8919180(mod198)x +≡; 4) 540(mod 45)ax +≡. 2. b 取何值时, 方程14(mod114)x b ≡1) 在0114x ≤<中有多于一个的解？ 2) 无解.3．利用本节提到的几种方法, 求解下列同余方程.1)3120(mod15)x +≡; 2) 49840(mod104)x -≡; 3) 52(mod 7)x ≡ ; 4) 711997(mod1999)x ≡;4. 知某一正整数的99次方除以97后得余数7, 而该正整数的100次方除97后得余数79, 问该正整数除以97后得到的余数是多少？§1. 10 一次同余方程组与孙子定理定义1. 13 有多个同余方程构成的组合称为同余方程组；称(1.10.1)式为一次同余方程组. 1112220(m o d )0(m o d ) 0(mod )n n n a x b m a x b m a x b m +≡⎧⎪+≡⎪⎨⎪⎪+≡⎩ (1.10.1) 其中12,,,n m m m 是正整数.如果存在整数0x 使00(mod )i i i a x b m +≡,(1,2,,)i n = ,则称0(mod )x x m ≡是(1.10.1)的一个解, 这里[]12,,,n m m m m = .本节的目的就是讨论(1.10.1)的解问题.若(1.10.1)有解, 则(1.10.1)中每个同余方程有解；反之, 若(1.10.1)中某个同余方程无解, 则(1.10.1)无解, 所以要研究(1.10.1)的解,可转化为研究下列同余方程的解.1122(mod )(mod ) (mod )n n x c m x c m x c m ≡⎧⎪≡⎪⎨⎪⎪≡⎩ . (1.10.2) 定理 1.18(中国剩余定理) 若12,,,n m m m 是n 个两两互素的正整数,则(1.10.2)关于模12n m m m m = 有唯一解112212(mod )n n n m m m x x c x c x c m m m m ≡+++ , (1.10.3) 其中i x 是 1(mod )i im x m m ≡的一个整数解()1,2,,i n = . 证 （存在性） 由12,,,n m m m 两两互素知(,)1i i m m m =.于是由定理1. 17知, 同余方 程1(mod )m x m i m i≡(1,2,,)i n = (1.10.4) 有唯一解. 设为(mod )x x m i i ≡. 即有1(mod )i i m x m m i ≡. 从而由|i j m m m （i j ≠）得1122121(mod )n n i ii i i n i m m m m x c x c x c x c c c m m m m m +++≡≡⋅≡ . 这说明112212(mod )n n nm m m x x c x c x c m m m m ≡+++ 是(1.10.2)的一个解.(唯一性) 若1(mod )x x m ≡及2(mod )x x m ≡是(1.10.2)的两个解, 则有1(mod )i i x c m ≡及2x ≡(mod )i i c m (1,2,,)i n = .于是12(mod )i x x m ≡,从而由i m (1,2,,)i n = 两两互素得121(mod )n x x m m ≡ , 亦即12(mod )x x m ≡. 这说明1(mod )x m 与2(mod )x m 是(1.10.2)的同一个解, 所以(1.10.2)只有一个解. ▋定理1.18的存在性的证明过程具体给出了在i m 两两互素的情况下同余方程组(1.10.2)的解法：首先分别求出每个方程1(mod )i im x m m ≡ (1,2,,)i n = 的一个整数解i x , 然后代入(1.10.3)式计算化简即得(1.10.2)的解.定理 1.18其实就是著名的孙子剩余定理, 国际上一般称之为中国剩余定理（Chinese Remainder Theorem ， 又简称为CTR 定理）.历史回顾：公元五世纪前后, 我国出现了一部著名的著作-《孙子兵法》, 书中提出了这样一个问题：“今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何?”该问题简称“物不知数”问题. 如设所要求的物数为x , 则x 就是下列同余方程组(1.10.5)的一个正整数解.2(mod 3)3(mod 5)2(mod 7)x x x ≡⎧⎪≡⎨⎪≡⎩. (1.10.5)对于“物不知数”问题的解法,《孙子算经》中记述：“凡三三数之剩一, 置七十；五五数之剩一, 置二十一；七七数之剩一, 则置十五；一百零六以上, 以一百零五减知即得.”明朝程大位在一五九三年出的一部著作《算经统宗》中关于“物不知数”问题有一首解法歌诀：“三人同行七十稀, 五树梅花二十一支,七子团圆整半月, 除百零五便得知.”也就是说 , 该问题的解答是70221315223323(mod105)x≡⨯+⨯+⨯≡≡.例1. 21 解同余方程组。