Sum of Two Squares

當一個正整數不是某個整數的平方時, 我們有興趣知道它是否可寫成兩個整數的平方和. 若 n 本身是某個整數的平方, 即存在 m $\in$ $\mathbb {N}$ 使得 n = m², 當然我們可以將 n 寫成 n = m² + 0². 所以我們可以將可寫成兩個整數的平方和的數視為平方數的推廣.

首先我們來看一個有趣的等式:

(a² + b²)(c² + d²) = (ac + bd )² + (ad - bc)². (7.1)

這個等式可以直接將等號兩邊展開來求證, 也可以用大家熟悉的複數運算來說明. 假設 z₁ = a + bi, z₂ = d + ci $\in$ $\mathbb {C}$ (這裡 $\mathbb {C}$ 表示複數所成之集合, 而 i $\in$ $\mathbb {C}$ 滿足 i² = - 1). 我們知 z₁, z₁ 的共軛複數分別為 $\overline{z_1}$ = a - bi,$\overline{z_2}$ = d - ci 且 $\left\vert\vphantom{ z_1}\right.$z₁$\left.\vphantom{ z_1}\right\vert^{2}_{}$ = z₁$\overline{z_1}$ = a² + b² 及 $\left\vert\vphantom{ z_2}\right.$z₂$\left.\vphantom{ z_2}\right\vert^{2}_{}$ = z₂$\overline{z_2}$ = c² + d². 因此

(a² + b²)(c² + d²) = z₁$$\overline{z_1}$$z₂$$\overline{z_2}$$ = z₁z₂$$\overline{z_1z_2}$$ = $$\left\vert\vphantom{(ad-bc)+(ac+bd)\mathbf{i}}\right.$$(ad - bc) + (ac + bd )i$$\left.\vphantom{(ad-bc)+(ac+bd)\mathbf{i}}\right\vert^{2}_{}$$ = (ac + bd )² + (ad - bc)².

利用式子 (7.1) 我們馬上有以下之結果.

Lemma 7.3.1   若 m, n $\in$ $\mathbb {N}$ 皆可以寫成兩個整數的平方和, 則 mn 亦可以寫成兩個整數的平方和.

証 明. 若 m = a² + b² 且 n = c² + d², 其中 a, b, c, d $\in$ $\mathbb {Z}$, 則利用式子 (7.1) 知 mn = (ac + bd )² + (ad - bc)². 因 ac + bd, ad - bc $\in$ $\mathbb {Z}$ 故知 mn 亦可以寫成兩個整數的平方和. $\qedsymbol$

注意 Lemma 7.3.1 僅告訴我們當 m, n 皆可以寫成兩個整數的平方和時, mn 也可以寫成兩個整數的平方和; 它並沒有告訴我們若 m, n 中有一個不能寫成兩個整數的平方和時, mn 是否可以寫成兩個整數的平方和.

由於每個大於 1 的整數都可以寫成質因數的乘積, 所以由 Lemma 7.3.1 我們很自然的要探討哪些質數可以寫成兩個整數的平方和哪些質數不能. 由於 2 = 1² + 1², 即 2 可以寫成兩個整數的平方和, 因此以下我們僅考慮奇質數的情形. 利用 Lemma 7.3.1 我們可以得到一個判別一個質數是否可以寫成兩個整數的平方和的方法.

Lemma 7.3.2   假設 p 是一個質數. 若存在 a, b $\in$ $\mathbb {Z}$ 使得 a² + b² = $\lambda$p, 其中 $\lambda$ $\in$ $\mathbb {N}$ 滿足 $\lambda$ < p, 則 p 可以寫成兩個整數的平方和.

証 明. 考慮集合 S = {s $\in$ $\mathbb {N}$ | 存在 u, v $\in$ $\mathbb {Z}$ 使得 u² + v² = sp}. 依照 S 的定義, 要證明 p 可以寫成兩個整數的平方和就等同於要證明 1 $\in$ S. 要如何知 1 $\in$ S 呢? 依假設知 S 為非空集合 (因 $\lambda$ $\in$ S) 且 S 的元素皆為正整數, 所以 1 $\in$ S 若且唯若 S 中最小的元素就是 1 (注意依正整數的 well-ordering principle, 由於 S 不是空集合所以 S 中必存在最小的元素). 令 m $\in$ S 是 S 中最小的元素, 我們要證明 m = 1.

