在维基百科:知识问答/存档/结构式讨论的话题

如題。用Excel的下拉複製、MOD函數，配合等差數列，逐項試誤，容易得知答案是29907。那麼，用人腦筆算要如何解題呢？謝謝解答！

如果能笔算的话是可行的。若设该最小值为x，则x是满足同余方程组$x\equiv {\begin{cases}1&\mod 2\\0&\mod 3\\2&\mod 5\\3&\mod 7\\9&\mod 11\\7&\mod 13\end{cases}}$的最小正数，然后根据中国剩余定理，各Mi及他们对应的数论倒数为(15015,1)(10010,2)(6006,1)(4290,6)(2730,6)(2310,3)，最后得到结果300177，模去30030得最小x为29907

P.S. 负数最大结果为-123，我怀疑是出题人按照这个数来出题的

但請問這些數論倒數又是如何筆算算出來的呢？

另外，您猜錯了，跟-123無關，絕對值會這麼小只是一個巧合，因為出題人就是我，是我自己出題給自己算的。

我只是把最小的5個奇質數隨便作直線排列而已，因為它們都是質數，所以

gcd(3 , 5)=gcd(3×5 , 7)=gcd(3×5×7 , 11)=gcd(3×5×7×11 , 13)=1

根據貝祖等式與扩展欧几里得算法，不論怎麼排列，一定都會有解。

好家伙。以3对应的Mi和其对应的数论倒数为例子，显然Mi就是2*5*7*11*13=10010，而数论倒数是10010*x=1 mod 3的最小正整数解，这等价于2*x=1 mod 3。枚举x=0,1,2或者是直接上exgcd(如你所提到的拓展欧几里得算法，这个可以手算)解2x-3y=1就能得到数论倒数为2了。

那如果我換一個題目「連續3個正整數分別是49、4、27的倍數，求此3數最小者的最小值」，請問這又要如何算呢？

数论倒数不一定非要是素数才能算，只要是互素的数就能算数论倒数（由Bezout定理）。这里的x分别模49，4，27的余数为0，3，25，这一组模的数论倒数为5，3和4，因此这样的数应该是模5292余31507 (=3*3*49*27+25*4*49*4)，最小正整数解就是5047。顺带一提，如果你所给出的倍数两两不是互素的情况下，假定解存在，将其写成线性同余方程组后可以把非互素的组合拆成等价的互素的组合，见中国剩余定理中“模不两两互质的同余式组”的部分

不過我倒是有別的方法：主要是利用「$k$為正整數，$a\equiv b{\pmod {m}}$，若且唯若$ka\equiv kb{\pmod {km}}$」這個性質，使得模數不同的同餘式變成模數相同，而可以直接兩式相減。其他同餘式性質可同時配合使用。

x分别模49，4，27的余数为0，3，25，則

x≡0 (mod 49) → 4x≡4*0 (mod 4*49) → 48x≡48*0 (mod 4*49)....甲

x≡3 (mod 4) → 49x≡49*3 (mod 4*49)....乙

乙減甲，得(49-48)x≡49*3-48*0≡147 (mod 196)

x≡147≡-49 (mod 196)

x≡-49 (mod 196) → 27x≡27*(-49) (mod 27*196)....丙

x≡25≡-2 (mod 27) → 196x≡196*(-2) (mod 27*196)....丁

丁減丙，得

(196-27)x≡196*(-2)-27*(-49)≡931 (mod 5292)

→169x≡931≡931+161*5292≡852943≡169*5047 (mod 5292)

→169與5292互質，故兩邊可同除以169，得x≡5047 (mod 5292)

我明白你什么意思。这个方法很基础也很常用，基本上想要解决这个问题的人都会像这样子两两的加入互素的模数的其它同余方程，以此来得到同余方程组的解。但这个问题恶心的地方正是（以第三组算式为例）将931 mod 5292写成931+161*5292 mod 5292，使得852943是169的倍数这一步，如果不能使用计算机/计算器的话想要找到161这个数将会耗费不少的计算量。所谓的数论倒数就是为了快速找到这样的数用的。

当然另一个方法是像第一组等式那样把x的系数凑成1。其实第二组等式也能这么做（比如运用exgcd——扩展欧几里得算法），可以得196*4+27*(-29)=1

計算量不會太龐大，一樣是擴展歐幾里得算法：

令931+5292a=169b

→931+5292a≡0(mod 169)

→86+53a≡0(mod 169)

令86+53a=169c

→86-169c≡0(mod 53)

→33-10c≡0(mod 53)

取c=-2有解

將c=-2代回86+53a=169c，得a=-8

但這樣會使得b為負數，所以取a=-8+169=161

161就是這麼得來的，並不是1,2,3,4,.....160,161逐個代入去試除是否169的倍數的。

您後半段的意思我懂。例如「整數x除以16、18、26分別餘4、10、22」要改成「整數x除以16、9、13分別餘4、1、9」。

1

这很简单，任何数的最小值基本上是0，1，2。