# 代數導論二 Week 4 (Part 4) - Fermat's Theorem for Sum of Squares

[TOC]

這邊其實就是把 *Fermat's Theorem for Sum of Square* 證明完。

## 引理：質數可以寫成平方和的充要條件

:::danger

假定 $p$ 是一個 $\Bbb Z$ 中的質數。則下列兩個敘述等價：

1. 以下的 $n$ 在 $\Bbb Z/p\Bbb Z$ 中有解：

$$
n^2 + 1 \equiv 0 \text{ mod }p
$$

2. $p$ 可以拆成兩個整數的平方和：

$$
\exists a, b \in \Bbb Z.p = a^2 + b^2
$$

:::

($\Leftarrow$)：假定敘述 $(1)$ 成立，那麼 $p$ 在 $\Bbb Z[i]$ 中可以寫成：

$$
p \mid n^2 + 1 = (n + i)(n - i)
$$

這時候，$p$ 只有兩種可能：

1. $p$ 在 $\Bbb Z[i]$ 中 *irreducibe* (等價地，*prime*)。
2. $p$ 在 $\Bbb Z[i]$ 中不是 *irreducible*。

但是第一個不可能，因為假定這時 $p$ 也是一個 $\Bbb Z[i]$ 的 *prime*。這時候就要有：

$$
p \mid (n + i) \text{ or }p \mid (n - i)
$$

但是這樣會有矛盾，因為這表示：存在 $x, y \in \Bbb Z$，使得：

$$
(n + i) = p(x + yi)
$$

但是這表示 $py = 1$，可是 $p$ 是質數，$y$ 是整數，所以這不可能發生。所以就證明了 $p$ 在 $\Bbb Z[i]$ 中 *reducible*，也就是存在 $\pi, \pi'$：

$$
p = \pi \pi'
$$

其中，$\pi, \pi'$ 都是 *prime*。兩邊一起取 *norm*，就會發現：