利用反證法, 假設 m$\ne$1. 故由 $\lambda$ $\in$ S 且 $\lambda$ < p 知 1 < m < p. 我們希望在 S 中找到比 m 更小的數而得到矛盾. 由於 m $\in$ S, 故存在 u, v $\in$ $\mathbb {Z}$ 使得 u² + v² = mp, 我們分成 m 是偶數及 m 是奇數兩種情況討論.

(I) m 是偶數: 此時由於 u² + v² = mp 是偶數, 我們知 u, v 必同奇同偶 (否則 u² + v² 不會是偶數), 即 u + v 和 u - v 皆為偶數. 此時 (u + v)/2 和 (u - v)/2 皆為整數且

($${\frac{u+v}{2}}$$)² + ($${\frac{u-v}{2}}$$)² = $${\frac{u^2}{2}}$$ + $${\frac{v^2}{2}}$$ = $${\frac{m}{2}}$$p.

故知 m/2 $\in$ S 且 m/2 < m, 此與 m 是 S 中最小的元素相矛盾.

(II) m 是奇數: 因為當 m 是奇數時

{$${\frac{-m+1}{2}}$$,$${\frac{-m+1}{2}}$$ + 1,..., 0, 1,...,$${\frac{m-1}{2}}$$ - 1,$${\frac{m-1}{2}}$$}

是一個 complete residue system modulo m. 我們可找到 c, d $\in$ $\mathbb {Z}$ 滿足 c $\equiv$ u(mod m) 且 d $\equiv$ v(mod m), 其中 - (m - 1)/2$\le$c, d$\le$(m - 1)/2. 注意這裡 c 和 d 不能同時等於 0, 這是因為如果 c = d = 0 表示 u $\equiv$ v $\equiv$ 0(mod m), 即 m| u 且 m| v. 因此 m²| u² + v² = mp, 即 m| p. 如此會和 1 < m < p 相矛盾, 故知 c 和 d 不同時為 0. 因為 c² + d² $\equiv$ u² + v²(mod m) 以及 u² + v² = mp, 我們得 c² + d² $\equiv$ 0(mod m). 亦即存在 k $\in$ $\mathbb {Z}$ 使得 c² + d² = km. 注意因 c 和 d 不同時為 0, 故 k$\ne$ 0. 另一方面因為 - (m - 1)/2$\le$c, d$\le$(m - 1)/2, 所以 c² + d²$\le$(m - 1)²/4 + (m - 1)²/4 = (m - 1)²/2 < m², 故得 0 < k < m. 也就是說 k $\in$ $\mathbb {N}$ 且 k < m. 現在我們有兩個等式: u² + v² = mp 以及 c² + d² = km. 利用式子 (7.1) 得

(uc + vd )² + (ud - vc)² = m²kp.

又因為 u $\equiv$ c(mod m) 且 v $\equiv$ d(mod m), 我們得

uc + vd $$\equiv$$ u² + v² $$\equiv$$ 0(mod m)    and    ud - vc $$\equiv$$ uv - uv $$\equiv$$ 0(mod m).

也就是說 (uc + vd )/m $\in$ $\mathbb {Z}$ 且 (ud - vc)/m $\in$ $\mathbb {Z}$. 因此知

($${\frac{uc+vd}{m}}$$)² + ($${\frac{ud-vc}{m}}$$)² = kp,

也就是說 kp 可以寫成兩個整數的平方和, 故又由 k $\in$ $\mathbb {N}$ 知 k $\in$ S. 然而我們又知 k < m, 此與 m 是 S 中最小的元素相矛盾.

我們證得若 m$\ne$1 會造成 m 不是偶數且不是奇數這樣的矛盾. 故由反證法知原假設 m$\ne$1 不成立, 也就是說 m = 1. 因此得證 p 可以寫成兩個整數的平方和. $\qedsymbol$

