107 國安局特考三等 數理組(選試英文) 數論 考古題詳解

核心觀念

1. 直角三角形內切圓半徑公式： 設直角三角形兩股長為 $a, b$，斜邊長為 $c$，內切圓半徑為 $r$。由切線長性質（或三角形面積公式），內切圓半徑滿足： $r = \frac{a + b - c}{2}$
2. 整數的同餘與奇偶性（Parity）： 對任意整數 $x$，其平方與其本身具有相同的奇偶性，即： $x^2 \equiv x \pmod 2$
3. 畢氏三元數（Pythagorean Triples）性質： 整數滿足 $a^2 + b^2 = c^2$。要證明 $r$ 為整數，等價於證明 $a + b - c$ 為偶數，即： $a + b - c \equiv 0 \pmod 2$

---

解題方法

本題可採用「同餘奇偶性分析」直接推導，亦可藉由「畢氏三元數參數式」進行驗證。以下提供標準證明與參數化另解：

【方法一：幾何關係配合同餘奇偶性（標準解法）】

步驟一：推導直角三角形內切圓半徑之代數關係 設直角三角形 $ABC$ 中，$\angle C = 90^\circ$，$BC = a$，$AC = b$，$AB = c$。 設內切圓圓心為 $I$，內切圓與三邊之切點分別為 $D, E, F$。由圓外一點到圓之兩切線段等長：

• 由直角頂點 $C$ 所作的切線段長為 $r$（四邊形 $CDIE$ 為邊長為 $r$ 的正方形）。
• 因此，兩股在另一端的切線段長分別為 $a - r$ 與 $b - r$。
• 斜邊長 $c$ 等於此兩切線段長之和： $c = (a - r) + (b - r) = a + b - 2r$ 移項整理得： $2r = a + b - c \implies r = \frac{a + b - c}{2}$

步驟二：利用模 2 同餘證明 $a + b - c$ 恆為偶數 已知 $a, b, c$ 均為正整數，且滿足畢氏定理 $a^2 + b^2 = c^2$。 由於任意整數與其平方之差必為偶數： $x^2 - x = x(x - 1) \equiv 0 \pmod 2 \implies x^2 \equiv x \pmod 2$ 將此同餘性質應用於 $a, b, c$： $a^2 \equiv a \pmod 2, \quad b^2 \equiv b \pmod 2, \quad c^2 \equiv c \pmod 2$ 代入 $c^2 = a^2 + b^2$ 的同餘關係式中： $c \equiv c^2 = a^2 + b^2 \equiv a + b \pmod 2$ 兩邊同減 $c$，得： $a + b - c \equiv 0 \pmod 2$ 這說明 $a + b - c$ 恆為偶數（即存在整數 $k$ 使得 $a + b - c = 2k$）。

步驟三：結論 由步驟一與步驟二可知： $r = \frac{a + b - c}{2} \in \mathbb{Z}$ 又由三角形邊長關係（兩邊之和大於第三邊）可知 $a + b > c$，故 $r > 0$。 因此，畢氏三角形內接圓的半徑 $r$ 必定為正整數。

---

核心觀念

1. 雷建得符號（Legendre Symbol）： 設 $p$ 為奇質數，整數 $a$ 與 $p$ 互質。定義：

$$\left(\frac{a}{p}\right) = \begin{cases} 1, & \text{若 } a \text{ 是模 } p \text{ 的二次剩餘（Quadratic Residue）}， \\ -1, & \text{若 } a \text{ 是模 } p \text{ 的二次非剩餘（Quadratic Nonresidue）}。 \end{cases}$$

2. 高斯引理（Gauss's Lemma）： 設 $p$ 為奇質數，$\gcd(a, p) = 1$。考慮整數集合

$$S = \left\{ a, 2a, 3a, \dots, \left(\frac{p-1}{2}\right)a \right\}$$

將 $S$ 中的每個元素除以 $p$ 取「最小正剩餘」（即落在區間 $\{1, 2, \dots, p-1\}$ 內的餘數）。若這些餘數中落在區間 $\left( \frac{p}{2}, p-1 \right]$ 的個數為 $n$，則

