一次同余式的解法yici tongyushi de jiefa

求一次同余式的解的方法.
❶辗转相除法.例如解同余式128x≡833 (mod1 001).显然其解集就是不定方程128x-1 001y=833解中x值的集合.因此，可以通过解上述不定方程求同余式的解.使用辗转相除法，(128,1 001)=1，且1001×(-39) +128×305=1 (参见“二元一次不定方程”).于是128×(305×833)-1 001×(39×833)=833，所以原不定方程的一个解为x₀＝305×833,y₀＝39×833.这样，原同余式的解为x≡305×833≡812 (modl 001).

❷逐步消去法.适用于模较小的同余式，其具体做法是不断变换其系数，使得有可能实行消去的步骤.例如，解同余式14x≡27(mod31).由14x≡27≡27+31≡58 (mod31)，消去公因数2可得7x≡29 (mod31).又有7x≡29≡60≡91 (mod31)，消去公因数7可得x≡13(mod31)，这就是所求的解.又例，解同余式6x≡15(mod33).就解集而言，它与2x≡5 (mod11)等价，因此我们只需解后者.我们有2x≡5≡16 (mod11)，故x≡8 (mod11).但是按照解的定义，必须求出对模33来说互不同余的解，这样的解恰有(6,33)=3个：8,8+11=19,8+11×2=30，所以原同余式的解为x≡8,19,30 (mod33) (参见“一次同余式”).

❸利用欧拉定理的解法.为了解同余式ax≡b(modm)，这里(a,m)=1，把同余式两边同乘以a^ψ(m)-1，得到a^ψ(m)x≡a^ψ(m)-1b (modm)，由欧拉定理知aψ^(m)≡1(modm) (参见“欧拉定理”)，有x≡a^ψ(m)-1b(modm)，这就是所求的解.例如，解同余式3x≡7 (mod10)，因为ψ(10)=4,(3,10)=1，所以x≡3ψ(10^)-1×7≡3³×7≡9 (mod10).