Lemma 7.3.2 的證明方法其實是類似於 descent 的方法都是由一個解得到更小的解而推得矛盾. 或許大家會疑惑為何同樣的推論方法, 一個會得到無解; 另一個卻推得有解. 這是因為在 descent 的方法推論中是沒有任何條件的, 所以若有正整數解則會沒有限制的推得無窮多個更小的正整數解而造成矛盾, 因此會得到無解的結論. 而這裡所用的方法中會得到比 m 更小的正整數是有條件的, 也就是說必須在 m > 1 的情形才可以. 因此同樣推得矛盾, 但此時矛盾會讓我們推得 m = 1, 所以有解. 希望這兩者邏輯上的差異, 大家都能了解. 另外 Lemma 7.3.2 證得存在的方法表面上好像只是邏輯推演, 並沒有告訴我們如何找到解. 事實上其解法過程中包含了找到解的方法. 我們來看一個具體的例子.

Example 7.3.3   考慮 p = 89. 由於 89 $\equiv$ 1(mod 4), 我們知存在 a $\in$ $\mathbb {Z}$ 使得 a² $\equiv$ - 1(mod 89). 事實上當 a = 34 時, a² = 1156 $\equiv$ - 1(mod 89), 我們有 (34)² + 1 = 13×89. 因為 13 < 89 故由 Lemma 7.3.2 知 89 可以寫成兩個整數的平方和. 我們要利用 Lemma 7.3.2 的證明方法將 89 寫成兩個整數的平方和.

對應到 Lemma 7.3.2 的證明, 我們知 13 $\in$ S. 因 13$\ne$1, 我們要利用 13, 在 S 中找到更小的元素. 我們要找到 c, d 滿足 34 $\equiv$ c(mod 13), 1 $\equiv$ d(mod 13) 以及 -6$\le$c, d$\le$6. 很容易得知 c = - 5 且 d = 1. 接著我們考慮 c² + d² = 25 + 1 = 26 = 2×13. 故由式子 (7.1) 得

(34×(- 5) + 1)² + (34 - (- 5))² = 169² + 39² = 2×13²×89.

由於 169 = 13×13 且 39 = 3×13, 我們得 13² + 3² = 2×89, 也就是說 2 $\in$ S. 注意到我們已將 13 $\in$ S 降到 2 $\in$ S. 再利用處理偶數情況的方法, 將 2 縮小. 即得

($${\frac{13+3}{2}}$$)² + ($${\frac{13-3}{2}}$$)² = 8² + 5² = 89.

在 Example 7.3.3 中我們利用 89 $\equiv$ 1(mod 4) 所以可以找到 a $\in$ $\mathbb {Z}$ 滿足 a² $\equiv$ - 1(mod 89). 再適當的選取 a (即選取 a 夠小) 使得 a¹ + 1 = $\lambda$p, 其中 0 < $\lambda$ < p, 以便套用 Lemma 7.3.2. 在一般的情形, 當 p 是一質數滿足 p $\equiv$ 1(mod 4) 時, 我們都可以如此作. 所以我們有以下之結果.

Proposition 7.3.4   若 p 是一質數且 p $\equiv$ 1(mod 4), 則 p 可以寫成兩個整數的平方和.

証 明. 由於 p $\equiv$ 1(mod 4), Theorem 5.4.1 告訴我們 x² $\equiv$ - 1(mod p) 有解. 亦即存在 a $\in$ $\mathbb {N}$ 使得 a² $\equiv$ - 1(mod p). 由於 {1, 2,..., p - 1} 是一個 reduced residue system modulo p, 所以我們可以選取 1$\le$a$\le$p - 1 使得 a² $\equiv$ - 1(mod p) (事實上可選取 1 < a < p/2). 因此存在 $\lambda$ $\in$ $\mathbb {N}$ 使得 a² + 1 = $\lambda$p. 又因為 a$\le$p - 1, 我們有 $\lambda$p = a² + 1$\le$(p - 1)² + 1 = p² - 2(p - 1) < p². 也就是說 $\lambda$ < p, 故利用 Lemma 7.3.2 得證 p 可以寫成兩個整數的平方和. $\qedsymbol$

