拉格朗日定理
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
拉格朗日定理设
p
p
p为素数对于模
p
p
p意义下的整数系多项式
f
(
x
)
=
a
n
x
n
+
a
n
−
1
x
n
−
1
+
⋯
+
a
0
(
p
∤
a
n
)
f\left(x\right) = a_n x^n + a_{n - 1} x^{n - 1} + \cdots + a_0 \left( p \nmid a_n\right)
f(x)=anxn+an−1xn−1+⋯+a0(p∤an)
的同余方程
f
(
x
)
≡
0
(
m
o
d
p
)
f\left(x\right)\equiv 0 \left(\mathop{mod} p\right)
f(x)≡0(modp)在模
p
p
p意义下至少有
n
n
n个不同的解
x
i
≢
x
j
(
m
o
d
p
)
,
∀
i
≠
j
x_i \not\equiv x_j \left(\mathop{mod} p \right),\quad \forall i\neq j
xi≡xj(modp),∀i=j
证明
n
=
0
n = 0
n=0时显然成立
假设
d
e
g
f
<
n
\mathop{deg} f <n
degf<n时都成立
利用反证法假设存在一个满足题目条件的
f
f
f在模
p
p
p意义下有着至少
n
+
1
n+1
n+1个不同的解
x
0
,
x
1
,
⋯
,
x
n
x_0,x_1,\cdots, x_n
x0,x1,⋯,xn
设
f
(
x
)
−
f
(
x
0
)
=
(
x
−
x
0
)
g
(
x
)
f\left(x\right) - f\left(x_0\right) = \left(x - x_0\right) g\left(x\right)
f(x)−f(x0)=(x−x0)g(x)
则
g
(
x
)
g\left(x\right)
g(x)在模
p
p
p意义下时一个至多
n
−
1
n-1
n−1次多项式
对于
1
≤
i
≤
n
1\le i \le n
1≤i≤n,有
(
x
i
−
x
0
)
g
(
x
i
)
≡
f
(
x
i
)
−
f
(
x
0
)
≡
0
(
m
o
d
p
)
\left(x_i - x_0\right)g\left(x_i\right) \equiv f\left(x_i\right) - f\left(x_0\right) \equiv 0 \left(\mathop{mod} p\right)
(xi−x0)g(xi)≡f(xi)−f(x0)≡0(modp)
又因为
x
i
≢
x
j
(
m
o
d
p
)
,
∀
i
≠
j
x_i \not\equiv x_j \left(\mathop{mod} p \right),\quad \forall i\neq j
xi≡xj(modp),∀i=j
故
g
(
x
i
)
≡
0
(
m
o
d
p
)
g\left(x_i\right)\equiv 0\left(\mathop{mod} p\right)
g(xi)≡0(modp),从而
g
(
x
)
≡
0
(
m
o
d
p
)
g\left(x\right) \equiv 0 \left(\mathop{mod} p\right)
g(x)≡0(modp)至少有
n
n
n个根矛盾