有一类自然数,除以11余5,除以13余6,除以17余8,除以19余9.求其中最小的一个自然数....

有一类自然数,除以11余5,除以13余6,除以17余8,除以19余9.求其中最小的一个自然数....
有一类自然数,除以11余5,除以13余6,除以17余8,除以19余9.求其中最小的一个自然数
....

有一类自然数,除以11余5,除以13余6,除以17余8,除以19余9.求其中最小的一个自然数....
看了好久的书才来做这个题,中国古代有一种算法叫做“大衍求一术”,简单点儿解释就是：求一个数N,使得它被A1除余r1,被A2除余r2,被A3除余r3,被A4除余r4…….写成代数式就是：N=A1q1+r1=A2q2+r2=A3q3+r3=A4q4+r4=……那么“大衍求一术”要求我们首先找到一个数M1,它除以A1余1,而同时又被B1=A2×A3×A4整除；再找一个数M2,它除以A2余1,而同时又被B2=A1×A3×A4整除；再找一个数M3,它除以A3余1,而同时又被B3=A1×A2×A4整除；再找一个数M4,它除以A4余1,而同时又被B4=A1×A2×A3整除；如此等等.以上一系列“求一”的过程,相当于解一系列不定方程：BiX+AiY=1,（i=1,2,3,4……）.那么,当A1,A2,A3,A4互质的时候,利用辗转相除法,可以求得上面不定方程的解Xi（i=1,2,3,4……）.于是,若令Mi=BiXi,那么M1r1+M2r2+M3r3+M4r4就是一个被A1除余r1,被A2除余r2,被A3除余r3,被A4除余r4的数,它加上或减去A1×A2×A3×A4依然具有同样性质.
现在利用上述性质做这道题：
先求被11除余1且被13×17×19=4199整除的数.用辗转相除法：4199-11×381=8；11-8=3；8-3×2=2；3-2=1；所以1=3-2=3-（8-3×2）=3×3-8=（11-8）×3-8=11×3-8×4=11×3-（4199-11×381）×4=-4199×4+11×1527,所以求得M1=-4199×4=-16796.用同样方法,还可求得M2=-10659,M3=-16302,M4=-2431.题中r1=5,r2=6,r3=8,r4=9,从而M1r1+M2r2+M3r3+M4r4=-300229,注意到11×13×17×19=46189,所以被11除余5,被13除余6,被17除余8,被19除余9的最小自然数是-300229+46189×7=23094.
如果楼主不明白什么是辗转相除法,自己去找点资料看看吧,很容易理解的.
终于做完了,打了好久字的说,打完收工!

没时间给你算。

23094/11=2099…5
23094/13=1776…6
23094/17=1358…8
23094/19=1215…9

23094

回答这个问题的过程中，我也把以前逃课的东西学会了。具体到这个问题的
数字解法不写了，篇幅太长。要的话可以联系。
同余方程组的解法，初等数论的，有点忘记了，等着，我去找找
这个问题的名字叫 孙子定理
同余方程组：x=ai (mod mi)，i＝1到n，mi两两互质
孙子定理告诉我们，这个问题的解存在，具体的解法是这样的
令M=m1*m2*m3....

全部展开

回答这个问题的过程中，我也把以前逃课的东西学会了。具体到这个问题的
数字解法不写了，篇幅太长。要的话可以联系。
同余方程组的解法，初等数论的，有点忘记了，等着，我去找找
这个问题的名字叫 孙子定理
同余方程组：x=ai (mod mi)，i＝1到n，mi两两互质
孙子定理告诉我们，这个问题的解存在，具体的解法是这样的
令M=m1*m2*m3......*mn
令Mi=M/mi
x=M1*a1*c1+M2*a2*c2+....+Mn*an*cn (mod M)就是解（即最小的那个正整数）
这里关键是ci的求法
ci是这么求的
Mi*ci (mod mi)=1
这个方程即
Mi*ci=1+mi*k，k是整数
ci=(1+mi*k)/Mi
也就是说要找这样的k，使得按照上面式子算出来的ci是整数即可
到这一步之后，问题可以转化为
求Mi*ci+mi*k=1这个二元一次不定方程的整数解，条件是Mi,mi互质
这是有一般算法的
算法可以参考这个问题：http://zhidao.baidu.com/question/20641262.html?si=2

收起

100万以内所有符合条件的自然数有：
23094
69283
115472
161661
207850
254039
300228
346417
392606
438795
484984
531173
577362
623551
669740

全部展开

100万以内所有符合条件的自然数有：
23094
69283
115472
161661
207850
254039
300228
346417
392606
438795
484984
531173
577362
623551
669740
715929
762118
808307
854496
900685
946874
993063
其中最小是23094.
方法是用delphi编程，条件语句外面套一个循环语句，代码为：
●●●●●●●●●●●分割线●●●●●●●●●●●
var i:Integer;
begin
memo1.Lines.Clear;
for i:=1 to 1000000 do
if (i mod 11=5) and (i mod 13=6) and (i mod 17=8) and (i mod 19=9) then
memo1.Lines.Append(IntToStr(i));
end;
end.
●●●●●●●●●●分割线●●●●●●●●●●●●
把其中的数字1000000改为更大的数字，就可以得到更多符合条件的结果。已编译过 ，运行无误

收起

同余方程组的解法，初等数论
23094/11=2099…5
23094/13=1776…6
23094/17=1358…8
23094/19=1215…9
最小数字为23094

23094