一次同余方程

　　1、ax+b≡c(modm)的一个解为ⅹ≡v(modm)，若t为另一个解，at+b≡c(modm)→av+b≡at+b(modm)→av≡at(modm)→v≡t(modm)→ⅹ≡v（modm）可以代表ax+b≡c(modm)的通解，因为其他解与其等价。
　　2.ax+t≡u(modb)→
　　aⅹ≡u-t(modb)，该同余方程解可通过ax≡±1(modb)求解，若ⅹ≡r(modb)为ax≡±1(modb)的解→ar≡±1(modb)，两边乘以(u-t)→ar(u-t)≡±(u-t)，因±aⅹ≡±(u-t)(modb)→
　　ar(u-t)≡±aⅹ(modb)→ⅹ≡±(u-t)r(modb)
　　aⅹ≡±1(modb)→(aⅹ±1)/b=y→aⅹ±1=by→ax=by±1(a与b互质)→ⅹ=(b/a)y±1/a→ⅹ/y=b/a±1/(ay)，b与a互质，写成连分数形式，分母以α、β、γ、……q、u、n，最后是形如u+1/n，去掉最后的1/n，连分数分母以α、β、γ……q、u，最后是q+1/u，为ⅹ/y的连分数。
　　3.aⅹ+t≡u(modm)，若a与m互质，解法如上所述，若a与m不互质，设δ为a、m的最大公约数，则δe=a，δf=m→δeⅹ+t≡u(modδf)→δeⅹ≡u-t(modδf)→(δeⅹ-(u-t))/δf=整数w→(δeⅹ-(u-t))/δ=fw→原同余方程也关与δ同余，a即δe可以被δ整除，那么u-t也被δ整除，u-t可表示为δk→δex≡δk(modδf)，与eⅹ≡k(modf)等价，e、f互质，与2中同余方程等同。
　　4.模为合数，ax≡b(modmn)→ax≡b(modm)或ax≡b(modn)成立，令δ为a、m最大公约数，(ax-b)/m=k→(ax-b)/(m/δ)=kδ，即ax≡b(modm/δ)，设x≡v(modm/δ)→(ⅹ-v)/(m/δ)=ⅹ1→ⅹ=(m/δ)*ⅹ1+v，该解是ax≡b(modm)的解，也是ax≡b(modmn)的解，但ⅹ1不知道，将ⅹ的表达式代入ax≡b(modmn)或ax≡b(modn)中，求解x1→(am/δ)*ⅹ1+av≡b(modmn)或(a/δ)*ⅹ1≡(b-av)/m(modn)。若n也可以写成两个因数相乘，继续上述方法。
　　例如，19ⅹ≡1(mod140)→19ⅹ≡1(mod2*70)→19ⅹ≡1(mod2)，ⅹ≡1(mod2)，v=1，m=2，a=19，δ=1，代入得(19*2/1)*ⅹ1+19*1≡1(mod140)→38ⅹ1+19≡1(mod140)→38ⅹ1≡-18(mod140)→19ⅹ1≡-9(mod70)→19ⅹ1≡-9(mod2*35)→19ⅹ1≡-9(mod2)，ⅹ1≡1(mod2)，a=19，b≡-9，v=1，m=2，δ=1，代入得38ⅹ2+19≡-9(mod70)→38ⅹ2≡-28(mod70)→19ⅹ2≡-14(mod35)→19ⅹ2≡-14(mod5*7)→19x2≡-14(mod7)，ⅹ2≡4(mod5)，a=19，b=-14，δ=1，m=5，v=4，代入得19*5ⅹ3+19*4≡-14(mod35)→
　　95x3≡-90(mod35)→
　　19x3≡-18(mod7)→x3≡2(mod7)→x3=2+7x4，因x=1+2x1，X1=1+2x2，x2=4+5x3→x2=4+10+35ⅹ4=14+35x4→x1=1+28+70x4→ⅹ=1+58+140ⅹ=59+140x4→
　　x-59=140x4→(ⅹ-59)/140=x4→
　　ⅹ≡59(mod140)。