三個線性同余方程組的計算機解決方案（C程序）

在我國的《孫子算經》中有著這樣一個的題目：有物不知其數，三個一數余二，五個一數余三，七個一數又余二，問該物總數幾何？在我國還流傳著這樣一個故事：相傳漢高祖劉邦問大將軍韓信統御兵士多少，韓信答說，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。劉邦茫然而不知其數。關于這類問題的解決方案，不同教育階段都有所不同。小學階段主要的解決方案可能就是尋找最大公倍數，聯立等式。而在高等教育階段，學習了《初等數論》的相關知識后，我們可以把這樣的問題抽象成多個線性同余方程組來解決。

首先介紹一下線性同余方程以及其求解方法。

若某未知數ax與常數b對常數n取模后結果相同，可以表示成ax≡b (mod n)的方程。此方程有解當且僅當 b 能夠被 a 與 n 的最大公約數整除(記作 gcd(a,n) | b)。這時，如果 x0 是方程的一個解，那么所有的解可以表示為:

{x0+kn/d|(k∈z)}

其中 d 是a 與 n 的最大公約數。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 個解。

通過這樣的方程，回歸到文章的最開始，對于《孫子算經》中的問題，可以聯立如下方程組：

那么，如何解決這個方程組？

依據中國余數定理，設有一數N，分別被兩兩互素的幾個數a1、a2、……an相除得余數R1、R2、……Rn，即：

N≡Ri(mod ai),(i=1、2、……n),

只需求出一組數K，使滿足

R1(mod ai),(i=1、2、……n),

即可求出適合該線性同余方程組的最小整數解（P是整數，M=a1×a2×……×an）。

看到這里相信大家對于線性同余方程組已經有了初步的理解。線性同余方程組本質上就是尋找多個關鍵數，這些關鍵數滿足的性質一定是：若除數集中元素共有n個，則關鍵數集中任意一個元素都可以被除數集中n-1個元素整除。對于這個問題，我們可以找到3個關鍵數，分別是70，21，15。觀察發現，70被3除余1而被5，7均可整除；21被5整除余1而被3，7均可整除；15被7除余1而被3，5均可整除。由此可得式：70a+21b+15c。這個式子滿足題目，但它并不是最小解，接下來可以減去105N（N=1,2,3……）。

當然這種解決方案屬于數理領域，對于信息化的今天，我們完全可以利用計算機來更加高效快捷的計算出這樣的線性同余方程組的答案。下文將通過C程序來提供任意三個線性同余方程組的計算工具。

還是觀察上文。一個數被3除余2，被5除余3，被7除余2。中國余數定理給出的解決方案計算龐雜且不易理解，丟番圖方程的解決方案可能無法求出給定范圍內的全部解。而使用計算機，通過遍歷的思想，我們可以很輕松的求出給定范圍內的全部解。

算法核心思路：設置if條件判斷，當且僅當i對3取模為2且i對5取模為3且i對7取模余2，輸出一次結果，否則不輸出。調用C程序中的if語句以及取模函數，可以得到核心代碼段：

if (i % 3 == 2 && i % 5 == 3 && i % 7 == 2)printf("該整數為%d\n", i);

核心問題已經解決了，接下來的問題就是：如何將該算法封裝成一個一般性的函數接口，每次調用只需要輸入上限值，除數與相對應的余數就可以直接得出結果，而不用每次都在函數體內進行修改？

這里我想到了利用數組來實現。定義兩個數組D和R，分別用于存放除數集與余數集，通過for循環嵌套scanf語句的方案，依次對除數與相應余數進行輸入，從而實現對函數的封裝。

整體代碼如下：

#include <stdio.h> #include <stdlib.h> int ChinaRemainderTheorem(int n) {int D[3]; //D數組用于存放除數int R[3]; //R數組用于存放余數for (int i = 0; i <= 2; i++) {D[i] = 0;R[i] = 0;} //初始化兩個數組printf("請依次輸入三個除數（結束請按回車）\n");for (int i = 0; i <= 2; i++) {scanf_s("%d", &D[i]);}printf("請依次輸入與三個除數對應的三個余數（結束請按回車）\n");for (int i = 0; i <= 2; i++) {scanf_s("%d", &R[i]);}for (int i = 0; i < n; i++)if (i % D[0] == R[0] && i % D[1] == R[1] && i % D[2] == R[2])printf("該整數為%d\n", i);printf("\n\n");return 0; } int main() {int a;int k;k = 1;while (k==1) {printf("請輸入上限。\n");scanf_s("%d", &a);ChinaRemainderTheorem(a);}return 0; }

運行成果展示：

總結

以上是生活随笔為你收集整理的三个线性同余方程组的计算机解决方案（C程序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。