離散數學/多項式

簡介

在本節中，我們研究了在一些具有單位元的交換環上的多項式。有趣的是，研究一些具有單位元的交換環上的多項式，其行為與數字非常相似；相同的規則通常適用於兩者。

定義

在一些具有單位元的交換環 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) 不可約，那麼如上所述的餘數集合將構成一個域。