匿名
匿名 發問於 科學數學 · 4 星期前

請問整數係數多元一次方程式有整數解條件?

假設A1*1+b1= a2*x2+bB2= a3*x3+b3=………………=an*Xn+Bn

其中A1,A2,A3,………...,An,B1,B2,B3,……..….,Bn都是正整數係數,

如果X1,X2,X3,.........Xn有正整數解的條件為何?

更新:

假設A1*X1+B1= A2*X2+B2= A3*X3+B3=………………=aAn*Xn+Bn

其中A1,A2,A3,………...,An,B1,B2,B3,……..….,Bn都是正整數係數,

如果X1,X2,X3,.........Xn有正整數解的條件為何?

1 個解答

評分
  • 4 星期前

    可參考:

    https://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E...

    如果 0 ≦ B_i < A_i, 這就是標準的: 以 A_i 除餘 B_i 的問題.

    如果有 B_i > A_i, 則必可化成 A_i * X_i +B_i = A_i * (X_i +k_i) + B'_i,

    滿足 0 ≦ B'_i < A_i. 如果標準的中國剩餘定理有解, 也就是存在正整數

    x_1,..., x_n 滿足修改後之方程式:

       A_1 * x_1 + B'_1 = A_2 * x_2 + B'_2 = ... = A_n * x_n + B'_n

    其中 x_i = X_i + k_i, 則因解之不唯一, 其實有無限多組解, 在某組解之後

    的所有解都滿足 X_i = x_i - k_i 是正整數.

    例如

       2x + 1 = 3y +2

    之最小正整數解是 (2,1), 但 (2+3p,1+2p), p 為非負整數,都是上式之解.

    因此,

        2x + 7 = 3y +2

    也有解, 最小解是 (5,5), 通解是 (5+3q,5+2q), q 是非負整數. 注意

        5 = 2+3(2) - 3, 5 = 1+2(2)

    第一式後面的 -3 是因 7 = 1+2(3), 或說 1 = 7-2(3). 

    因此, 不失一般性, 可以假設所有 B_i 都小於 A_i .

    如果 A_1, A_2, ..., A_n 兩兩互質, 也就是 i≠j 則 A_i 與 A_j 沒有大於 1

    的公約數, 那問題一定有解, 其解法就是 "孫子歌訣" 的一般化:

      三人同行七十稀, 五樹梅花廿一枝, 七子團圓正半月, 除百零五便得知.

    這是解 3x+2 = 5y+3 = 7z+2 的歌訣. 意思是:

      考慮:

         以 3 除時, 5*7 = 35 的倍數中除以 3 餘數是 1 的最小倍數是 70;

         以 5 除時, 3*7 = 21 的倍數中除以 5 餘數是 1 的最小倍數是 21;

         以 7 除時, 3*5 = 15 的倍數中除以 7 餘數是 1 的最小倍數是 15;

     則用問題中之餘數乘以上述各 "xxx的最小倍數":

         2 × 70 + 3 × 21 + 2 × 15 = 233

    這是 3x+2 = 5y+3 = 7z+2 的一個共同值, 得解 (77,46,33); 

    而把 233 除以 105 = 3×5×7 得餘數23, 對應 (x,y,z) = (7,4,3) 是原問題

    的最小解.

    上述解法的一般化, 也就是在諸 A_i 兩兩互質時的解法:

    (1) 首先計算 M_i = Π_(j≠i) A_j, 式中 Π 是連乖符號. 也就是說, M_i 是

          將除了 A_i 以外的所有 A_j 相乘的結果.

    (2) 考慮 M_i  的倍數中除以 A_i 餘數是 1 的 (可取其最小值, 但其實是

          否取最小值無妨, 都只是得原方程式一組解罷了.) 假設 t_i * M_i 即

          除以 A_i 的餘數就是 1.

    (3)  K = Σ_(i=1~n) B_i*t_i*M_i 即是 A_i*X_i+B_i = K 之一個共同值,

          而 X_i = (K-B_i)/A_i, i = 1,...,n 即是原方程式的一組解.

    (4) 把上述 K 除以 M = Π_(i=1~n) = A_i*M_i 取餘數, 得一組最小解.

    Wiki 上也考慮了諸 A_i 並不兩兩互質的情形, 其方法據其所引參考資

    料是來自 劉古勝等 2010 的一篇刊登在 高師理科學刊  的論文 "推廣

    的孫子定理". 具體方法是將原方程式化為 "等同" 的方程式:

        a_1 y_1 + b_1 = .... = a_m y_m + b_m

    其中諸 a_i 兩兩互質. "等同" 的意思是: 結果的 a_i*y_i+b_i 的共同值

    K 與原方程式的 A_i*X_i+B_i 的共同值一樣.

    考慮 K = N*x + R. 假設 N = P*Q, 其中 P, Q 互質. 則

         K = (NP)*Q + R = (NQ)*P + R.

    反之, 若 K = A*Q + R = B*P + R, 因 P, Q 互質故, 可得:

         P 可整除 A, Q 可整除 B, 因此 

         A*Q + R = B*P + R = N*(PQ) + R

    也就是說: K 與 R 除以 N 餘數相同, 可以分解為等價的兩個條件:

    K 與 R 除以 P, Q 其餘數皆相同. 

    因此, A_i*X_i+B_i 式可以對 A_i 做質因數分解, 而後以互質的因數

    將方程式改寫. 例如 A_1 = P_1*Q_1, P_1, Q_1 互質, 則

        A_1*X_1+B_1 = A_2*X_2+B_2 = .... = A_n*X_n+B_n = K

        P_1*Y_1+B_1 = Q_1*Z_1+B_1 = A_2*X_2+B_2 = ... = K

    結果之 K 相等同.

    在做了上述方程式之改寫後, 首先要檢查的是: 有無矛盾? 例如某一

    式分解並化簡(使 "餘數" 小於 "除數")後得 9x+3, 另一式分解後得

    9x+2, 顯然矛盾. 出現矛盾, 即代表原方程式無解.

    所以: 原問中的方程式有解的條件, 就是考慮原方程式中 A_i 不互

    質的配對, 看它們是否會有解 (有解就是方程式不矛盾, 無解就是

    有矛盾.) 如果兩兩之間都有解, 則整個方程式有解.

    因為原方程式有解與否的問題如上述可以縮減為看配對方程式

       A_i*X_i+B_i = A_j*X_j+B_j,  i≠j

    是否有解, 因此條件可以簡化成:

       若且唯若對所有 i ≠ j, (A_i,A_j) 可整除 B_i - B_j

        則原方程式有解.

    因為 A_i*X_i+B_i = A_j*X_j+B_j 有解的條件可以直接用 A_i 

    與 A_j 的 g.c.d. 能整除 B_i - B_j 來判定.

    • ...顯示所有留言
    • 老怪物
      Lv 7
      4 星期前舉報

      這也就 是說, 只要所有成對的方程式 Ai*Xi+Bi = Aj*Xj+Bj 
      都有解,  n 個式子構成的方程式就有解 (在回答中已說明
      這一點).  因此, 要看原 n 變元 (n 個式子) 的方程式是否
      有解, 可以 就 n(n-1)/2 個配對方程式 Ai*Xi+Bi = Aj*Xj+Bj
      一一檢查 (g.c.d. 判定法, 或分解為乘數互質的等同方程式
      有無矛盾檢測法皆可.)

    • Commenter avatar登入以回覆解答
還有問題嗎?立即提問即可得到解答。