离散数学/多项式

简介

在本节中，我们研究了在一些具有单位元的交换环上的多项式。有趣的是，研究一些具有单位元的交换环上的多项式，其行为与数字非常相似；相同的规则通常适用于两者。

定义

在一些具有单位元的交换环 R 上的多项式是一个形如

$\sum _{j=0}^{n}a_{j}x^{j};\forall a_{j}\in R,a_{n}\not =0$

其中 n ∈ N，而 x 是一个不定元（不是变量）。

术语

给定多项式中的第一个非零项，即上面的项 a_nxⁿ

• a_n 称为首项系数
  • 给定 7x³+2x+5，7 是首项系数
• 该多项式的次数为n
  • 7x³+2x+5，3 是次数
• 如果 a_n=1，则该多项式称为首一多项式
  • 7x³+2x+5 不是首一多项式，而 x⁴ 和 x⁵-3x+2 是首一多项式。

在上面，如果对于所有 i 都有 a_i=0，则该多项式为零多项式。

性质

令 R[x] 为所有次数多项式的集合。显然 R 在加法和乘法下是封闭的（虽然不是以一种直接的方式），因此我们有 R[x] 本身就是一个具有单位元的交换环。

现在假设 R 是一个域 F；我们这样做是为了能够对多项式定义一些有用的操作

除法算法

首先回忆一下数字的除法算法，即每个数字都可以分解为以下形式

n = qk+r

其中 q 是商，r 是余数，且 r<n。

现在，由于 F 是一个域，我们可以在 F 上的多项式 F[x] 中做类似的事情。

如果 f(x), g(x) ∈ F[x]，且 g(x) 非零

f(x) = q(x)g(x)+r(x)

同样，q(x) 称为商多项式，r(x) 称为余数多项式。此外，我们有 r(x) 的次数 ≤ f(x) 的次数

我们通过多项式长除法进行除法。为了简洁起见，我们省略了 x^k 项。以下是一个示例。我们将 x³+x+2 除以 x-1。首先写下

${\begin{matrix}&&&&&&&\\1&-1&|&1&0&1&2&\\\end{matrix}}$

注意，我们在任何不存在的多项式中放置一个 0。现在 x³/x = x²，所以我们在第二列中放置一个 1 以得到

${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\\end{matrix}}$

将 x² 乘以除数 x-1 以得到 x³-x²，也就是 (1 -1)，因此像下面这样写下它

${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\&&|&1&-1&&&\\\end{matrix}}$

现在减去 (1 0) 和 (1 -1)，删除第三个 1 以得到

${\begin{matrix}&&&&1&&&\\1&-1&|&1&0&1&2&\\&&|&1&-1&&&\\&&|&&1&1&&\\\end{matrix}}$

现在重复这个过程，但这次用x²除（因为我们已经减去并得到了 (1 1) - x² + x），并以相同的方式继续，得到

${\begin{matrix}&&&&1&1&2&\\1&-1&|&1&0&1&2&\\&&|&1&-1&&&\\&&|&&1&1&&\\&&|&&1&-1&&\\&&|&&&2&2&\\&&|&&&2&-2&\\&&|&&&&4&\\\end{matrix}}$

所以商是x²+x+2，余数是4。

欧几里得算法

现在我们有了多项式的除法算法，即欧几里得算法，因此可以很容易地找到两个多项式的最大公约数。

例子

让我们使用上面类似的例子：gcd(x³+x+2, x-1) 是什么？我们已经在上面证明了 x³+x+2=(x²+x+2)(x-1) + 4

按照欧几里得算法的正常方式进行

x³+x+2=(x²+x+2)(x-1) + 4

gcd(x³+x+2, x-1) = gcd(x-1,4)

任何单项式与整数的最大公约数显然是 1，所以 x³+x+2 与 x-1 互质。

第二个例子，考虑 gcd(x²-1,x²+2x+1)

x²+2x+1=(x²-1)*1+2x+2

x²-1=(2x+2)*x/2+ -(x+1)

2x+2=-(x+1)*(-2)+0

由于 -1 的因子没有区别，所以 gcd(x²-1,x²+2x+1) 是 -(x+1)

不可约多项式

我们已经看到 x³+x+2 与 x-1 互质；它们没有共同因子。那么，我们能确定“素数”多项式吗？确实可以 - 这取决于多项式所在的域。我们称这些多项式为不可约多项式，而不是素数。

例子

取 p(x)=x³ + x² + 2 在 Z₃ 上。现在如果它有根，我们就可以分解这个多项式 - 根据因式定理（它也适用于任何具有单位元的交换环上的多项式）p(k)=0 意味着 k 是一个根。所以，让我们看看以下情况：因为我们在 Z₃ 中，我们只需要检查三个值 p(0)=2 p(1)=1 p(2)=2 所以 p(x) 没有根 - 它不可约（“素数”）。

现在观察一个有趣的事实。取完全相同的多项式，但这次在 Z₂ 上。然后这个多项式等价于

x³+x²+0

因此它有根 p(0)=0，因此可约，但在 Z₂ 上

所以多项式的可约性取决于它所在的域。

证明不可约性

证明一个多项式不可约的一般方法是

• 观察它的次数
• 确定可能的分解
• 排除这些分解

实际上是一个用情况来证明。

例如，考虑在 Z₃ 中的多项式 q(x)=x⁴+x+2。为了证明它不可约，观察到 q(x) 可以以下列方式分解

1. 线性，不可约三次
2. 线性，线性，不可约二次
3. 线性，线性，线性，线性
4. 不可约二次，不可约二次

所以我们可以通过证明它没有线性因子来证明 1, 2, 3。4 有点难。让我们继续证明它没有线性因子：观察

q(0)=2

q(1)=1

q(2)=2

所以 q 没有线性因子。现在，我们需要证明 q 不是两个不可约二次多项式的乘积。

在 Z₃ 中，我们有以下二次多项式

{x²,x²+1,x²+x,x²+x+1,x²+x+2,x²+2,x²+2x,x²+2x+1,x²+2x+2}

我们可以通过观察很容易地识别出不可约二次多项式。然后我们得到

{x²+1, x²+x+2, x²+2x+2}

如果我们能证明这些多项式中没有一个能整除 q(x)=x⁴+x+2，我们就证明了 q(x) 不可约。

让我们先尝试 x²+1。

${\begin{matrix}&&&&&&1&0&2\\1&0&1&|&1&0&0&1&2\\&&&&1&0&1&&\\&&&&&&2&1&2\\&&&&&&2&0&2\\&&&&&&&1&0\\\end{matrix}}$

我们得到一个余数，所以 x²+1 不能整除 q。在除以其他多项式时，我们都会得到一个余数。（自己验证一下，作为练习）。

所以 q(x) 在 Z₃ 中不可约。

模运算和多项式

既然我们有了多项式除法和因式定理，以及多项式似乎模仿了整数的行为 - 我们能否合理地用多项式定义某种模运算？

确实可以。如果我们有一个域 Z_p[x]，我们希望找到用某个多项式 m(x) 除时所有的余数（记住，这些余数是多项式），我们可以通过多项式长除法来做到这一点。

如果 m(x) 不可约，那么如上所述的余数集合将构成一个域。