武如长每周一题

武如长

武如长每周一题
今有一数，5…2；7…0；11…1；求最小数？
提示：此题由孙子算法演变而来。中国余数定理，经秦九韶改进，变成了现在全世界通用的同余式。
吴文俊院士告诉我们：不崇洋，不泥古。我想：此题能否不用同余式求解，用另一种方法，或者用一种更优越的方法求解呢？
我甚至惊奇的发现：用中国余数定理可以对偶猜给于证明。请朋友们，拭目以待。

drc2000

[这个贴子最后由drc2000在 2010/11/27 02:11pm 第 2 次编辑]

下面引用由武如长在 2010/11/27 00:54pm 发表的内容：
武如长每周一题
今有一数，5…2；7…0；11…1；求最小数？
提示：此题由孙子算法演变而来。中国余数定理，经秦九韶改进，变成了现在全世界通用的同余式。
吴文俊院士告诉我们：不崇洋，不泥古。我想：此题能否不 ...

我只知道"有几个数,求其中最小的数"之类的说法.而未见给出一数,求最小数的说法.
"今有一数"…"求最小数？" 既然是一数,求最小数,当然就是它本身.
题目其余所云,似乎和题目无太多必然关系.

luyuanhong

[这个贴子最后由luyuanhong在 2010/11/27 03:48pm 第 1 次编辑]

下面引用由武如长在 2010/11/27 00:54pm 发表的内容：
武如长每周一题
今有一数，5…2；7…0；11…1；求最小数？
提示：此题由孙子算法演变而来。中国余数定理，经秦九韶改进，变成了现在全世界通用的同余式。
吴文俊院士告诉我们：不崇洋，不泥古。我想：此题能否不 ...

题  已知有一个正整数，除以5余2，除以7余0，除以11余1，求满足条件的最小数。

解  先找出满足“除以5余2”的最小正整数：2 ，然后逐次加 5 ，得到数列：
    2 ，7 ，12 ，17 ，22 ，27 ，32 ，…
在这个数列中，找出满足“除以7余0”的最小正整数：7 ，然后逐次加 5×7=35 ，
得到数列：
    7 ，42 ，77 ，112 ，147 ，182 ，217 ，252 ，287 ，322 ，357 ，…
在这个数列中，找出满足“除以11余1”的最小正整数：287 。
    287 就是满足条件的最小数。

drc2000

[这个贴子最后由drc2000在 2010/11/27 10:31pm 第 1 次编辑]

下面引用由luyuanhong在 2010/11/27 03:47pm 发表的内容：
题  已知有一个正整数，除以5余2，除以7余0，除以11余1，求满足条件的最小数。...

原来是这道题目!
另解如下:
[color=#FF0000]列不定方程
(以下字母均为整数)
设所求的数为x,则:
x= 5a+2......(1)
x= 7b+0......(2)
x=11c+1......(3)
第一次[color=#FF0000]消元
将(2)分别代入(1)(3)得
5a+2=7b.......(4)
11c+1=7b......(5)
第二次消元
解(4)得到:b=5k+1.......(6)
解(5)得到:b=11m+8......(7)
第三次消元
由(6)(7)得
5k+1=11m+8
既:5k=11m+7......(8)
解(8)得:
m=5n+3......(9)
[color=#FF0000]回代
将(9)代入(7)得
b=11(5n+3)+8=55n+41......(10)
再将(10)代入(2)得:
x=7(55n+41)=385n+287
通解:x=385n+287
当n=0时,最小的正整数为x=287
当n=1时,第2大的正整数为x=672
...

awei

[这个贴子最后由awei在 2010/11/27 11:17pm 第 2 次编辑]

[color=#0000FF]
11在M=5的反数为1（官科称为逆元）
7在M=5的反数为3。
2*（11*1）*（7*3）=462
5在M=11的反数为9，
7在M=11的反数为8。
1*（5*9）*（7*8）=2,520
462+2520+0=2,982
2,982mod(5*11*7）=287
方法很简单，可是和一次同余方程一样，
主要求逆元或者就是我讲的反数。
ab mod c =1,那么a和b在模c上互为反数，
a,b,c为正整数