中国剩余定理证明

中国剩余定理的讨论均在正整数范围内.

题目:
今有物不知其数.三三数余a,五五数余b,七七数余c.
问:物至少几许.
编辑注:a<3、b<5、c<7.

解题诗:
三人同行七十稀,五树梅花廿一枝,七子团圆正半月,除百零五便得知.
解意:
求出70a+21b+15c的值,然后减去105的倍数使小于105,所得的值就是题目的解.

证明:
设物有X.因本题是求物至少几许,所以X<3×5×7即X<105.
令:
3m+a=X..................①
5n+b=X..................②
7p+c=X..................③
①×70+②×21+③×15得:
(210m+105n+105p)+(70a+21b+15c)=106X
化成如下形式:
X=(70a+21b+15c)-105[X-(2m+n+p)]..................④
令:R=X-(2m+n+p)
由①、②、③分别得:m=X/3-a/3、n=X/5-b/5、p=X/7-c/7
有:
R=X-(2X/3-2a/3+X/5-b/5+X/7-c/7)
=X-106/105X+2a/3+b/4+c/7
=2a/3+b/5+c/7-X/105
因1≤a≤2、1≤b≤4、1≤c≤6、1≤X≤104
有R=2a/3+b/5+c/7-X/105<4/3+4/5+6/7=314/105<3
R=2a/3+b/5+c/7-X/105≥2/3+1/5+1/7-104/105=2/105>0
所以有R=1或R=2
把R=1代入④得:
X=70a+21b+15c-105
把R=2代入④得:
X=70a+21b+15c-210
所以70a+21b+15c-105或70a+21b+15c-210就是题目的解.
得证.