動機
整數 Euclid 算法與多項式長除法有相同的結構作用:把問題化為餘式較小的問題。前面的章節分別在整數及域上多項式使用這個機制。現在把真正需要的假設抽取出來,再問:若不能作餘式遞減的除法,哪些結論仍成立?
三類整環組織了答案。Euclid 整環有整數值大小控制的除法;主理想整環要求每個理想只有一個生成元;唯一分解整環要求非零元素可分解為不可約元,並有唯一性。定義記錄的是不同資訊。它們之間的蘊含需要證明,而熟悉的分解外觀,不是任意整環同時屬三類的證據。
本篇整環均為交換環,有 且無零因子。使用前篇的理想、單位及多項式次數。兩元素相差單位因子時稱為相伴;分解唯一性必須容許這個不確定性。
定義
定義 5.1.1
(三種整環條件)
Euclid 整環是具有函數 的整環,對任意 、,存在 使 ,且 或 。主理想整環(PID)要求每個理想均由一元素生成。唯一分解整環(UFD)要求每個非零非單位都有有限不可約分解,且除了因子次序及相伴外唯一。
此處 Euclid 定義只要求所示餘式條件,不要求大小乘法性,也不另加元素與其倍數之間的大小比較。整數用 ,域 上的 用次數。域本身亦包括在內:取常值大小零,除法餘式總為零。
定義 5.1.2
(不可約元與素元)
非零非單位 若滿足每次 都有一個因子為單位,稱為不可約元。若 總蘊含 或 ,則稱為素元。 的最大公因子 整除兩者,且每個公因子都整除 ;它只在相伴意義下確定。
整環的素元必不可約。若 ,素性給出例如 ,故 ,消去非零 得 ,所以 為單位。反方向須額外結構,會成為 PID 的重要結論。「尚未找到分解」既沒有證明不可約,也沒有證明素性。
概念視角結構
把整除讀成主理想的包含關係
在整環中, 當且僅當 ; 是單位當且僅當 ; 相伴當且僅當 。用這種語言,非零非單位 不可約,當且僅當 在真主理想中是極大的; 是素元,當且僅當 是素理想。分解問題於是變成關於主理想這個有序集合的問題。在 PID 中,這個集合包含所有理想,所以下面的鏈論證與極大性論證才可以使用。
定理 / 命題
定理 5.1.3
(Euclid 除法推出主理想與 Bézout)
每個 Euclid 整環都是 PID。在 PID 中, 由最大公因子 生成,並有 使 。特別地, 互質當且僅當 。
定理 5.1.4
(主理想推出唯一分解)
PID 的每條上升理想鏈均最終穩定。PID 的每個不可約元都是素元,每個非零非單位都有不可約分解。因此每個 PID 都是 UFD,且
證明思路或證明
證明
(最小大小給出生成元)
取 Euclid 整環的非零理想 。其非零元素大小構成非空非負整數集,故有最小值,取達到它的 。任意 除以 ,餘式 仍在 。若非零,其大小較小,矛盾。因此每個 都是 的倍數,。零理想是 ,故得 PID。
在 PID 寫 。由 , 整除兩者;由 ,它是兩者的 線性組合。每個公因子都整除此組合,故 是最大公因子。一輸入為零時論證仍成立;兩者均零時生成元為零,不把它稱作單位或不可約元。最大公因子是整除命題,Bézout 等式則是理想成員命題,PID 性質在此把兩者連起來。
理想鏈取代數值下降
證明
(上升鏈與分解的存在)
設 為 PID 的上升理想鏈。聯集 是理想:任取兩元素,它們同在某個足夠後的理想內,該處對加法與純量乘法封閉。寫 。由 ,它已在某個 ,於是 ,故相等,之後全部相同。無需 Euclid 大小函數,便證明上升鏈條件。
假設某非零非單位 沒有不可約分解。它不是不可約,故可寫 ,兩者均非單位。至少一因子也沒有不可約分解,否則把兩個有限分解相乘便能分解 ;把該因子命名為 。此時 :整除給包含;若相等,則 ,消去得 ,與非單位矛盾。重複會產生嚴格上升的主理想鏈,違反鏈條件。所以不可約分解必存在。
這使用可逐次選取的通常集合論背景。亦可用上升鏈條件,在反例生成的主理想中選極大者,分解後反駁極大性。障礙是無限嚴格增大的理想鏈,並非聲稱任意環元素都有遞減的數值大小。
為何不可約元變成素元
證明
(不可約元是素元,以及唯一性)
設 PID 中 不可約,且 、。 的生成元 整除 ,故不可約性迫使 為單位或與 相伴。後者會使 ,矛盾。故 為單位,縮放其 Bézout 等式得 。乘 後, 均被 整除,所以 ,證明素性。
對唯一性,比較非零元素的兩個不可約分解。一邊的第一因子整除另一邊乘積,反覆用素性便知它整除某不可約因子,兩者遂相伴。消去匹配的非零因子後重複,有限過程最後只餘單位。非空的非單位乘積不可能為單位,因為交換環中若乘積可逆,每因子均可逆。因此兩列長度相同,按重排及相伴逐一匹配。存在性與唯一性用不同論證,兩者對 UFD 結論均必要。
證明透視
兩種不同的停止理由
Euclid 除法因非負整數大小下降而停止;PID 分解因理想不能永遠嚴格上升而停止。從 Euclid 整環轉到 PID,即使沒有指定大小函數,仍保留第二機制。混淆兩者,便會暗中把 Euclid 假設加進所有 PID 的定理。
例題詳解
例題 5.1.5
(Gaussian 除法與最大公因子證書)
在 定義 。對非零 ,把 的兩實座標各四捨五入至最近整數,得 Gaussian 整數 。則 ,所以非零餘式滿足 ,故此範數為 Euclid 大小。
取 、,得 ,再有 。最大公因子是單位,回代給 。兩次餘式範數均下降,最後等式亦可獨立驗證互質。Euclid 證明現在保證整個環的理想主性與唯一分解,而非只處理這兩個輸入。
例題 5.1.6
(最大公因子未必生成二元素理想)
在 , 為真理想,因為每元素常數項均零。若它是 ,則 整除 。把它看成係數在整環 的 多項式, 的因子在 的次數為零,故 。它在該環整除 ,所以為單位或與 相伴;後者不可能整除 ,令 即見。因此每個公因子都是單位,任何候選理想生成元都為單位,與真理想矛盾。兩元素最大公因子為一,但環內不存在 。僅憑最大公因子存在,不能把 Bézout 結論推到任意整環。
例題 5.1.7
(不可約卻不素的元素)
令 。範數 具乘法性,單位恰為 。沒有範數二或三的元素: 時至少五, 時是平方。
二、三的範數為四、九,若分解為非單位,便須有範數二或三的因子,故兩者不可約。 的範數為六,非平凡分解須有範數二與三,也不可能,故亦不可約。然而
給出不等價不可約分解:兩邊因子範數不同,而相伴保持範數。二整除右邊乘積,卻不整除任一因子,因其整數係數一為奇數。因此離開 PID 論證後,不可約未必素;此整環不是 UFD、不是 PID,也不是 Euclid 整環。
使用層級而不反轉箭頭
要證具體環是 UFD,若較強條件容易建立,證它已足夠。Gaussian 座標取整證 Euclid 除法,餘下兩結論由結構定理完成。反之,要否定 PID,須展示非主理想,或用不具唯一分解等合法障礙。找不到方便大小函數,不是非 Euclid 的證明。
定理給蘊含而非定義等價,未分類全部 Euclid 函數,也未證每個 UFD 都主理想,不能把箭頭倒畫便宣稱反向。即使有求最大公因子的算法,仍須檢查它保證甚麼:算出公因子不自動把它表為線性組合,多項式例子已展示這個區分。
常見錯誤
常見錯誤
(三種條件都假定整環)
三種定義均假定整環。零因子環中,非零因子可能不能消去,而素性及唯一性證明都在關鍵位置使用消去。Euclid 大小亦非要求每個代數操作均使其下降,只要求選定的非零餘式較小。
反例模式
消去失效時,素元未必不可約
沒有整環假設,「素元必不可約」就不成立。在 中,剩餘類 是非零非單位,而且是素元:模六的剩餘類有明確的奇偶性, 為偶數當且僅當 或 為偶數。然而 給出 ,而 與 都不是單位,因為它們的倍數全是偶數。在「素元必不可約」的證明中,現在 以 、 成立,但消去 會得到 :這裏 ,而 。在整環中這一步消去合法,蘊含關係便成立。
常見錯誤
(不可約與素是不同條件)
不可約限制每次分解必有單位因子;素性控制乘積整除。在已證為 PID 的環中兩者相同,但在任意整環把它們當同義,便抹去二次整數反例。唯一性也須保留單位及相伴: 的單位為 ,只選正負號不能消除所有不確定性。
總結
最小餘式大小使每理想主性成立。主理想給 Bézout 等式及上升鏈穩定,再給不可約元的素性、分解存在與唯一。Gaussian 整數展示成功鏈;二變量多項式及二次整數則指出較弱資訊不足以推出哪些結論。
練習
快速檢查
(證明整環中同一對元素的任意兩個最大公因子相伴,並另處理 。)
解答 · 答案
兩個最大公因子彼此整除。若非零,寫 、,消去得 ,故相伴。對 ,最大公因子須被每個公因子整除,包括零,因此必為零;兩者就是同一零元素,無需消去。
快速檢查
(在 PID,證明非零非單位 為素元當且僅當 為非零素理想,並證不可約元生成極大理想。)
解答 · 答案
對非零非單位 , 蘊含 或 ,正是素元定義;非單位保證理想真。若 不可約且 ,則 ,故 單位或與 相伴,所以 或 ,證明極大性。單位的理想為全環,不符合真素理想條件。
快速檢查
(在 驗證 、,並用範數證三個所示因子不可約。)
解答 · 答案
直接相乘得 、。三因子範數為二、五、五,均為正有理質數。範數乘法性迫使每次分解有範數一的因子,即單位,故不可約;相伴仍可相差任一 Gaussian 單位。
快速檢查
(證明 的理想 為真理想且不主。)
解答 · 答案
映射 是環同態,因為關係 模二變成 。核恰為指定理想:若 偶,原元素為 ,末項偶。因此理想真。若為 ,則 整除二與 ,所以 同時整除四、六,只可能為一或二。二不可能,一會使 可逆、理想等於全環,矛盾。因此不主。