动机
哪些正整数可以写成 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 ,两对不同。两个平方数之和定理保证存在,但不声称它们是仅有的表示。