$$\left(\frac{a}{p}\right) = (-1)^n$$

3. 模 8 同餘系與二項式奇偶性： 任意奇質數 $p$ 必同餘於 $1, 3, 5, 7 \pmod 8$ 其一，可藉由代入分析代數式 $\frac{p^2-1}{8}$ 之奇偶性。

---

解題方法

本題採用**高斯引理（Gauss's Lemma）**進行標準推導。

步驟一：建立高斯引理中的檢驗集合

令 $a = 2$，考慮集合

$$S = \left\{ 1 \cdot 2, 2 \cdot 2, 3 \cdot 2, \dots, \left(\frac{p-1}{2}\right) \cdot 2 \right\}$$

由於集合中最大元素為 $2 \cdot \frac{p-1}{2} = p - 1 < p$，故 $S$ 中所有元素本身即為模 $p$ 的最小正剩餘，無需額外減去 $p$ 的倍數。

步驟二：計算大於 $\frac{p}{2}$ 的元素個數 $n$

欲求元素 $2k \in S$ 滿足 $2k > \frac{p}{2}$ 的個數，其中 $1 \le k \le \frac{p-1}{2}$：

$$2k > \frac{p}{2} \iff k > \frac{p}{4}$$

因此，滿足條件的整數 $k$ 之範圍為：

$$\left\lfloor \frac{p}{4} \right\rfloor + 1 \le k \le \frac{p-1}{2}$$

滿足條件的元素個數 $n$ 為：

$$n = \frac{p-1}{2} - \left\lfloor \frac{p}{4} \right\rfloor$$

步驟三：按 $p \pmod 8$ 分類討論 $n$ 與 $\frac{p^2-1}{8}$ 的奇偶性

任何奇質數 $p$ 均可表示為 $8k + r$，其中 $r \in \{1, 3, 5, 7\}$，分別計算 $n$ 與 $\frac{p^2-1}{8}$：

1. 若 $p \equiv 1 \pmod 8$，設 $p = 8k + 1$：

$$n = \frac{(8k+1)-1}{2} - \left\lfloor \frac{8k+1}{4} \right\rfloor = 4k - 2k = 2k \equiv 0 \pmod 2$$ $$\frac{p^2-1}{8} = \frac{(8k+1)^2-1}{8} = \frac{64k^2 + 16k}{8} = 8k^2 + 2k \equiv 0 \pmod 2$$

此時 $n$ 與 $\frac{p^2-1}{8}$ 皆為偶數，故 $(-1)^n = (-1)^{(p^2-1)/8} = 1$。

2. 若 $p \equiv 3 \pmod 8$，設 $p = 8k + 3$：

$$n = \frac{(8k+3)-1}{2} - \left\lfloor \frac{8k+3}{4} \right\rfloor = (4k+1) - 2k = 2k + 1 \equiv 1 \pmod 2$$ $$\frac{p^2-1}{8} = \frac{(8k+3)^2-1}{8} = \frac{64k^2 + 48k + 8}{8} = 8k^2 + 6k + 1 \equiv 1 \pmod 2$$

此時 $n$ 與 $\frac{p^2-1}{8}$ 皆為奇數，故 $(-1)^n = (-1)^{(p^2-1)/8} = -1$。

3. 若 $p \equiv 5 \pmod 8$，設 $p = 8k + 5$：

$$n = \frac{(8k+5)-1}{2} - \left\lfloor \frac{8k+5}{4} \right\rfloor = (4k+2) - (2k+1) = 2k + 1 \equiv 1 \pmod 2$$

核心觀念

1. 歐幾里得輾轉相除法（Euclidean Algorithm）與貝祖定理（Bézout's Identity）： 對任意兩整數 $a, b$，其最大公因數 $\gcd(a, b)$ 必可表為兩數的整數線性組合，即存在整數 $x, y$ 使得： $a x + b y = \gcd(a, b)$ 透過輾轉相除法記錄每一步的商與餘數，再由最後一個非零餘數反向代換（擴展歐幾里得演算法，Extended Euclidean Algorithm），即可求得一組整數解 $(x, y)$。