接下來我們看怎樣的質數不能寫成兩個整數的平方和. 當 p $\equiv$ 1(mod 4) 時, 在 Proposition 7.3.4 我們是利用此時 x² $\equiv$ - 1(mod p) 有解證得 p 可以寫成兩個整數的平方和. 我們也可以利用當 p $\equiv$ 3(mod 4) 時, x² $\equiv$ - 1(mod p) 無解證得 p 不可以寫成兩個整數的平方和.

Lemma 7.3.5   假設 p 是一個質數滿足 p $\equiv$ 3(mod 4) 且 n $\in$ $\mathbb {N}$ 滿足 p| n. 若 a, b $\in$ $\mathbb {Z}$ 使得 a² + b² = n, 則 p| a 且 p| b.

証 明. 我們要用反證法證明此定理. 不失一般性, 我們假設 p$\nmid$a. 此時由 a² + b² = n 且 p| n 知 p$\nmid$b, 否則由 a² = n - b² 得 p| a² 會造成與 p$\nmid$a 的假設相矛盾. 既然 a² + b² = n 且 p| n, 我們得 a² $\equiv$ - b²(mod p). 注意由於 a, b 皆與 p 互質, 我們可以用 Legendre symbol 處理問題. 利用 Legendre symbol 的性質 (Lemma 5.3.2) 知

