Question

求解同余方程37x=1(mod44)

Answer 1

由题意可得：

37x=44m+1

37（x-m）=7m+1

则7|37(x-m)-1

注意到;

37≡2 (mod 7)

则可得37×4≡8≡1 (mod 7)

那么去x-m=4

m=（37×4-1）/7=21

可得37x=44m+1的一个特解：

m=21，x=25

则该不定方程的通解为：

x=25+44t

m=21+3tt

则可得同余方程的解为：

x≡25 (mod  44)