2. 四平方和定理（Lagrange's Four-Square Theorem）與不定方程整數解： 每一個正整數皆可表示為四個整數的平方和。本題特別限制 $k, l, m, n$ 必須為正整數（即 $k, l, m, n \ge 1$），可採用「最大平方數逼近夾擠法」或「題幹因數關聯法」進行有效分解。

---

解題方法

第 (一) 小題：求 $\gcd(12378, 3054)$ 及其線性組合

步驟一：正向執行輾轉相除法 計算 $12378$ 與 $3054$ 的除法算式：

$$\begin{aligned} 12378 &= 3054 \times 4 + 162 \quad &\cdots (1) \\ 3054 &= 162 \times 18 + 138 \quad &\cdots (2) \\ 162 &= 138 \times 1 + 24 \quad &\cdots (3) \\ 138 &= 24 \times 5 + 18 \quad &\cdots (4) \\ 24 &= 18 \times 1 + 6 \quad &\cdots (5) \\ 18 &= 6 \times 3 + 0 \quad &\cdots (6) \end{aligned}$$

最後一個非零餘數為 $6$，故： $\gcd(12378, 3054) = 6$

步驟二：逆向回推求線性組合（擴展歐幾里得演算法） 由式 $(5)$ 開始逐步向上代入消去各階餘數： 由 $(5)$ 得： $6 = 24 - 18 \times 1$

將式 $(4)$ 之 $18 = 138 - 24 \times 5$ 代入： $6 = 24 - (138 - 24 \times 5) \times 1 = 24 \times 6 - 138 \times 1$

將式 $(3)$ 之 $24 = 162 - 138 \times 1$ 代入： $6 = (162 - 138 \times 1) \times 6 - 138 \times 1 = 162 \times 6 - 138 \times 7$

將式 $(2)$ 之 $138 = 3054 - 162 \times 18$ 代入： $6 = 162 \times 6 - (3054 - 162 \times 18) \times 7 = 162 \times 132 - 3054 \times 7$

將式 $(1)$ 之 $162 = 12378 - 3054 \times 4$ 代入： $6 = (12378 - 3054 \times 4) \times 132 - 3054 \times 7 = 12378 \times 132 - 3054 \times (4 \times 132 + 7)$ $6 = 12378 \times 132 - 3054 \times 535$

改寫為標準線性組合形式： $\gcd(12378, 3054) = 12378 \times (132) + 3054 \times (-535)$

其通解形式為（$t \in \mathbb{Z}$）： $\gcd(12378, 3054) = 12378 \times (132 + 509t) + 3054 \times (-535 - 2063t)$

---

第 (二) 小題：求正整數 $k, l, m, n$ 滿足 $k^2+l^2+m^2+n^2=9828$

本題提供兩種解題切入途徑：

核心觀念

本題包含兩個數論基礎而經典的子題：

1. 同餘運算與代數分解： 證明整除性 $a \mid (b^n - 1)$，本質上即證明同餘式 $b^n \equiv 1 \pmod a$。可利用同餘的乘冪性質，或是利用代數恆等式中的平方差公式 $A^2 - B^2 = (A - B)(A + B)$ 進行因式分解，尋找 $a$ 的倍數。
2. 費馬因數分解法（Fermat's Factorization Method）： 適用於分解奇合數 $N$。核心思想是將 $N$ 表示為兩個平方數的差： $N = x^2 - y^2 = (x - y)(x + y)$ 此時 $x - y$ 與 $x + y$ 即為 $N$ 的非平凡因數。

• 搜尋起點：取 $x = \lceil \sqrt{N} \rceil$。
• 判定條件：檢驗 $x^2 - N$ 是否為完全平方數 $y^2$。若否，則遞增 $x$（即 $x \leftarrow x + 1$）繼續檢驗，直到找到完全平方數為止。

---

解題方法

(一) 證明 $41$ 可以整除 $2^{20}-1$

