求解一次同余式

33x≡22(mod 77)
解:

1. 计算最大公因数(33,77)=11.因为(33,77)=11|22,所以原同余式有解.
2. 运用广义Euclid除法,求同余式:3x≡1(mod 7)的一个特解x1≡5(mod 7).
   所以3x≡2 (mod 7)的一个特解为x0≡2 * x1≡3(mod 7)
3. 写出原同余式的全部解
   x≡3+t*[77/(33,77)]≡3+7t(mod 77) ,t=0,1,2,...,10

广义Euclid除法,求同余式ax≡1(mod m) ,(a,m)=1,m为正整数
ax≡1(mod m) => ax=km+1 令x=s,k=-t则
sa+tm=(a,m)=1
利用广义Euclid除法求出s和t, 则x=s也就求出了.