中国剩余定理

解如下同余方程组

x ≡ 1 (mod 3)

x ≡ 2 (mod 5)

x ≡ 3 (mod 7)

解题思路：一般来说解这样的同余方程组（Systems of Congruences）有两种解法，一种是利用同余的基本性质，另外一种是利用中国剩余定理（Chinese Remainder Theorem）。

方法一：同余的基本性质

从第一个方程组得知：x=1+3k（其中k是一个整数）代入第二个方程，即：1+3k≡ 2 (mod 5)。所以3k≡ 1 (mod 5)，3k≡ 6 (mod 5)，则k≡ 2 (mod 5)，即k=2+5m，m是一个整数。因此x=1+3k=7+15m，再将其代入第三个等式，得7+15m≡ 3(mod 7)，即15m≡ 3(mod 7)，即5m≡ 1(mod 7)，即5m≡ 1+14(mod 7)，得m≡ 3(mod 7)，可得m=3+7n。

所以：x=1+3k=1+3(2+5m)=7+15m=7+15(3+7n) =52+105n，n为整数，即该同余方程组的通解为：x=52+105n，n为整数。

方法二：中国剩余定理

中国剩余定理，又称孙子定理或中国余数定理，是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。该定理在中国古代也被称为“韩信点兵”、“求一术”（宋 沈括）、“鬼谷算”（宋 周密）、“隔墻算”（宋 周密）、“剪管术”（宋 杨辉）、“秦王暗点兵”、“物不知数”等。

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

x≡a1 (mod m1)

x≡a2 (mod m2)

...

x≡an (mod mn)

有解的判定条件，并用构造法给出了在有解情况下解的具体形式。中国剩余定理说明：假设整数m1, m2, ... , mn其中任两数互质，则对任意的整数：a1, a2, ... , an，该方程组有解，并且通解可以用如下方式构造得到。

该方程组的通解为：

x≡a1M1y1+a2M2y2+....+anMnyn+tM(modM)

其中t为整数，

M = m1m2 ... mn

Mk= M/mk = m1m2 ... mk-lmk+l ... mn

Mkyk≡1 (mod mk)

该同余方程组在[0，M-1]范围内有唯一解，如下：

x≡a1M1y1+a2M2y2+....+anMnyn(modM)

回到开始的同余方程组。

we have M=3·5·7=105, M1=105/3=35, M2=105/5=21, and M3=105/7=15.To determine y1, we solve 35y1≡1(mod3), or equivalently, 2y1≡1(mod3).This yields y1≡2(mod3). We find y2 by solving 21y2≡1(mod5); this immediately gives y2≡1(mod5). Finally, we find y3 by solving 15y3≡1(mod7). This gives y3≡1(mod7). Hence,

x≡1·35·2+2·21·1+3·l5·1=157≡52 (mod l05).

所以此同余方程组的通解为：

x=52+105t，t为整数

总结

对于解如下同余方程组：

x≡a1 (mod m1)

x≡a2 (mod m2)

...

x≡an (mod mn)

其本质是找到一个满足同余方程组最小的特解Xmin，然后其通解形式为：

X=LCM(m1,m2,m3...mn)×t+Xmin (其中t是整数)

比如对于开始的同余方程组：

x ≡ 1 (mod 3)

x ≡ 2 (mod 5)

x ≡ 3 (mod 7)

满足第一个方程的数分别为：

1，4，7，10，13，16，19，22，25，28，31，34，37，40，43，46，49，52，55...

满足第二个方程的数分别为：

2，7，12，17，22，27，32，37，42，47，52，57...

满足第三个方程的数分别为：

3，10，17，24，31，38，45，52，59...

由此可知，满足同余方程组的最小数为52，又有：

LCM(m1,m2,m3)=105

所以该同余方程组的通解为：

x=52+105t，t为整数

例题：

Problem

Let N=123456789101112...4344 be the 79-digit number that is formed by writing the integers from 1 to 44 in order, one after the other. What is the remainder when N is divided by 45?

解题思路：N是一个由1到44组成的79位的数字，要求求得N除以45的余数。45是一个合数，根据中国剩余定理只需要求模5和模9之后的余数即可。

最后一位数是4，所以模5的余数是4，而：

N≡1+2+3...+42+43+44≡0(mod9)

故可得到如下同余方程组：

x ≡ 4 (mod 5)

x ≡ 0 (mod 9)

根据中国剩余定理，其通解为：

x=9+45t，t为整数

故该问题的答案为9。