有正整数N，它除以3余2，除以5余3，除以7余4。，除以11余5，除以13余6除以17余7除以19余8，求N的最小值

发布网友 发布时间：2022-05-01 21:01

我来回答

共2个回答

热心网友 时间：2023-10-03 03:32

看了好久的书才来做这个题，中国古代有一种算法叫做“大衍求一术”，简单点儿解释就是：求一个数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。

如果楼主不明白什么是辗转相除法，自己去找点资料看看吧，很容易理解的。
终于做完了，打了好久字的说，呵呵，打完收工！
另外,团IDC网上有许多产品团购,便宜有口碑追问柴你们idc的人怎么不看题呢,只知道复制复制在复制,

热心网友 时间：2023-10-03 03:33

跳过9的素数除数？成等差分布余数？
对于这种题，我有一个非常巧妙的算法，这道题得4383593，落叶海滩拿最小公倍数做，并算出“有正整数N，它除以3余2，除以5余3，除以7余4，除以11余5，除以13余6，除以17余7，除以19余8，除23余9，求N的最小值”的答案了。
我落叶海滩打死也不说那个公式，贴主，这种题中国没几个人会简便算法，你就别问了
楼上方法太麻烦追问可是这是好像是小学奥数,这种题要用中国剩余定理(我们还没学),答案没错,我编程也算了,电脑都算了几十秒
楼上根本不一样的题乱复制的,我*剩余定理的公式,符号都没见过,也不知道怎么算,我高一,估计很快要学这种东西了,公式说说吧,你弄得很诱人多给点分业务所韦.要在我高一的知识范围内.可以听懂