33x≡22(mod 77)
解:

1. 計算最大公因數(shù)(33,77)=11.因為(33,77)=11|22,所以原同余式有解.
2. 運(yùn)用廣義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為正整數(shù)
ax≡1(mod m) => ax=km+1 令x=s,k=-t則
sa+tm=(a,m)=1
利用廣義Euclid除法求出s和t, 則x=s也就求出了.