sponsored links

一次同餘方程

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)。

分類: 教育
時間: 2021-09-20

相關文章