同余方程定义:
设 f ( x ) = a n x n + . . . + a 1 x + a 0 f(x)=a_nx^n+...+a_1x+a_0 f(x)=anxn+...+a1x+a0为整系数多项书,将含有变量 x x x的同余式 f ( x ) = 0 ( m o d m ) f(x)=0(mod~m) f(x)=0(mod m)称为模 m m m的同余式, n n n称为同余方程的次数。
若 a a a是同余方程的解,那么剩余类 k m + a km+a km+a均是同余方程的解。我们把整个剩余类看成同余方程的一个解。当 c 1 , c 2 c_1,c_2 c1,c2模 m m m不同于且是同余方程的解时,我们把它看作同余方程不同的解。
一次同余方程
形式: a x = b ( m o d m ) ax=b(mod~m) ax=b(mod m)
定理:一次同余方程 a x = b ( m o d m ) ax=b(mod~m) ax=b(mod m)有解的充要条件是 g c d ( a , m ) ∣ b gcd(a,m)|b gcd(a,m)∣b,且解数为 g c d ( a , m ) gcd(a,m) gcd(a,m)。
证:
必要性:设 g c d ( a , m ) = r gcd(a,m)=r gcd(a,m)=r。因为一次同余方程有解,所以 a x 0 = k m + b → b = a x 0 − k m ax_0=km+b\rightarrow b=ax_0-km ax0=km+b→b=ax0−km。 r ∣ a , r ∣ m → r ∣ b r|a,r|m\rightarrow r|b r∣a,r∣m→r∣b。
充分性:因为 g c d ( a , m ) ∣ b gcd(a,m)|b gcd(a,m)∣b,所以令 a ′ = a g c d ( a , m ) , b ′ = b g c d ( a , m ) , m ′ = m g c d ( a , m ) a'=\frac{a}{gcd(a,m)},b'=\frac{b}{gcd(a,m)},m'=\frac{m}{gcd(a,m)} a′=gcd(a,m)a,b′=gcd(a,m)b,m′=gcd(a,m)m。
考虑同余方程 a ′ x = 1 ( m o d m ′ ) a'x=1(mod~m') a′x=1(mod m′),因为 g c d ( a ′ , m ′ ) = 1 gcd(a',m')=1 gcd(a′,m′)=1,所以存在唯一逆元使得 a ′ x 0 = 1 ( m o d m ′ ) a'x_0=1(mod~m') a′x0=1(mod m′)。因此 a ′ x = b ′ ( m o d m ′ ) a'x=b'(mod~m') a′x=b′(mod m′)存在唯一解 x = x 0 b ′ ( m o d m ′ ) x=x_0b'(mod~m') x=x0b′(mod m′)。
设 a ′ x 0 b ′ = k 1 m ′ + b ′ a'x_0b'=k_1m'+b' a′x0b′=k1m′+b′左右同乘 r r r得到:
a x 0 b ′ − b = r a ′ x 0 b ′ − b = r ( k 1 m ′ + b ′ ) − b = r k 1 m ′ + r b ′ − b = k 1 m ax_0b'-b=ra'x_0b'-b=r(k_1m'+b')-b=rk_1m'+rb'-b=k_1m ax0b′−b=ra′x0b′−b=r(k1m′+b′)−b=rk1m′+rb′−b=k1m。
所以 m ∣ a x 0 b ′ − b m|ax_0b'-b m∣ax0b′−b,即 a ( x 0 b ′ ) = b ( m o d m ) a(x_0b')=b(mod~m) a(x0b′)=b(mod m),所以 x = x 0 b ′ ( m o d m ) x=x_0b'(mod~m) x=x0b′(mod m)是同余方程特解。
考虑同余方程解的个数:
x = x 0 b ′ ( m o d m ′ ) x=x_0b'(mod~m') x=x0b′(mod m′)可得 x = x 0 b ′ + k m ′ , k = 0 , − 1 , 1 , − 2 , 2 , . . . . x=x_0b'+km',k=0,-1,1,-2,2,.... x=x0b′+km′,k=0,−1,1,−2,2,....
模 m m m可写为 x = x 0 b ′ + k m ′ ( m o d m ) , k = 0 , 1 , 2... , g c d ( a , m ) − 1 x=x_0b'+km'(mod~m),k=0,1,2...,gcd(a,m)-1 x=x0b′+km′(mod m),k=0,1,2...,gcd(a,m)−1(因为若 k = g c d ( a , m ) + t , x = x 0 b ′ + g c d ( a , m ) m ′ + t m ′ = x 0 b ′ + m + t m ′ ( m o d m ) = x 0 b ′ + t m ′ ( m o d m ) , t < g c d ( a , m ) k=gcd(a,m)+t,x=x_0b'+gcd(a,m)m'+tm'=x_0b'+m+tm'(mod~m)=x_0b'+tm'(mod~m),t<gcd(a,m) k=gcd(a,m)+t,x=x0b′+gcd(a,m)m′+tm′=x0b′+m+tm′(mod m)=x0b′+tm′(mod m),t<gcd(a,m)),所以解数为 g c d ( a , m ) gcd(a,m) gcd(a,m)。