$$
N(p) = p^2 = N(\pi) N(\pi')
$$

由前面的討論，這個狀況發生時，要有 $N(\pi) = N(\pi') = \pm p$。假定這時候：

$$
\pi = a + bi \quad a, b \in \Bbb Z
$$

那麼 $N(\pi) = \pm p$ 的意思是：

$$
N(\pi) = a^2 + b^2 = \pm p
$$

因為在 $\Bbb Z[i]$ 中，$N$ 就是複數格子點的距離平方，所以只能是正的。也就是：

$$
N(\pi) = a^2 + b^2 = p
$$

所以 $p$ 就可以表為兩個整數的平方和。

($\Leftarrow$)：假定 $p$ 可以寫成兩個整數的平方和，也就是假定存在 $a, b \in \Bbb Z$，使得：

$$
p = a^2 + b^2
$$

也就是說，在 $\Bbb Z/p\Bbb Z$ 中，$(a^2 + b^2)$ 是 $\bar 0$：

$$
\bar a^2 + \bar b^2 = \bar 0 \text{ in }\Bbb Z/p\Bbb Z
$$

更進一步，因為 $a, b \in \Bbb Z$，而且 $a^2 + b^2 = p$，所以：

$$
|a| < p \text{ and }|b| < p
$$

而且因為 $p$ 是質數，所以：

$$
\gcd (a, p) = 1
$$

由輾轉相除法原理，存在 $m, n \in \Bbb Z$，使得：

$$
ma + np = 1
$$

也就是：

$$
ma \equiv 1 \text{ mod }p
$$

把這個 $m$ 同時平方乘到 $a^2 + b^2$ 上，就可以觀察到：

$$
\begin{align}
&a^2 + b^2 \equiv 0 \text{ mod }p
\newline
&\Rightarrow m^2a^2 + m^2b^2 \equiv 0 \text{ mod }p
\newline
&\Rightarrow (ma)^2 + (mb)^2 \equiv 0 \text{ mod }p
\end{align}
$$

不過觀察一下就會發現：

$$
\underbrace{(ma)^2}_{=\bar 1^2 = \bar 1} + (mb)^2 \equiv 0 \text{ mod }p
$$

所以上面這個東西其實就表示：

$$
1 + (mb)^2 \equiv 0 \text{ mod }p
$$

因此 $mb$ 就是那個要解的 $n$。

## 引理：另一個質數可以寫成平方和的充條件

:::danger

假定 $p$ 是一個 $\Bbb Z$ 中的質數。則：

$$
\begin{align}
&(p = 2) \text{ or }(p \equiv 1 \text{ mod } 4)
\newline
&\iff \exists a, b \in \Bbb Z.p = a^2 + b^2
\end{align}
$$

:::

$(\Leftarrow)$：這是相對容易的方向。如果 $a = b = 1$，那麼 $p$ 就是 $2$。另外一方面，如果 $a, b$ 其中一個比 $1$ 大，那麼一定要 $a, b$ 裡面其中一個是奇數，另外一個是偶數，否則 $(a^2 + b^2)$ 就會是個偶數。但是一個奇數的平方加一個偶數平方，結果一定會模 $4$ 餘 $1$，所以就證明完了。

$(\Rightarrow)$：從上面的等價條件知道，只要證明所有模 $4$ 餘 $1$ 的質數 $p$，下面的這個東西的 $n$ 都有解：

$$
n^2 + 1 \equiv 0 \text{ mod }p
$$

可以觀察：在這個狀況下，$\Bbb Z/p\Bbb Z$ 中的元素 $x$ 如果有乘法反元素，而且這個 $x$ 不是 $\pm 1$，那麼這個反元素就不會是 $x$ 自己。也就是對於任意 $\pm 1 \neq x \in \Bbb Z/p\Bbb Z$，若：

$$
\begin{align}
&x^2 \equiv 1 \text{ mod }p
\newline
&\iff x = \pm 1 \text{ mod }p
\end{align}
$$

右邊到左邊是顯然的，所以證左邊到右邊既可以了。也就是要問：

$$
x^2 - 1 \equiv 0 \text{ mod }p
$$

時，$x$ 會不會剛好是模 $p$ 餘 $1$。觀察上面這句話，就是在說：

$$
p \mid (x + 1)(x - 1)
$$

因為 $p$ 是質數，所以：

$$
p \mid (x + 1) \text{ or }p \mid (x - 1)
$$

如果是 $p \mid (x + 1)$ 的狀況，那就有：

$$
x = -1 \text{ mod }p
$$

另外一方面，如果是 $p \mid (x - 1)$ 的狀況，那就有：

$$
x = 1 \text{ mod }p
$$

兩個合起來就證明完了。那有這個東西有什麼用呢？這是因為 $(\Bbb Z/p\Bbb Z)^*$ 會是 $\Bbb Z/p\Bbb Z$ 少掉 $\bar 0$。又因為 $p$ 模 $4$ 餘 $1$，所以 $(\Bbb Z/p\Bbb Z)^*$ 的大小就會是 $4$ 的倍數：

$$
|(\Bbb Z/p\Bbb Z)^*| = 4k \quad k \in \Bbb N
$$

所以令：

$$
\begin{align}
(\Bbb Z/p\Bbb Z)^* = &\{1, -1\} & (1)
\newline
&\cup\{2, 3, ... 2k\} & (2)
\newline
&\cup\{-2, -3, ... -2k\} & (3)
\end{align}
$$

對於 $(2)\cup(3)$ 裡面的元素，因為他們都不是 $\pm 1$，裡面每一個人都跟自己不一樣的人湊成一對反元素。所以：

$$
\left(\prod_{i = 2}^{k}i \right) \left(\prod_{i = 2}^{k}-i \right) \equiv 1^{2k - 1} \text{ mod }p
$$

把 $\pm 1$ 也一起放進去，就會發現：

$$
\left(\prod_{i = 1}^{k}i \right) \left(\prod_{i = 1}^{k}-i \right) \equiv -1 \text{ mod }p
$$

所以，把裡面所有元素乘起來，就會是那個要解的 $n$：

$$
\underbrace{\left(\prod_{i = 1}^{k}i \right) \left(\prod_{i = 1}^{k}-i \right)}_{n} \equiv -1 \text{ mod }p
$$

## 觀察：Fermat's Theorem on Sum of Squares

:::danger

假定 $p \in \Bbb Z$ 是一個質數，則：

$$
p = a^2 + b^2 \quad a, b \in \Bbb Z
$$

等價於

$$
(p \equiv 2) \text{ or } (p\equiv 1 \text{ mod }4)
$$

更進一步，假定 $a, b$ 是一個上述的解，除了把 $a, b$ 用下面兩個操作得到的其他的解之外：

1. 交換 $a, b$ 的值。
2. 交換 $a, b$ 的正負號。

不會有其他的解。

:::

等價的部分就是剛剛證明的。而唯一性的部分，假定這個解除了 $a, b$ 之外，還有 $c, d \in \Bbb Z$。也就是：

$$
p = c^2 + d^2
$$

那麼 $p$ 放到 $\Bbb Z[i]$ 時，就會有以下的分解：

$$
p = (c + di)(c - di)
$$

但另外一方面，$p = a^2 + b^2$ 也會給出另外一個分解：

$$
p = a^2 + b^2 = (a + bi)(a - bi)
$$

可以觀察：$a\pm bi$ 與 $c\pm di$ 都是 *irreducible*，因為他們的 *norm* 都是質數。比如說：

$$
N(c + di) = p \Rightarrow c + di \text{ irreducible}
$$

既然 $\Bbb Z[i]$ 是一個 *Euclidean Domain*，那麼他也要是一個 *UFD*。再加上 $(a \pm bi)$ 與 $(c \pm di)$ *irreducible*。所以下面這兩個 $p$ 的分解，每一項之間頂多只差一個 *unit*：

$$
(c + di)(c - di) = (a + bi)(a - bi)
$$

也就是：

$$
(c + di) = u (a + bi) \text{ or } u(a - bi)
$$

而 $\Bbb Z[i]$ 中，一個數字是 *unit* 等價於他的 *norm* 是 $1$，所以只可能有 $1, -1, i, -i$ 這四種可能。所以 $(c + di)$ 只可能是下面 $4$ 種的其中一個：

$$
c + di = (a + bi), (-a-bi), (ai-b), (-ai + b)
$$

因此就證明了唯一性。