同余方程定义:
设
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)。