本題提供兩種嚴謹的解題切入點，考場上任選其一即可獲得滿分：

方法一：同餘綜合法（推薦）

欲證 $41 \mid (2^{20} - 1)$，等價於證明 $2^{20} \equiv 1 \pmod{41}$。

1. 計算 $2$ 的冪次模 $41$： $2^5 = 32 \equiv -9 \pmod{41}$
2. 兩邊平方： $2^{10} = (2^5)^2 \equiv (-9)^2 = 81 \pmod{41}$ 因為 $81 = 41 \times 2 - 1$，所以： $2^{10} \equiv -1 \pmod{41}$
3. 再次兩邊平方： $2^{20} = (2^{10})^2 \equiv (-1)^2 = 1 \pmod{41}$
4. 移項即得： $2^{20} - 1 \equiv 0 \pmod{41}$ 故 $41 \mid (2^{20} - 1)$ 得證。

方法二：代數因式分解法

利用代數平方差公式展開： $2^{20} - 1 = (2^{10} + 1)(2^{10} - 1)$ 計算 $2^{10}$ 的數值： $2^{10} = 1024$ 因此： $2^{10} + 1 = 1025$ 將 $1025$ 除以 $41$： $1025 = 41 \times 25$ 因為 $41 \mid (2^{10} + 1)$，而 $2^{10} + 1$ 是 $2^{20} - 1$ 的因數，所以 $41 \mid (2^{20} - 1)$ 得證。

---

(二) 運用 Fermat 的方法因式分解數字 $119143$

設 $N = 119143$。

步驟一：確定搜尋起點 $x_0$

先估算 $\sqrt{N}$ 的範圍： $345^2 = 119025 < 119143 < 346^2 = 119716$ 因此 $x$ 的最小可能整數值為： $x = \lceil \sqrt{119143} \rceil = 346$

步驟二：依序檢驗 $x^2 - N$ 是否為完全平方數

利用連續平方數差的遞推關係簡化計算：$(x + 1)^2 - N = (x^2 - N) + (2x + 1)$。

1. 當 $x = 346$： $346^2 - 119143 = 119716 - 119143 = 573$ 檢驗：$23^2 = 529 < 573 < 576 = 24^2$，非完全平方數。

2. 當 $x = 347$： $347^2 - 119143 = 573 + (2 \times 346 + 1) = 573 + 693 = 1266$ 檢驗：$1266 \equiv 2 \pmod 4$，非完全平方數（完全平方數模 4 必為 0 或 1）。

核心觀念

本題的核心在於求解與探討非平方正整數 $d$ 之佩爾方程式（Pell's Equation）：

$$x^2-dy^2=1$$

解答本題需掌握以下核心定義與數論性質：

1. 原始解（Fundamental Solution）： 在所有滿足 $x^2-dy^2=1$ 的正整數解 $(x, y) \in \mathbb{Z}^+ \times \mathbb{Z}^+$ 中，使數值 $x+y\sqrt{d}$ 達到最小的解 $(x_1, y_1)$，稱為該佩爾方程式的「原始解」（或基本解）。由實數大小關係可知，此極小性亦等價於 $x_1$ 或 $y_1$ 為正整數解中的最小值。
2. 二次域的範數（Norm）與乘法性： 在環 $\mathbb{Z}[\sqrt{d}] = \{x+y\sqrt{d} \mid x,y\in\mathbb{Z}\}$ 中，定義元素 $\alpha = x+y\sqrt{d}$ 的共軛元素為 $\bar{\alpha} = x-y\sqrt{d}$，其範數為：

$$N(\alpha) = \alpha \bar{\alpha} = (x+y\sqrt{d})(x-y\sqrt{d}) = x^2-dy^2$$

範數具備乘法保距性，即對任意 $\alpha, \beta \in \mathbb{Z}[\sqrt{d}]$，恆有 $N(\alpha\beta) = N(\alpha)N(\beta)$。 3. 解結構的完備性論證： 欲證明「所有」正整數解皆能表示為 $(x_1+y_1\sqrt{d})^n$，必須證明兩件事：

