如何判断多项式是否不可约
令环RRR上的nnn次多项式为:a(x)=∑i=0naixi∈R[x]a(x) = \sum_{i=0}^n a_i x^i \in R[x]a(x)=i=0∑naixi∈R[x]复数域上复数域是的代数封闭的。因此,复数域上的多项式a(x)a(x)a(x)都可以写成:a(x)=∏i=1n(x−αi)a(x) = \prod_{i=1}^{n}(x-\alpha_i)a(x)=i=1∏n(x−
令环
R
R
R上的
n
n
n次多项式为:
a
(
x
)
=
∑
i
=
0
n
a
i
x
i
∈
R
[
x
]
a(x) = \sum_{i=0}^n a_i x^i \in R[x]
a(x)=i=0∑naixi∈R[x]
复数域上
复数域是的代数封闭的。因此,复数域上的多项式
a
(
x
)
a(x)
a(x)都可以写成:
a
(
x
)
=
∏
i
=
1
n
(
x
−
α
i
)
a(x) = \prod_{i=1}^{n}(x-\alpha_i)
a(x)=i=1∏n(x−αi)
因此,
a
(
x
)
a(x)
a(x)在复域上不可约
⟺
n
=
1
\iff n=1
⟺n=1
实数域上
如果
α
\alpha
α是一个非实的复根,那么共轭
α
ˉ
\bar \alpha
αˉ也是根,且它们的重数相同。从而实数域上的多项式
a
(
x
)
a(x)
a(x)都可以写成
a
(
x
)
=
∏
α
j
∈
R
(
x
−
α
j
)
∏
α
k
∉
R
(
x
−
α
k
)
(
x
−
α
ˉ
k
)
a(x) = \prod_{\alpha_j \in R}(x-\alpha_j) \prod_{\alpha_k \not \in R}(x-\alpha_k)(x-\bar\alpha_k)
a(x)=αj∈R∏(x−αj)αk∈R∏(x−αk)(x−αˉk)
那么:
- 如果 n = 1 n=1 n=1,那么它在实数域上不可约
- 如果 n = 2 n=2 n=2,它在实数域上不可约 ⟺ Δ = b 2 − 4 a c < 0 \iff \Delta = b^2-4ac < 0 ⟺Δ=b2−4ac<0
- 如果 n > 2 n>2 n>2,那么它在实数域上是可约的
如果 n n n是奇数,它包含至少一个实根。
有理数域上
有理数域是整数环的分式域,我们将有理数域上的多项式 f ( x ) f(x) f(x)乘以它系数的最小公倍数,得到整系数的有理数多项式 g ( x ) g(x) g(x),那么 f ( x ) f(x) f(x)在有理域上不可约 ⟺ g ( x ) \iff g(x) ⟺g(x)在有理域上不可约。
有理数域上的整系数多项式可约,那么它一定可以写作两个度数大于等于 1 1 1的整系数多项式因子的乘积。
如果整系数多项式 a ( x ) a(x) a(x)的系数互素,我们称它为本原多项式。
对于整系数多项式,
- 如果 n = 1 n=1 n=1,那么它在有理域上不可约
- 如果 n = 2 , 3 n=2,3 n=2,3,在有理域上不可约 ⟺ \iff ⟺有有理根,因此只需验证所有可能的有理根:令 i ∣ a 0 , j ∣ a n i | a_0,\,\, j | a_n i∣a0,j∣an分别是末项系数和首项系数的因子,所有可能的有理根为 i j , ∀ i , j \dfrac{i}{j},\,\, \forall i,j ji,∀i,j
- 注意,如果 n > 3 n>3 n>3,即使没有有理根也可以是可约的,比如 ( x 2 + 1 ) 2 (x^2+1)^2 (x2+1)2可约但没有有理根
- 形如 a x 2 + b x + c ax^2+bx+c ax2+bx+c的整系数多项式,如果 a b c abc abc是奇数,那么它在有理数域上不可约
Eisenstein判别法:若存在素数 p p p,使得对于整系数多项式 a ( x ) a(x) a(x)的系数有
- p ∤ a n p \nmid a_n p∤an
- p ∣ a i , ∀ i = 0 , 1 , ⋯ , n − 1 p \mid a_i,\,\, \forall i=0,1,\cdots,n-1 p∣ai,∀i=0,1,⋯,n−1
- p 2 ∤ a 0 p^2 \nmid a_0 p2∤a0
那么 a ( x ) a(x) a(x)在有理数域上不可约。
实际上,有些多项式无法使用Eisenstein判别法,因此可以做适当变形后再使用Eisenstein判别法。
Eisenstein间接判别法: a ( x ) a(x) a(x)在有理数域上不可约 ⟺ ∀ a ≠ 0 , b ∈ Q \iff \forall a \neq 0,b \in Q ⟺∀a=0,b∈Q, f ( a x + b ) f(ax+b) f(ax+b)在有理数域上不可约。
Eisenstein判别法的派生:若存在素数 p p p,使得对于整系数多项式 a ( x ) a(x) a(x)的系数有
- p ∤ a 0 p \nmid a_0 p∤a0
- p ∣ a i , ∀ i = 1 , ⋯ , n − 1 , n p \mid a_i,\,\, \forall i=1,\cdots,n-1,n p∣ai,∀i=1,⋯,n−1,n
- p 2 ∤ a n p^2 \nmid a_n p2∤an
那么 a ( x ) a(x) a(x)在有理数域上不可约。
Eisenstein判别法的推广:若存在素数 p p p,令 d = g c d ( a 0 , ⋯ , a n ) d=gcd(a_0,\cdots,a_n) d=gcd(a0,⋯,an),使得对于整系数多项式 a ( x ) a(x) a(x)的系数有
- p ∤ a j d , ∃ j = 0 , 1 , ⋯ , n p \nmid \dfrac{a_j}{d},\,\, \exists j=0,1,\cdots,n p∤daj,∃j=0,1,⋯,n
- p ∣ a i d , ∀ i ≠ j p \mid \dfrac{a_i}{d},\,\, \forall i \neq j p∣dai,∀i=j
- p 2 ∤ a 0 d p^2 \nmid \dfrac{a_0}{d} p2∤da0
- p 2 ∤ a n d p^2 \nmid \dfrac{a_n}{d} p2∤dan
- p ∤ a j d − b p \nmid \dfrac{a_j}{d} - b p∤daj−b,这里 b ∣ a 0 a n d 2 b \mid \dfrac{a_0a_n}{d^2} b∣d2a0an且 b ≠ a 0 a n d 2 b \neq \dfrac{a_0a_n}{d^2} b=d2a0an
那么 a ( x ) a(x) a(x)在有理数域上不可约。
上述的Eisenstein判别法都是判断多项式在有理数域上不可约的充分不必要条件。
模
p
p
p剩余类判别法:对于整系数多项式
a
(
x
)
a(x)
a(x),令
p
∤
a
n
p \nmid a_n
p∤an,那么记
a
ˉ
(
x
)
=
a
(
x
)
m
o
d
p
∈
Z
p
[
x
]
\bar a(x) = a(x) \mod p \in Z_p[x]
aˉ(x)=a(x)modp∈Zp[x]
若
a
ˉ
(
x
)
\bar a(x)
aˉ(x)在某个素域
Z
p
Z_p
Zp上不可约,那么
a
(
x
)
a(x)
a(x)在有理数域上不可约。若
a
(
x
)
a(x)
a(x)在有理数域上可约,那么模掉任意的素数
p
p
p都可约。
奇数次多项式判别法:若存在素数 p p p,使得对于 2 n + 1 2n+1 2n+1次的整系数多项式 a ( x ) a(x) a(x)的系数有
- p ∤ a 2 n + 1 p \nmid a_{2n+1} p∤a2n+1
- p ∣ a i , ∀ i = n + 1 , n + 2 , ⋯ , 2 n p \mid a_i,\,\, \forall i=n+1,n+2,\cdots,2n p∣ai,∀i=n+1,n+2,⋯,2n
- p 2 ∣ a i , ∀ i = 0 , 1 , ⋯ , n p^2 \mid a_i,\,\, \forall i=0,1,\cdots,n p2∣ai,∀i=0,1,⋯,n
- p 3 ∤ a 0 p^3 \nmid a_0 p3∤a0
那么 a ( x ) a(x) a(x)在有理数域上不可约。
有限域上
对于任意的 n ∈ Z + n \in Z^+ n∈Z+,在 G F ( q ) [ x ] GF(q)[x] GF(q)[x]中总存在 n n n次不可约多项式。
在
G
F
(
q
)
[
x
]
GF(q)[x]
GF(q)[x]中所有次数整除
n
n
n的首一不可约多项式的乘积为:
x
q
n
−
x
=
x
(
x
q
n
−
1
−
1
)
x^{q^n} - x = x(x^{q^n-1} - 1)
xqn−x=x(xqn−1−1)
若
a
(
x
)
≠
x
a(x) \neq x
a(x)=x是在
G
F
(
q
)
[
x
]
GF(q)[x]
GF(q)[x]中的
n
n
n次不可约多项式,若
α
\alpha
α是它在
G
F
(
q
)
GF(q)
GF(q)的代数闭包里的一个根,那么
- 有 n n n个不同的根,即一组共轭元 α , α q , α q 2 , ⋯ , α q n − 1 \alpha,\alpha^{q},\alpha^{q^2},\cdots,\alpha^{q^{n-1}} α,αq,αq2,⋯,αqn−1,且 n n n是满足 α q n = α \alpha^{q^{n}}=\alpha αqn=α的最小正整数
- 若 o r d ( α ) = l ord(\alpha)=l ord(α)=l,那么 l ∣ q n − 1 l \mid q^n-1 l∣qn−1,且 n n n是满足 q n ≡ 1 m o d l q^n \equiv 1 \mod l qn≡1modl的最小正整数
- 这组共轭根的乘法阶都是 l l l
分圆多项式
n ≥ 1 n\ge 1 n≥1, x n − 1 x^n-1 xn−1在域 K K K上的分裂域(splitting field)叫做 n n n次分圆域(cyclotomic field),记做 K ( n ) K^{(n)} K(n),而所有的根叫做 n n n次单位根(roots of unity),记做 E ( n ) E^{(n)} E(n)。
域 K K K的特征为 p p p,
- 若 ( n , p ) = 1 (n,p)=1 (n,p)=1或者 p = 0 p=0 p=0,那么 E ( n ) E^{(n)} E(n)是 K ( n ) K^{(n)} K(n)的一个 n n n阶循环乘法子群,其生成元 ξ \xi ξ叫做 n n n次本原单位根(primitive)
- 若 n = m p e , ( m , p ) = 1 n=mp^e,(m,p)=1 n=mpe,(m,p)=1,那么 K ( n ) = K ( m ) K^{(n)} = K^{(m)} K(n)=K(m)且 E ( n ) = E ( m ) E^{(n)} = E^{(m)} E(n)=E(m)
若
(
n
,
p
)
=
1
(n,p)=1
(n,p)=1或者
p
=
0
p=0
p=0,那么定义
K
K
K上的
n
n
n次分圆多项式:
Q
n
(
x
)
=
∏
1
≤
s
≤
n
,
(
s
,
n
)
=
1
(
x
−
ξ
s
)
Q_n(x) = \prod_{1\le s \le n,\,\,(s,n)=1} (x - \xi^s)
Qn(x)=1≤s≤n,(s,n)=1∏(x−ξs)
且
x
n
−
1
=
∏
d
∣
n
Q
d
(
x
)
x^n - 1 = \prod_{d \mid n} Q_d(x)
xn−1=d∣n∏Qd(x)
Q
n
(
x
)
Q_n(x)
Qn(x)的度数为
ϕ
(
n
)
\phi(n)
ϕ(n),系数都属于
K
K
K的素域。若
p
=
0
p=0
p=0(素域是有理数域),那么进一步的系数属于整数环。
分圆多项式是有理数域上不可约的整系数多项式,从而也是某一些素域 Z p Z_p Zp上(不是全部)的不可约多项式。
令
r
r
r是素数且
(
r
,
p
)
=
1
(r,p)=1
(r,p)=1或者
p
=
0
p=0
p=0,
k
k
k是自然数,那么
Q
r
k
(
x
)
=
x
r
k
−
1
Q
1
(
x
)
Q
r
(
x
)
⋯
Q
r
k
−
1
(
x
)
=
x
r
k
−
1
x
r
k
−
1
−
1
=
1
+
x
r
k
−
1
+
x
2
r
k
−
1
+
⋯
+
x
(
r
−
1
)
r
k
−
1
\begin{aligned} Q_{r^k}(x) &= \dfrac{x^{r^{k}}-1}{Q_1(x)Q_r(x) \cdots Q_{r^{k-1}}(x)}\\ &= \dfrac{x^{r^{k}}-1}{x^{r^{k-1}}-1}\\ &= 1 + x^{r^{k-1}} + x^{2r^{k-1}} + \cdots + x^{(r-1)r^{k-1}} \end{aligned}
Qrk(x)=Q1(x)Qr(x)⋯Qrk−1(x)xrk−1=xrk−1−1xrk−1=1+xrk−1+x2rk−1+⋯+x(r−1)rk−1
特别的,
- 取 k = 1 k=1 k=1,则 Q r ( x ) = 1 + x + x 2 + ⋯ + x r − 1 Q_r(x) = 1 + x + x^2 + \cdots + x^{r-1} Qr(x)=1+x+x2+⋯+xr−1
- 取 r = 2 r=2 r=2,则 Q 2 k ( x ) = 1 + x 2 k − 1 Q_{2^k}(x) = 1 + x^{2^{k-1}} Q2k(x)=1+x2k−1
因此,我们容易的构造了上述两类不可约多项式!
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)