動機
哪些正整數可以寫成 x 2 + y 2 x^2+y^2 x 2 + y 2 ,其中 x , y ∈ Z x,y\in\mathbb Z x , y ∈ Z ?例如 5 = 1 2 + 2 2 5=1^2+2^2 5 = 1 2 + 2 2 ,18 = 3 2 + 3 2 18=3^2+3^2 18 = 3 2 + 3 2 ,但 3 3 3 不能這樣表示。我們會看到質因數分解給出完整答案;關鍵是解釋不同同餘類中的質數為何有不同作用。座標可以為零或負數,交換座標或改變符號都不改變平方和。
模四餘三的質數造成的障礙
平方數模 4 4 4 只能餘 0 0 0 或 1 1 1 ,所以模 4 4 4 餘 3 3 3 的數不是兩個平方數之和。要得到完整的因數判別法,需要更強的結論。
設質數 p ≡ 3 ( m o d 4 ) p\equiv3\pmod4 p ≡ 3 ( mod 4 ) 。若 p ∣ x 2 + y 2 p\mid x^2+y^2 p ∣ x 2 + y 2 ,則 p ∣ x p\mid x p ∣ x 且 p ∣ y p\mid y p ∣ y 。
證明
(費馬(Fermat)小定理排除 − 1 -1 − 1 的平方根)
若 p ∤ y p\nmid y p ∤ y ,可在模 p p p 下除以 y 2 y^2 y 2 ,得到 t 2 ≡ − 1 ( m o d p ) t^2\equiv-1\pmod p t 2 ≡ − 1 ( mod p ) 。由費馬小定理,1 ≡ t p − 1 ≡ ( − 1 ) ( p − 1 ) / 2 ≡ − 1 ( m o d p ) 1\equiv t^{p-1}\equiv(-1)^{(p-1)/2}\equiv-1\pmod p 1 ≡ t p − 1 ≡ ( − 1 ) ( p − 1 ) /2 ≡ − 1 ( mod p ) ,與奇質數 p p p 矛盾。因此 p ∣ y p\mid y p ∣ y ,再由原同餘式得到 p ∣ x p\mid x p ∣ x 。
於是非零平方和若被這樣的 p p p 整除,其兩個座標都能除以 p p p ,平方和便能除以 p 2 p^2 p 2 。反覆應用可知 v p ( x 2 + y 2 ) v_p(x^2+y^2) v p ( x 2 + y 2 ) 是偶數。這比檢查模 4 4 4 強:21 ≡ 1 ( m o d 4 ) 21\equiv1\pmod4 21 ≡ 1 ( mod 4 ) ,但 3 3 3 與 7 7 7 的指數均為奇數,仍不能表示。
反例模式
整除引理需要模四餘三 命題:若質數 p p p 整除 x 2 + y 2 x^2+y^2 x 2 + y 2 ,則 p p p 同時整除 x x x 與 y y y 。取 p = 5 p=5 p = 5 便不成立:x = 1 x=1 x = 1 、y = 2 y=2 y = 2 時 x 2 + y 2 = 5 x^2+y^2=5 x 2 + y 2 = 5 被 5 5 5 整除,但 5 ∤ 1 5\nmid1 5 ∤ 1 且 5 ∤ 2 5\nmid2 5 ∤ 2 。p = 2 p=2 p = 2 亦不成立,因為 2 ∣ 1 2 + 1 2 2\mid1^2+1^2 2 ∣ 1 2 + 1 2 。兩種情況下 − 1 -1 − 1 都是模 p p p 的平方數(2 2 ≡ − 1 ( m o d 5 ) 2^2\equiv-1\pmod5 2 2 ≡ − 1 ( mod 5 ) ,1 2 ≡ − 1 ( m o d 2 ) 1^2\equiv-1\pmod2 1 2 ≡ − 1 ( mod 2 ) ),而這正是證明在 p ≡ 3 ( m o d 4 ) p\equiv3\pmod4 p ≡ 3 ( mod 4 ) 時排除的情形。修正後的命題保留這個假設;對其他質數,p p p 在 x 2 + y 2 x^2+y^2 x 2 + y 2 中的指數可以是奇數,例如 5 = 1 2 + 2 2 5=1^2+2^2 5 = 1 2 + 2 2 。
定義
為甚麼模四餘一的質數可以表示
先證明每個質數 p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) 本身是兩個平方數之和。引入高斯(Gauss)整數與範數:
Z [ i ] = { a + b i : a , b ∈ Z } , N ( a + b i ) = a 2 + b 2 . \mathbb Z[i]=\{a+bi:a,b\in\mathbb Z\},\qquad N(a+bi)=a^2+b^2. Z [ i ] = { a + bi : a , b ∈ Z } , N ( a + bi ) = a 2 + b 2 . 因為 N ( z ) = z z ‾ N(z)=z\overline z N ( z ) = z z ,所以 N ( z w ) = N ( z ) N ( w ) N(zw)=N(z)N(w) N ( z w ) = N ( z ) N ( w ) 。範數為 1 1 1 的元素恰是單位 1 , − 1 , i , − i 1,-1,i,-i 1 , − 1 , i , − i 。
每個質數 p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) 都是兩個整數平方數之和。
對 α , β ∈ Z [ i ] \alpha,\beta\in\mathbb Z[i] α , β ∈ Z [ i ] ,若 β ≠ 0 \beta\ne0 β = 0 ,將 α / β \alpha/\beta α / β 的實部和虛部分別取最近整數,得到 q ∈ Z [ i ] q\in\mathbb Z[i] q ∈ Z [ i ] 。令 r = α − q β r=\alpha-q\beta r = α − q β ,則 N ( r ) ≤ N ( β ) / 2 < N ( β ) N(r)\le N(\beta)/2<N(\beta) N ( r ) ≤ N ( β ) /2 < N ( β ) 。因此高斯整數也有歐幾里得(Euclid)除法;反覆除法給出最大公因子與貝祖(Bézout)等式。特別地,不可約高斯整數是質元素:若它整除 z w zw z w 而不整除 z z z ,它與 z z z 的最大公因子是單位,再用貝祖等式可知它整除 w w w 。
對奇質數 p p p ,把非零餘數與其逆元配對,得到威爾遜同餘 ( p − 1 ) ! ≡ − 1 ( m o d p ) (p-1)!\equiv-1\pmod p ( p − 1 )! ≡ − 1 ( mod p ) :只有 1 1 1 與 − 1 -1 − 1 是自身的逆元。若 p = 4 k + 1 p=4k+1 p = 4 k + 1 ,令 t = ( 2 k ) ! t=(2k)! t = ( 2 k )! ,將 j j j 與 p − j p-j p − j 配對,並注意 2 k 2k 2 k 是偶數,便有 ( p − 1 ) ! ≡ t 2 ( m o d p ) (p-1)!\equiv t^2\pmod p ( p − 1 )! ≡ t 2 ( mod p ) 。所以 t 2 ≡ − 1 ( m o d p ) t^2\equiv-1\pmod p t 2 ≡ − 1 ( mod p ) 。
現在 p p p 在 Z [ i ] \mathbb Z[i] Z [ i ] 中整除 ( t + i ) ( t − i ) (t+i)(t-i) ( t + i ) ( t − i ) ,卻不整除任何一個因子:若普通整數 p p p 整除其中一個高斯整數,其兩個係數都必須被 p p p 整除,但虛部係數是 1 1 1 或 − 1 -1 − 1 。故 p p p 不是高斯質元素,依前面關於歐幾里得除法的論證(不可約元必為質元)也不是不可約元素。將它寫成 p = α β p=\alpha\beta p = α β ,其中兩因子均非單位。由 N ( α ) N ( β ) = p 2 N(\alpha)N(\beta)=p^2 N ( α ) N ( β ) = p 2 ,兩範數都是大於 1 1 1 的整數,只能都等於 p p p 。寫 α = a + b i \alpha=a+bi α = a + bi 即得 p = a 2 + b 2 p=a^2+b^2 p = a 2 + b 2 。另有 2 = 1 2 + 1 2 2=1^2+1^2 2 = 1 2 + 1 2 。
證明透視
何處用到 $p$ 模四的餘數 證明由三個互相獨立的步驟組成,只有第一步用到 p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) 。
− 1 -1 − 1 的平方根。 寫 ( p − 1 ) ! = ∏ j = 1 ( p − 1 ) / 2 j ( p − j ) ≡ ( − 1 ) ( p − 1 ) / 2 ( ( ( p − 1 ) / 2 ) ! ) 2 ( m o d p ) (p-1)!=\prod\limits_{j=1}^{(p-1)/2}j(p-j)\equiv(-1)^{(p-1)/2}\bigl(((p-1)/2)!\bigr)^2\pmod p ( p − 1 )! = j = 1 ∏ ( p − 1 ) /2 j ( p − j ) ≡ ( − 1 ) ( p − 1 ) /2 ( (( p − 1 ) /2 )! ) 2 ( mod p ) 。當 p = 4 k + 1 p=4k+1 p = 4 k + 1 時符號為 ( − 1 ) 2 k = 1 (-1)^{2k}=1 ( − 1 ) 2 k = 1 ,由威爾遜同餘得 t 2 ≡ − 1 t^2\equiv-1 t 2 ≡ − 1 ,其中 t = ( 2 k ) ! t=(2k)! t = ( 2 k )! 。當 p = 4 k + 3 p=4k+3 p = 4 k + 3 時符號為 − 1 -1 − 1 ,同一計算只給出 ( ( 2 k + 1 ) ! ) 2 ≡ 1 \bigl((2k+1)!\bigr)^2\equiv1 ( ( 2 k + 1 )! ) 2 ≡ 1 ,沒有任何資訊;整除引理說明 − 1 -1 − 1 模這樣的質數沒有平方根。
不可約元是質元。 Z [ i ] \mathbb Z[i] Z [ i ] 中的歐幾里得除法給出貝祖等式,所以整除乘積的不可約高斯整數必整除其中一個因子。這把「p p p 整除 ( t + i ) ( t − i ) (t+i)(t-i) ( t + i ) ( t − i ) 卻不整除任一因子」轉化為「p p p 可分解為兩個非單位之積」。
範數的計數。 由乘法性得 N ( α ) N ( β ) = p 2 N(\alpha)N(\beta)=p^2 N ( α ) N ( β ) = p 2 ,兩個範數都大於 1 1 1 ,所以 N ( α ) = p N(\alpha)=p N ( α ) = p ;寫 α = a + b i \alpha=a+bi α = a + bi 即得座標。
第二步不是構造性的:它證明真因子存在,卻沒有把它找出來。下面的最大公因子計算補上這一點。
高斯整數除法的細節
複數商不一定是高斯整數,因此值得仔細檢查取整步驟。寫 α / β = u + v i \alpha/\beta=u+vi α / β = u + v i ,其中 u , v ∈ R u,v\in\mathbb R u , v ∈ R ,選整數 m , n m,n m , n 使 ∣ u − m ∣ ≤ 1 / 2 |u-m|\le1/2 ∣ u − m ∣ ≤ 1/2 、∣ v − n ∣ ≤ 1 / 2 |v-n|\le1/2 ∣ v − n ∣ ≤ 1/2 ,再令 q = m + n i q=m+ni q = m + ni 。於是餘數 r = α − q β r=\alpha-q\beta r = α − q β 滿足
N ( r ) = N ( β ) N ( ( u − m ) + ( v − n ) i ) ≤ 1 2 N ( β ) . N(r)=N(\beta)N((u-m)+(v-n)i)\le\frac12N(\beta). N ( r ) = N ( β ) N (( u − m ) + ( v − n ) i ) ≤ 2 1 N ( β ) .
當某座標恰在兩個整數中間時,兩種取整都可以;我們需要的是非負整數範數嚴格下降,而不是商唯一。最後一個非零餘數經過回代給出貝祖等式。因此最大公因子只在相差一個單位的意義下唯一;例如 2 + 3 i 2+3i 2 + 3 i 與 − 3 + 2 i -3+2i − 3 + 2 i 互為相伴元素,範數相同。
取 p = 29 p=29 p = 29 、t = 12 t=12 t = 12 ,則 t 2 + 1 = 145 = 5 ⋅ 29 t^2+1=145=5\cdot29 t 2 + 1 = 145 = 5 ⋅ 29 ,故 29 29 29 在 Z [ i ] \mathbb Z[i] Z [ i ] 中整除 ( 12 + i ) ( 12 − i ) (12+i)(12-i) ( 12 + i ) ( 12 − i ) 。對 29 29 29 與 12 + i 12+i 12 + i 做高斯歐幾里得算法:
29 12 + i = 12 5 − 1 5 i , 29 = 2 ( 12 + i ) + ( 5 − 2 i ) . \frac{29}{12+i}=\frac{12}{5}-\frac15i,\qquad
29=2(12+i)+(5-2i). 12 + i 29 = 5 12 − 5 1 i , 29 = 2 ( 12 + i ) + ( 5 − 2 i ) . 商 2 2 2 來自分別取整。接著
12 + i = ( 2 + i ) ( 5 − 2 i ) , N ( 5 − 2 i ) = 25 + 4 = 29. 12+i=(2+i)(5-2i),\qquad N(5-2i)=25+4=29. 12 + i = ( 2 + i ) ( 5 − 2 i ) , N ( 5 − 2 i ) = 25 + 4 = 29. 第二次除法整除,所以最後一個非零餘數是最大公因子,得 29 = 5 2 + 2 2 29=5^2+2^2 29 = 5 2 + 2 2 。無需事先知道答案,只需執行除法。注意同餘 t 2 ≡ − 1 ( m o d p ) t^2\equiv-1\pmod p t 2 ≡ − 1 ( mod p ) 本身還不是平方和表示;最大公因子計算才把它轉化為範數為 p p p 的因子。
為甚麼最大公因子的範數恰為質數
一般地,設 p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) 是質數,t 2 ≡ − 1 ( m o d p ) t^2\equiv-1\pmod p t 2 ≡ − 1 ( mod p ) ,而 d d d 是 p p p 與 t + i t+i t + i 的高斯最大公因子。算法不可能返回單位:否則貝祖等式給出 u p + v ( t + i ) = 1 up+v(t+i)=1 u p + v ( t + i ) = 1 ;乘以 t − i t-i t − i 後,左邊兩項均被 p p p 整除,就會得到 p ∣ t − i p\mid t-i p ∣ t − i ,但其虛部係數為 − 1 -1 − 1 。它也不可能與 p p p 相伴,否則 p ∣ t + i p\mid t+i p ∣ t + i ,而虛部係數為 1 1 1 。
由於 d ∣ p d\mid p d ∣ p ,整數 N ( d ) N(d) N ( d ) 整除 p 2 p^2 p 2 。它既不為 1 1 1 ,也不為 p 2 p^2 p 2 :若為 p 2 p^2 p 2 ,餘下的因子範數為 1 1 1 ,便是單位,於是 d d d 與 p p p 相伴。因此 N ( d ) = p N(d)=p N ( d ) = p 。這與前面的不可約論證使用相同的核心事實,卻進一步說明如何從同餘求出座標。尋找 − 1 -1 − 1 的平方根和執行高斯除法有計算成本;存在性定理本身不是複雜度界。
完整判別法
正整數 n n n 可表示為兩個整數平方數之和,當且僅當它的質因數分解中,每個滿足 p ≡ 3 ( m o d 4 ) p\equiv3\pmod4 p ≡ 3 ( mod 4 ) 的質數 p p p 都以偶數指數出現。
必要性已由整除性質證明。反過來,把 n n n 分解為 2 2 2 、模 4 4 4 餘 1 1 1 的質數,以及模 4 4 4 餘 3 3 3 的質數的偶次冪 p 2 e p^{2e} p 2 e 的乘積。每個因子都是兩個平方數之和:前兩類見上,最後一類為 ( p e ) 2 + 0 2 (p^e)^2+0^2 ( p e ) 2 + 0 2 。再用恆等式
( a 2 + b 2 ) ( c 2 + d 2 ) = ( a c − b d ) 2 + ( a d + b c ) 2 (a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2 ( a 2 + b 2 ) ( c 2 + d 2 ) = ( a c − b d ) 2 + ( a d + b c ) 2 逐次合併表示;它正是 ( a + b i ) ( c + d i ) (a+bi)(c+di) ( a + bi ) ( c + d i ) 的範數乘法公式。這既證明充分性,也說明只要找出 2 2 2 、模 4 4 4 餘 1 1 1 的質數以及偶次冪因子的表示,就能構造 n n n 的座標。定理針對正整數;另有平凡情形 0 = 0 2 + 0 2 0=0^2+0^2 0 = 0 2 + 0 2 。
概念視角 代數
兩個平方數之和即高斯範數 由於 x 2 + y 2 = N ( x + y i ) x^2+y^2=N(x+yi) x 2 + y 2 = N ( x + y i ) ,可表示為兩個平方數之和的整數恰好是高斯整數的範數,而乘積恆等式就是 N N N 的乘法性。用這種語言,判別法記錄的是普通質數在 Z [ i ] \mathbb Z[i] Z [ i ] 中如何分解。質數 2 2 2 等於 − i ( 1 + i ) 2 -i(1+i)^2 − i ( 1 + i ) 2 。質數 p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) 可寫成 π π ‾ \pi\overline\pi π π ,其中 N ( π ) = p N(\pi)=p N ( π ) = p ,如上所證。質數 p ≡ 3 ( m o d 4 ) p\equiv3\pmod4 p ≡ 3 ( mod 4 ) 保持不可約:若 p = α β p=\alpha\beta p = α β 且兩因子均非單位,則 N ( α ) = p N(\alpha)=p N ( α ) = p ,p p p 便是兩個平方數之和,這在模 4 4 4 下不可能。既然不可約,p p p 就是高斯質元素,所以 p ∣ N ( z ) = z z ‾ p\mid N(z)=z\overline z p ∣ N ( z ) = z z 迫使 p ∣ z p\mid z p ∣ z 或 p ∣ z ‾ p\mid\overline z p ∣ z ;無論哪種情況,p p p 都整除 z z z 的兩個座標。因此 p p p 只能通過因子 p 2 = N ( p ) p^2=N(p) p 2 = N ( p ) 整除 N ( z ) N(z) N ( z ) ,這正是其指數為偶數的原因。
例題
21 = 3 ⋅ 7 21=3\cdot7 21 = 3 ⋅ 7 模 4 4 4 餘 1 1 1 ,但 3 3 3 和 7 7 7 均以奇數指數出現,因此不能表示為兩個平方數之和。只檢查 n ( m o d 4 ) n\pmod4 n ( mod 4 ) 會漏掉這個障礙。
130 = 2 ⋅ 5 ⋅ 13 130=2\cdot5\cdot13 130 = 2 ⋅ 5 ⋅ 13 ,其中 2 = 1 2 + 1 2 2=1^2+1^2 2 = 1 2 + 1 2 ,5 = 1 2 + 2 2 5=1^2+2^2 5 = 1 2 + 2 2 ,13 = 2 2 + 3 2 13=2^2+3^2 13 = 2 2 + 3 2 。計算 ( 1 + i ) ( 1 + 2 i ) = − 1 + 3 i (1+i)(1+2i)=-1+3i ( 1 + i ) ( 1 + 2 i ) = − 1 + 3 i ,再乘 2 + 3 i 2+3i 2 + 3 i 得 − 11 + 3 i -11+3i − 11 + 3 i 。取範數即得 130 = 11 2 + 3 2 130=11^2+3^2 130 = 1 1 2 + 3 2 。改變符號或因子的選擇可能得到其他表示。
45 = 3 2 ⋅ 5 = 3 2 + 6 2 45=3^2\cdot5=3^2+6^2 45 = 3 2 ⋅ 5 = 3 2 + 6 2 。雖然 3 ≡ 3 ( m o d 4 ) 3\equiv3\pmod4 3 ≡ 3 ( mod 4 ) ,它的指數是偶數;判別法並未禁止這種質數出現。
常見錯誤
選擇、符號與邊界情況
乘積恆等式可能給出多種表示,因為改變一個因子為其共軛不會改變範數。對於 65 = 5 ⋅ 13 65=5\cdot13 65 = 5 ⋅ 13 ,利用 5 = N ( 2 + i ) 5=N(2+i) 5 = N ( 2 + i ) 、13 = N ( 3 + 2 i ) 13=N(3+2i) 13 = N ( 3 + 2 i ) ,有
( 2 + i ) ( 3 + 2 i ) = 4 + 7 i , ( 2 + i ) ( 3 − 2 i ) = 8 − i . (2+i)(3+2i)=4+7i,\qquad (2+i)(3-2i)=8-i. ( 2 + i ) ( 3 + 2 i ) = 4 + 7 i , ( 2 + i ) ( 3 − 2 i ) = 8 − i .
取範數得到 65 = 4 2 + 7 2 = 8 2 + 1 2 65=4^2+7^2=8^2+1^2 65 = 4 2 + 7 2 = 8 2 + 1 2 。高斯因子乘以單位會改變符號或交換座標,取共軛則改變虛部的符號;但這兩組數即使忽略符號和次序仍不同。判別法只判斷能否表示,本身不計算所有表示的個數。
還要注意邊界。1 = 1 2 + 0 2 1=1^2+0^2 1 = 1 2 + 0 2 :其質因數分解中沒有違反條件的指數,故條件真空成立。負數不能寫成兩個整數平方數之和,因為平方數非負;零則用 0 = 0 2 + 0 2 0=0^2+0^2 0 = 0 2 + 0 2 單獨處理,不必為零編造質因數分解。最後,要求兩個座標都嚴格為正是另一個問題;本定理容許座標為零,並不自動給出兩個正座標。
質數的論證是從「p p p 是質數且 p ≡ 1 ( m o d 4 ) p\equiv1\pmod4 p ≡ 1 ( mod 4 ) 」推到「t 2 ≡ − 1 ( m o d p ) t^2\equiv-1\pmod p t 2 ≡ − 1 ( mod p ) 有解」,不能反過來當作質數檢驗:7 2 = 49 ≡ − 1 ( m o d 25 ) 7^2=49\equiv-1\pmod{25} 7 2 = 49 ≡ − 1 ( mod 25 ) ,但 25 25 25 是合數。
實際判別時先求完整 的質因數分解,再逐個檢查模 4 4 4 餘 3 3 3 的質數的指數。兩個這樣的質數相乘可以模 4 4 4 餘 1 1 1 ,卻可能不滿足判別法,21 21 21 就是例子。反之,偶次冪可以吸收到兩個座標裏:p 2 e ( a 2 + b 2 ) = ( p e a ) 2 + ( p e b ) 2 p^{2e}(a^2+b^2)=(p^ea)^2+(p^eb)^2 p 2 e ( a 2 + b 2 ) = ( p e a ) 2 + ( p e b ) 2 。關鍵是每個相關質數各自的指數,而不是質因數總數或整個數的餘數。
從座標讀出準確指數
整除障礙提供的不只是偶數指數。設質數 p ≡ 3 ( m o d 4 ) p\equiv3\pmod4 p ≡ 3 ( mod 4 ) ,且 x 2 + y 2 ≠ 0 x^2+y^2\ne0 x 2 + y 2 = 0 。令 m m m 為使 p m p^m p m 同時整除兩個座標的最大非負整數。即使一個座標為零,另一個也非零,因此這樣的最大值存在。寫 x = p m u x=p^mu x = p m u 、y = p m v y=p^mv y = p m v ,則 u , v u,v u , v 至少一個不被 p p p 整除。由整除引理,p p p 不可能整除 u 2 + v 2 u^2+v^2 u 2 + v 2 ;否則它會同時整除 u , v u,v u , v 。因此
v p ( x 2 + y 2 ) = 2 m . v_p(x^2+y^2)=2m. v p ( x 2 + y 2 ) = 2 m .
這從兩個座標的共同尺度解釋了指數為何為偶數。例如,非零平方和恰被 3 3 3 整除六次時,兩個座標均被 27 27 27 整除,卻不能同時被 81 81 81 整除。約定 v p ( 0 ) = + ∞ v_p(0)=+\infty v p ( 0 ) = + ∞ ,結論涉及座標指數的最小值 ,並不要求二者相等;例如 3 2 + 0 2 = 9 3^2+0^2=9 3 2 + 0 2 = 9 有一個零座標。
對於給定的小數,還可以做有界搜尋。若 x 2 + y 2 = 65 x^2+y^2=65 x 2 + y 2 = 65 ,則 ∣ x ∣ , ∣ y ∣ ≤ 8 |x|,|y|\le8 ∣ x ∣ , ∣ y ∣ ≤ 8 。忽略符號及次序,檢查不超過 65 65 65 的平方數:只有 1 + 64 1+64 1 + 64 與 16 + 49 16+49 16 + 49 之和為 65 65 65 。所以前面得到的 ( 1 , 8 ) (1,8) ( 1 , 8 ) 與 ( 4 , 7 ) (4,7) ( 4 , 7 ) 已包含所有此意義下不同的表示。這個有限搜尋證明的是本例的完整性,而分解判別法本身只保證存在。輸入很大時,搜尋可能昂貴;得到完整質因數分解也可能困難,因此不能把任何一種方法直接當成快速算法。
分別檢查每個指數
考慮 n = 3 2 ⋅ 7 ⋅ 13 = 819 n=3^2\cdot7\cdot13=819 n = 3 2 ⋅ 7 ⋅ 13 = 819 。3 3 3 的指數為偶數,13 13 13 模 4 4 4 餘 1 1 1 ,但 7 7 7 模 4 4 4 餘 3 3 3 且只出現一次,所以 819 819 819 不能表示。只檢查第一個質數,或把 3 3 3 與 7 7 7 的指數加成一個總數,都會丟掉判別法需要的資訊。相反,再乘一個 7 7 7 後,每個相關指數都是偶數:事實上 5733 = ( 3 ⋅ 7 ) 2 ⋅ 13 = 42 2 + 63 2 5733=(3\cdot7)^2\cdot13=42^2+63^2 5733 = ( 3 ⋅ 7 ) 2 ⋅ 13 = 4 2 2 + 6 3 2 。這裏的座標來自將 13 = 2 2 + 3 2 13=2^2+3^2 13 = 2 2 + 3 2 的兩個座標同乘 21 21 21 ;兩個座標恰好都是正數。這既符合判別法,也給出可直接計算核實的表示:驗證最後的等式並不需要重新依賴整個分解證明。
練習
快速檢查
(75 75 75 能否表示為兩個平方數之和?)
解答 · 答案 75 = 3 ⋅ 5 2 75=3\cdot5^2 75 = 3 ⋅ 5 2 ,其中 3 3 3 的指數為奇數,所以不能。
快速檢查
(給出 65 65 65 的兩種表示,暫不區分符號及次序。)
解答 · 答案 65 = 1 2 + 8 2 = 4 2 + 7 2 65=1^2+8^2=4^2+7^2 65 = 1 2 + 8 2 = 4 2 + 7 2 。僅靠這兩式不能斷言沒有其他表示。
快速檢查
(若 7 ∣ x 2 + y 2 7\mid x^2+y^2 7 ∣ x 2 + y 2 ,證明 49 ∣ x 2 + y 2 49\mid x^2+y^2 49 ∣ x 2 + y 2 。)
解答 · 答案 7 ≡ 3 ( m o d 4 ) 7\equiv3\pmod4 7 ≡ 3 ( mod 4 ) ,故 7 7 7 整除兩個座標,因而 49 49 49 整除它們的平方和。
快速檢查
(2025 2025 2025 能否表示為兩個平方數之和?)
解答 · 答案 2025 = 45 2 + 0 2 2025=45^2+0^2 2025 = 4 5 2 + 0 2 。判別法也給出相同結果:2025 = 3 4 5 2 2025=3^4 5^2 2025 = 3 4 5 2 ,3 3 3 的指數為偶數。
快速檢查
(求 98 98 98 的一個表示並解釋為何因子 7 7 7 無礙。)
解答 · 答案 98 = 2 ⋅ 7 2 = 7 2 + 7 2 98=2\cdot7^2=7^2+7^2 98 = 2 ⋅ 7 2 = 7 2 + 7 2 ;質數 7 ≡ 3 ( m o d 4 ) 7\equiv3\pmod4 7 ≡ 3 ( mod 4 ) 的指數為偶數 2 2 2 ,判別法容許表示。
快速檢查
(忽略符號和次序,列出 5 5 5 的所有表示。)
解答 · 答案 若 x 2 + y 2 = 5 x^2+y^2=5 x 2 + y 2 = 5 ,兩座標的絕對值都不超過 2 2 2 ,可用平方數只有 0 , 1 , 4 0,1,4 0 , 1 , 4 ;只有 1 + 4 = 5 1+4=5 1 + 4 = 5 ,故唯一數對是 ( 1 , 2 ) (1,2) ( 1 , 2 ) 。
快速檢查
(若 3 5 ∣ x 2 + y 2 3^5\mid x^2+y^2 3 5 ∣ x 2 + y 2 ,是否必有 3 6 ∣ x 2 + y 2 3^6\mid x^2+y^2 3 6 ∣ x 2 + y 2 ?)
解答 · 答案 平方和為零時每個正整數都整除它;非零時其 3 3 3 的指數為偶數,既然至少為 5 5 5 ,便至少為 6 6 6 。也可對兩個座標反覆使用整除引理。
快速檢查
(給出 85 85 85 的兩種表示,忽略符號和次序。)
解答 · 答案 85 = 2 2 + 9 2 = 6 2 + 7 2 85=2^2+9^2=6^2+7^2 85 = 2 2 + 9 2 = 6 2 + 7 2 ,兩對不同。兩個平方數之和定理保證存在,但不聲稱它們是僅有的表示。