動機
方程 看來像一個沒有停止準則的搜尋。逐一測試較大的 有時很快找到解,但 的第一組正解已是 。完整理論須解釋解為何存在、搜尋為何能找到,以及一個解怎樣生成其餘所有解。
表達式 把問題連起來。乘法保持範數 ,共軛則把根號項變號。連分數給出無限多個逼近,其非零整數範數卻留在有界集合內。重複論證於是產生範數一的元素;離散性再給出最小正單位,把乘法化為完整分類。
全章設 是非平方整數,未必無平方因子。所用先備定理為上一章已證的收斂、誤差界及 Legendre 判準,不假設所有二次無理數連分數的週期定理。
定義
定義 7.4.1
(本章的二次整數、共軛與範數)
令 ,乘法取通常實數乘法。因 無理,表示唯一。定義 ,以及 。共軛保持加法與乘法,故 。
的單位是在 內有乘法逆元的元素。這恰好等價於範數為 或 :必要性由整數範數相乘得出,充分性由 得出。正單位指作為實數大於零。本章不宣稱此環一定是該二次域的全體代數整數環。
正 Pell 方程要求範數一,負 Pell 方程要求範數負一。正解是 。單位還包括 及共軛,所以全體單位的結構比正解列表包含更多資料。
定理
定理 7.4.2
(存在性與最小生成單位)
對每個非平方整數 , 都有 的解。在兩種範數的所有大於一單位中,有最小者 。每個正單位唯一寫成 ,其中 ;全體單位為 。
若 ,便不存在負一範數單位,範數一正解恰為 的係數,。若 ,範數一正解為 的係數,;負一範數正解為 的係數,。
概念視角幾何
單位是雙曲線上的一條軌道
設 是大於一的最小範數一單位。乘以 在係數對上的作用是
這是行列式為 的整數矩陣,其逆(乘以 )也是整數矩陣。它保持 及每條曲線 。定理是說: 在 分支上的整點恰好組成這個矩陣的一條軌道,即 的軌道。
定理 7.4.3
(每個正 Pell 解都來自漸近分數)
若 且 ,則 是 的既約漸近分數。因此逐個測試漸近分數的範數是否為一,必會終止,並先找到最小的大於一範數一單位;若測試兩種符號,先找到的便是 。這是終止與分類定理,並無宣稱多項式時間複雜度。
證明思路
有界範數產生真正單位
證明
(重複的範數與剩餘類對給出單位)
令 為 的漸近分數。分母趨向無限,誤差小於 。對充分大的 ,有 且 。所以非零整數
滿足
非零性來自無理性。可取值的整數有限,所以無限多對有相同範數 。再取無限子序列,使 模 也相同。正實數 無界,可選其中 。
把商的分母有理化,得
兩個分子都被 整除:模 ,第一個同餘 ,第二個同餘零。所以商在 內,範數一,且大於一。記為 ;其共軛是正數 ,因此
商已在 內,故這些係數是整數,存在性得證。僅有範數重複還不保證商整係數;剩餘類對也重複,才補上這一步。
先用離散性,再用冪作除法
證明
(先求最小單位,再用冪作除法)
對單位 ,其共軛絕對值為 ,所以整數係數滿足 、。可行整數對有限。存在性已給一個大於一單位,在不超過它的有限個單位中取最小者 。
給定正單位 ,選唯一整數 使 。因 的冪向上無界、向下趨零,這個整數存在。於是 是位於 的正單位,由最小性只能是一。因此 。不同冪有不同實數值;每個負單位則是某正單位的負值。
由範數乘法性,,立即得到所述奇偶區分。若兩種範數的單位 ,代入 的係數式便知 ;零與一之間的單位則必有一個負係數:範數為一時 為負,範數為負一時 為負,例如 。所以定理指定的冪範圍恰好列盡正解。
證明透視
兩個作用不同的有限性論證
存在性利用範數與剩餘類只有有限選擇,製造整係數的商。分類則利用有界實數區間內只有有限整數係數對,取得最小生成單位。兩者都不能只由幾個已見解推出。一旦最小者存在,除以它的冪便排除相鄰冪之間還藏著其他單位。
連分數為何先找到最小解
證明
(Legendre 判準與解的次序)
正解的 若有公因數,其平方須整除一,所以分數既約。有理化給出
範數一時 ;範數負一時,由 (因 )得 ,所以分母的括號仍大於二。Legendre 判準遂證明它是漸近分數。
在兩種符號的正解中, 增大會使 嚴格增大。若 ,則 ,連最小可能的 也大於最大可能的 。固定正 時兩種範數不能同時出現,因為非負整數平方不能相差二。漸近分數的分母除最初可能同為一外嚴格遞增,而這最初兩個也不能同為 Pell 解。因此第一個測到的解,正是指定範數類中的最小單位;存在性保證範數一測試最終成功。
平方根尾項的精確有限狀態計算
尾項可用整數運算產生,無須四捨五入的平方根。設 。若 ,定義
把 取倒數並有理化,便得下一尾項。歸納保持 整數、、 及 。由 得整除性保持。正的分數部分給出 ,而 及 給出下界。因此 是正整數且至多為 。取整公式精確,因把 改為 只把整數分子減少嚴格介於零、一之間的量,除以正整數後不會越過下一整數。
整數狀態 只有有限個,下一狀態又由當前狀態唯一決定,所以某狀態重現後,往後全部重複。這證明本類平方根展開最終週期性;並未證明所有最終週期實連分數的完整刻畫,也沒有用週期長度奇偶規則判定負方程。
例題
例題 7.4.4
(平方根二與負範數生成單位)
的首個漸近分數 範數為 ,已是兩符號中的第一個正解,故 。其平方 是最小的大於一範數一單位。 的全部正解為 的係數,,首三組是 。負範數正解來自 的奇數次冪,首幾組為 。指數奇偶性來自範數同態。
例題 7.4.5
(有局部障礙的負方程)
的首幾個漸近分數是 ,範數為 ,故 範數一。另一方面,負方程 模三要求 ,但平方剩餘只有零與一,故不可能。全部範數一正解是 的正整數次冪,首幾組為 。局部不可能性與整體單位分類互相吻合。
例題 7.4.6
(十三的首個正範數解為何很大)
精確尾項計算給出 。到六之前的漸近分數是 ,範數為 。所以兩符號中最小的大於一單位是 ,最小範數一單位是其平方:
驗算為 。過早停止的直接搜尋會漏掉它。這裏由逼近判準及排序證明保證最小性;單獨展示等式只能保證它是一組解。
反例模式
漸近分數未必解任何一個 Pell 方程
的漸近分數 範數是 。每個正 Pell 解都是漸近分數,但逆命題不成立;誤差判準只確定解出現的位置,仍須測試整數範數。此外不能把非平方參數定理用於平方 :此時 迫使範數一方程的 。
常見錯誤
常見錯誤
(環是 ,小於一的單位有負係數)
本章的環明確是 ;改用完整代數整數環,單位生成元可能改變。對 ,較大的環含有 ,其範數為 ,而 才是本章所得的生成元。正實數單位若小於一,也可以有負係數, 就是例子。
常見錯誤
(最小單位不一定範數為一)
兩種範數共用的最小生成單位,未必解正 Pell 方程;範數為負一時須取平方。例如 時, 的範數是 ,最小的範數一單位是 。
常見錯誤
(單有相同範數不能給出整係數商)
範數重複不足以保證整係數商,還須匹配剩餘類。對 ,漸近分數 與 的範數都是 ,因為 。它們模 的剩餘類對分別是 與 ,而事實上
同理,有限部分商串也不能單靠外觀證明週期,須有精確重複狀態;搜尋已證會終止,不代表對很大的 已證計算很快。
小結
小逼近誤差使漸近分數的整數範數有界。範數與剩餘類同時重複,便產生正的範數一單位;離散性再給出最小生成元及全部冪分類。Legendre 判準把每個正 Pell 解放進漸近分數序列,令精確搜尋同時具備終止性與完備性。
練習
快速檢查
(對 ,求兩種範數中最小的大於一單位,以及範數一的最小者,並寫出兩個 Pell 方程的全部正解。)
精確計算第一尾項 。
解答 · 答案
第一尾項為 ,整數部分四,分數部分與原輸入相同,故 。首個 範數負一,所以 ,。範數一正解為 的係數,;負一正解為 的係數,。單位定理排除其他解。
快速檢查
(若 是最小的大於一範數一單位,推導生成全部範數一正解的整數遞推。對 從 計算下一步。)
把 乘以 ,再比較係數。
解答 · 答案
把 乘以 ,得到 、,起始為 。冪分類證明列盡。 的下一組為 。
快速檢查
(證明 的全體整數解由 ,,表示。交代負 及額外負號怎樣影響 。)
由分類 及範數的奇偶出發。
解答 · 答案
若 ,取 ;否則取 。由奇偶計算,全體範數一單位恰為 。 時係數皆正; 時共軛給出 ,其中 。乘負一則同時反轉兩係數符號。 給 ,所以全部整數符號情形都已交代,沒有添入不存在的 正解。
快速檢查
(直接證明 不可能,再用 找最小範數一正單位。以精確尾項證明此重複展開。)
對負方程在模 下考慮。
解答 · 答案
模三要求 ,不可能。 第一尾項是 ,整數部分二;下一個是 ,整數部分四;其後回到第一尾項。首兩個漸近分數為範數負二的 ,及範數一的 。所以最小大於一單位是 ,範數一正解為其正整數次冪;局部障礙也獨立排除了負範數單位。