另解一次同余方程

摘要本文主要闡述幾種一次同余方程的特殊解法:逐次減小模法、逐次減小系數法、形式分數法。

關鍵詞一次同余方程特殊解法逐次減小形式分數

中圖分類號:G633.6文獻標識碼:A

由王進明老師主編，人民教育出版社出版的《初等數論》，介紹了幾種比較傳統的一次同余方程的求解方法:同余變形法，“大衍求一術”，歐拉方法，組合數法等。在這里將介紹幾種其他的較為簡捷的解法。

由于一次同余方程

ax b (mod m)(1)

的解的存在性及其解的個數已經得到認識，我們這里只需要討論當(a， m) = 1時的情況就可以了。

1 逐次減小模法

定理1設(a， m) = 1，則存在整數y，使得a|b +ym，且

x(mod m)

是方程(1)的解。

解因為(a， m) = 1，則不定方程az- my=b一定有解，即存在整數y，使得a|b + ym。直接將x(mod m)代入方程(1)中驗算，有

axb+ymb (mod m)。

于是結論成立。

定理1說明，求方程(1)的解可以轉化為求方程

my-b (mod a)(2)

的解，這有兩個方便之處:一是將一個對于大模m的同余方程轉化為一個對于小模a的同余方程，因此有可能通過對模a的完全剩余系進行逐個驗證，以求出方程(2)和(1)的解;二是對于方程(2)繼續使用定理1，則又可繼續轉化成一個更小的模的同余方程，再依次遞推可得原一次同余方程的解。

例1解同余方程

19x3 (mod 53)

解先解同余方程

53y3 (mod 19)，

15y16 (mod 19)

解同余方程

19z 16 (mod 15)，

4z 14 (mod 15)

解同余方程

15r14 (mod 4)，

3r 2 (mod 4)

得到r 2 (mod 4)，因此方程4z 14 (mod 15)的解是

z = 11 (mod 15)。

方程15y 16 (mod 19)的解是

y= 15 (mod 19)。

最后得到方程19x 3 (mod 53)的解是

x= 42 (mod 53)。

2 逐次減小系數法

定理2設a > 0， (a， m) = 1，是m對模a的最小非負剩余且(， m) = 1，則同余方程

x -b(mod m) (3)

等價于同余方程(1)。

證明設x是(1)的解，則由m =a得到

(mod m)，

即x是同余方程(3)的解。但是由已知條件可知同余方程(1)與(3)都有且只有一個解。所以這兩個同余方程等價。

利用定理2，可以將同余方程(1)逐次轉化成未知數的系數更小一些的同余方程，從而易于求解。當然在轉化過程中為了保證每次的(， m) = 1，此方法最好在模m為質數時使用。

例2解同余方程22x 23 (mod 37)。

解由定理2，依次得到

22x23 (mod 37) 15x23€?14 (mod 37)

7x 14€?9 (mod 37)

2x9€?29 (mod 37)

x 29€?8 33 (mod 37)。

3 形式分數法

定義1:當(a， m) = 1時，若ab c (mod m)，則記b(mod，稱為形式分數。

根據定義和記號，由同余的性質:

若ab c (mod m)(a+mt2)bc+mt1(mod m)及

若(d，m)=1且a=da1，c=dc1，abc (mod m)a1bc1 (mod m)

則形式分數有下列性質

(1)(mod，

(2)若(d，m)=1，且，則(mod)

利用形式分數的性質把分母變成1，從而一次同余式的解。

例3解一次同余式17(mod25)

解:∵(17，25)=1，原同余方程有解，利用形式分數的性質，

同余方程解為 (下轉第126頁)(上接第112頁)

(mod25)

在代數學里的一個主要問題是求解代數方程，能夠在有解的條件下求解代數方程的所有解，并最好能給出解的公式。但是具有普遍意義的求解公式往往計算繁雜，對于具體的方程采用特殊的解法常常可以事半功倍。