拉格朗日定理
拉格朗日定理：设
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个根，矛盾