1 = $$\left(\vphantom{\dfrac{{a^2}}{\,{p}\,}}\right.$$$${\dfrac{{a^2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{a^2}}{\,{p}\,}}\right)$$ = $$\left(\vphantom{\dfrac{{-b^2}}{\,{p}\,}}\right.$$$${\dfrac{{-b^2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{-b^2}}{\,{p}\,}}\right)$$ = $$\left(\vphantom{\dfrac{{-1}}{\,{p}\,}}\right.$$$${\dfrac{{-1}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{-1}}{\,{p}\,}}\right)$$$$\left(\vphantom{\dfrac{{b^2}}{\,{p}\,}}\right.$$$${\dfrac{{b^2}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{b^2}}{\,{p}\,}}\right)$$ = $$\left(\vphantom{\dfrac{{-1}}{\,{p}\,}}\right.$$$${\dfrac{{-1}}{\,{p}\,}}$$$$\left.\vphantom{\dfrac{{-1}}{\,{p}\,}}\right)$$.

然而由 p $\equiv$ 3(mod 4) 以及 Theorem 5.4.1 我們知 $\left(\vphantom{\dfrac{{-1}}{\,{p}\,}}\right.$${\dfrac{{-1}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{-1}}{\,{p}\,}}\right)$ = - 1. 由此矛盾知 p| a, 並由 b² = n - a² 得 p| b. $\qedsymbol$

Lemma 7.3.5 證明的想法類似於 Proposition 7.1.1 所提的方法, 即利用探討 x² + y² = n 這個 Diophantine equation 在 modulo p 的情形來推得此 Diophantine equation 無解. 利用 Lemma 7.3.5 我們馬上得到以下之結果.

Proposition 7.3.6   若 p 是一質數且 p $\equiv$ 3(mod 4), 則 p 不能寫成兩個整數的平方和.

証 明. 我們用反證法. 假設存在 a, b $\in$ $\mathbb {Z}$ 使得 a² + b² = p. 由於 p 是質數, 我們知 a, b 皆不等於 0. 故知可取 a, b $\in$ $\mathbb {N}$ 滿足 1$\le$a$\le$p - 1 且 1$\le$b$\le$p - 1. 此時 a, b 皆與 p 互質故與 Lemma 7.3.5 的結果相矛盾. 由此矛盾知 p 不能寫成兩個整數的平方和. $\qedsymbol$

知道了哪些質數可以寫成兩個整數的平方和, 哪些質數不可以寫成兩個整數的平方和. 接下來我們就來探討哪些正整數可以寫成兩個整數的平方和. 給定一正整數 n. 若 n = 1 當然可寫成兩個整數的平方和. 若 n$\ge$2, 首先我們將 n 作質因數的分解. 我們可以將 2 和除以 4 餘 1 的質因數忽略, 因為它們可以寫成兩個整數的平方和. 而若 n 有除以 4 餘 3 的質因數, 我們又可以將有平方的部份忽略, 因為它們也可以寫成兩個整數的平方和. 由此看出質因數分解後的次數是重要的, 我們特別用以下名詞的定義: 若 n = p₁^{n₁ ...} p_r^n_r, 其中這些 p_i 是相異質數. 我們稱 p_i 是 n 的質因數且 n_i 是 p_i 的次數. 例如 2250 = 2×3²×5³, 我們稱 2250 有 2 次 3 的質因數且有 3 次 5 的質因數. 依此定義我們有以下之結果.

Theorem 7.3.7   假設 n $\in$ $\mathbb {N}$. 則 n 可以寫成兩個整數的平方和若且唯若 n 沒有任何的除以 4 餘 3 的質因數其次數是奇數.

証 明. 假設 n 沒有任何的除以 4 餘 3 的質因數其次數是奇數. 我們僅需考慮 n$\ge$2 的情形. 此時可將 n 質因數分解成

n = 2^n₀q₁^{n₁ ...} q_r^{n_r .} p₁^{2m₁ ...} p_s^2m_s,

其中 q_i, p_j 皆為相異的奇質數且 q_i $\equiv$ 1(mod 4) 及 p_j $\equiv$ 3(mod 4). 由於我們可將 n 寫成

n = 2^n₀q₁^{n₁ ...} q_r^{n_r .} (p₁^{m₁ ...} p_s^m_s)²,

而 2 可以寫成兩個整數的平方和, q₁,..., q_r 可以寫成兩個整數的平方和 (Proposition 7.3.4) 以及 (p₁^{m₁ ...} p_s^m_s)² 可以寫成兩個整數的平方和 (因為是一個平方數), 故由 Lemma 7.3.1 知 n 可以寫成兩個整數的平方和.

反之, 若 p $\equiv$ 3(mod 4) 是 n 的一個質因數且其次數為 2k + 1, 即 n = p^{2k + 1}n', 其中 p$\nmid$n'. 我們用反證法證明 n 不可以寫成兩個整數的平方和. 假設存在 a, b $\in$ $\mathbb {Z}$ 使得 a² + b² = n. 則由 Lemma 7.3.5 知 p| a 且 p| b. 令 a = p^rc 且 b = p^sd, 其中 c, d 皆與 p 互質且 r, s $\in$ $\mathbb {N}$. 不失一般性我們假設 2r$\le$2s, 我們要證明 2k + 1 > 2r. 假設 2k + 1 < 2r, 由 p^2rc² + p^2sd² = p^{2k + 1}n' 知 n' = p^{2r - 2k - 1}c² + p^{2s - 2k - 1}d². 又因為 2s - 2k - 1$\ge$2r - 2k - 1 > 0 知 p| n'. 此與 p$\nmid$n' 相矛盾, 故知 2k + 1 > 2r. 再由 p^2rc² + p^2sd² = p^{2k + 1}n' 知

c² + p^{2s - 2r}d² = c² + (p^{s - r}d )² = p^{2k + 1 - 2r}n',

即 p^{2k + 1 - 2r}n' 可以寫成 c 和 p^{s - r}d 的平方和. 由於 p $\equiv$ 3(mod 4), p| p^{2k + 1 - 2r}n' 且 p$\nmid$c, 此與 Lemma 7.3.5 的結果相矛盾, 故知 n 不可以寫成兩個整數的平方和. $\qedsymbol$

例如 2250 = 2×3²×5³ 中唯一的除以 4 餘 3 的質因數是 3, 且 3 的次數為 2 是偶數, 所以 2250 可以寫成兩個整數的平方和. 事實上 2250 = 45² + 15². 另外 6174 = 2×3²×7³ 中除以 4 餘 3 的質因數是 3 和 7, 其中 7 的次數為 3 是奇數, 所以 6174 無法寫成兩個整數的平方和.