• 充分性（Existence）：由式子展開生成的每一組 $(x_n, y_n)$ 確實皆為正整數解。
• 必要性／完備性（Completeness）：不可能存在任何一組正整數解遺漏在此生成數列之外（利用原始解的極小性進行反證）。

---

解題方法

證明分為兩大部分：第一部分證明以該式定義的 $(x_n, y_n)$ 均為方程式的正整數解；第二部分證明方程式的任意正整數解均可由該式表示。

第一部分：驗證由式子生成的 $(x_n, y_n)$ 皆為正整數解（充分性）

設 $(x_1, y_1)$ 為佩爾方程式的原始解，故 $x_1, y_1 \in \mathbb{Z}^+$ 且滿足 $x_1^2-dy_1^2=1$。 對任意給定的正整數 $n \in \{1, 2, 3, \ldots\}$，考慮：

$$x_n+y_n\sqrt{d}=(x_1+y_1\sqrt{d})^n$$

1. 整數性與正值性： 由二項式定理展開：

$$(x_1+y_1\sqrt{d})^n = \sum_{k=0}^{n} \binom{n}{k} x_1^{n-k} (y_1\sqrt{d})^k$$

將偶數項（不含 $\sqrt{d}$）與奇數項（含 $\sqrt{d}$）分開整理：

$$x_n = \sum_{k \text{ 為偶數}} \binom{n}{k} x_1^{n-k} y_1^k d^{k/2}, \qquad y_n = \sum_{k \text{ 為奇數}} \binom{n}{k} x_1^{n-k} y_1^k d^{(k-1)/2}$$

因為 $x_1, y_1, d \in \mathbb{Z}^+$，所以 $x_n, y_n$ 顯然為整數，且所有各項均為正，故 $x_n > 0$ 且 $y_n > 0$。

2. 滿足佩爾方程式： 對其取代數共軛（或利用自同構性質），可得：

$$x_n-y_n\sqrt{d}=(x_1-y_1\sqrt{d})^n$$

將兩式相乘，利用平方差公式：

$$x_n^2-dy_n^2 = (x_n+y_n\sqrt{d})(x_n-y_n\sqrt{d}) = \left[(x_1+y_1\sqrt{d})(x_1-y_1\sqrt{d})\right]^n = (x_1^2-dy_1^2)^n$$

已知 $x_1^2-dy_1^2=1$，故：

$$x_n^2-dy_n^2 = 1^n = 1$$

因此，對所有 $n \ge 1$，$(x_n, y_n)$ 確實為 $x^2-dy^2=1$ 的正整數解。

---

第二部分：證明方程式的所有正整數解皆由此形式產生（完備性）

設 $(u, v)$ 為 $x^2-dy^2=1$ 的任一組正整數解，則 $u, v \in \mathbb{Z}^+$ 且 $u^2-dv^2=1$。 由於 $u, v \ge 1$ 且 $d \ge 2$，必有 $u+v\sqrt{d} > 1$。 同理，原始解滿足 $x_1+y_1\sqrt{d} > 1$。

考慮數列 $\{(x_1+y_1\sqrt{d})^k\}_{k=1}^{\infty}$，這是一個嚴格遞增且趨向無窮大的幾何級數：

$$1 < x_1+y_1\sqrt{d} < (x_1+y_1\sqrt{d})^2 < (x_1+y_1\sqrt{d})^3 < \cdots$$

因為 $u+v\sqrt{d} \ge x_1+y_1\sqrt{d}$（依原始解之定義），由實數的阿基米德性質，必存在一個唯一的正整數 $m \ge 1$，使得：

$$(x_1+y_1\sqrt{d})^m \le u+v\sqrt{d} < (x_1+y_1\sqrt{d})^{m+1}$$

欲證 $u+v\sqrt{d} = (x_1+y_1\sqrt{d})^m$。我們採用反證法： 假設嚴格不等式成立，即：

$$(x_1+y_1\sqrt{d})^m < u+v\sqrt{d} < (x_1+y_1\sqrt{d})^{m+1}$$