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

核心觀念

本題考查多項式係數和與奇次項係數和的關係。

設

$$f(x)=c_0+c_1x+c_2x^2+\cdots+c_nx^n。$$

則：

• 各項係數總和為 $f(1)=c_0+c_1+\cdots+c_n。$
• 偶次項係數和與奇次項係數和之差為 $f(-1)=c_0-c_1+c_2-c_3+\cdots。$

因此，奇次項係數總和為

$$\frac{f(1)-f(-1)}{2}。$$

解題方法

令

$$g(x)=2x^3-3x^2+x+a，$$

則

$$f(x)=\bigl(g(x)\bigr)^3。$$

第一步：利用各項係數總和求 $a$

題目已知 $f(x)$ 展開式的各項係數總和為 $8$，因此

$$f(1)=8。$$

計算 $f(1)$：

$$f(1)=\left(2(1)^3-3(1)^2+1+a\right)^3。$$

化簡得

$$f(1)=(2-3+1+a)^3=a^3。$$

所以

$$a^3=8，$$

得到

$$a=2。$$

第二步：計算 $f(-1)$

代入 $a=2$：

核心觀念

本題考查「多項式整除」與「多項式除法的餘式判定」。

若多項式 $f(x)$ 能整除多項式 $P(x)$，則將 $P(x)$ 除以 $f(x)$ 所得的餘式必須為零。由於除式為

$$x^2+x+2,$$

因此在計算餘式時，可利用

$$x^2+x+2=0 \quad\Longrightarrow\quad x^2\equiv -x-2.$$

只要將高次冪降為一次式，再令餘式的各項係數均為 $0$，即可求出 $p,q$。

解題方法

令

$$P(x)=x^5+x^4+x^3+px^2+2x+q.$$

在模 $x^2+x+2$ 下，有

$$x^2\equiv -x-2.$$

依此計算各次冪：

計算 $x^3$

$$x^3=x\cdot x^2 \equiv x(-x-2) =-x^2-2x.$$

再代入 $x^2\equiv -x-2$：

$$x^3\equiv -(-x-2)-2x =2-x.$$

計算 $x^4$

$$x^4=x\cdot x^3 \equiv x(2-x) =2x-x^2.$$

因此

$$x^4\equiv 2x-(-x-2) =3x+2.$$

計算 $x^5$

$$x^5=x\cdot x^4 \equiv x(3x+2) =3x^2+2x.$$

因此

$$x^5\equiv 3(-x-2)+2x =-x-6.$$

求 $P(x)$ 的餘式

將上述結果代入 $P(x)$：

核心觀念

本題考查以下數論觀念：

1. 模 $p$ 的同餘運算與乘法逆元。
2. 多項式 $x^2+x+1$ 與分解式 $x^3-1=(x-1)(x^2+x+1)$ 的關係。
3. 質數 $p=3k+2$ 滿足 $p\equiv 2\pmod 3,$ 因此 $p-1\equiv 1\pmod 3,$ 不被 $3$ 整除。

目標是證明：若 $p\mid a^2+ab+b^2,$ 則必有 $p\mid a,\qquad p\mid b.$

---

解題方法

先處理 $b$ 是否被 $p$ 整除，再利用模 $p$ 的乘法逆元將二次式化為一元方程。

第一步：證明 $p\mid b$

假設反證 $p\nmid b$。由於 $p$ 是質數，$b$ 在模 $p$ 下具有乘法逆元，記為 $b^{-1}$。

由題設 $a^2+ab+b^2\equiv 0\pmod p.$

兩邊同乘以 $b^{-2}$，令 $x\equiv ab^{-1}\pmod p,$ 可得 $x^2+x+1\equiv 0\pmod p.$

因此 $x^3-1=(x-1)(x^2+x+1)\equiv 0\pmod p,$ 所以 $x^3\equiv 1\pmod p.$

若 $x\equiv 1\pmod p$，則代入 $x^2+x+1\equiv 0\pmod p$ 得到 $3\equiv 0\pmod p,$ 這表示 $p=3$，但題設 $p=3k+2$，故 $p\neq 3$，矛盾。

所以 $x\not\equiv 1\pmod p.$

另一方面，$x\not\equiv 0\pmod p$，因為若 $x\equiv0\pmod p$，則 $x^2+x+1\equiv1\not\equiv0\pmod p.$

故 $x$ 是模 $p$ 的非零元素，且 $x^3\equiv1\pmod p$，但 $x\not\equiv1\pmod p$。因此 $x$ 的乘法階為 $3$，依費馬小定理或有限乘法群的性質，必有 $3\mid p-1.$

核心觀念

本題考查「整數除法與同餘」：

對整數 $a$ 除以正整數 $b$，可表示為

$$a=bq+r,\qquad 0\le r<b,$$

其中 $q$ 為商，$r$ 為餘數。

本題要求計算

$$258000\div 7$$

所得的餘數。

解題方法

直接進行整數除法：

$$258000=7\times 36857+1$$

因為

$$7\times 36857=257999,$$

所以

$$258000-257999=1.$$

且餘數 $1$ 符合 $0\le 1<7$，因此 $258000$ 除以 $7$ 的餘數為 $1$。

亦可用同餘觀念快速計算：

$$258000=258\times 1000.$$

分別計算模 $7$ 的餘數：

核心觀念

本題考查 RSA 加密中的模冪運算。RSA 公開金鑰加密公式為

$$C\equiv M^e\pmod N,$$

其中：

• $M$：明文，本題為 $12$
• $e$：公開加密指數，本題為 $7$
• $N=pq=55$
• $C$：密文，本題要求出的 $X$

因此本題須計算

$$X\equiv 12^7\pmod{55}.$$

解題方法：平方乘法

直接計算 $12^7$ 數值較大，採用平方乘法可簡化運算。

先計算平方：

$$12^2=144\equiv 34\pmod{55},$$

因為

$$144-2\cdot55=34.$$

再計算四次方：

$$12^4\equiv 34^2=1156\pmod{55}.$$

由於

$$1156=21\cdot55+1,$$

所以

$$12^4\equiv 1\pmod{55}.$$

將 $12^7$ 分解為

$$12^7=12^4\cdot12^2\cdot12.$$

代入上述結果：

核心觀念

求 $3 \bmod 20$ 的乘法逆元，就是尋找整數 $x$，使得

$$3x \equiv 1 \pmod{20}.$$

乘法逆元存在的條件為

$$\gcd(3,20)=1.$$

因為 $\gcd(3,20)=1$，所以 $3$ 在模 $20$ 下具有乘法逆元。

解題方法

使用輾轉相除法：

$$20=6\cdot 3+2,$$ $$3=1\cdot 2+1.$$

將 $1$ 反向表示為 $3$ 與 $20$ 的線性組合：

$$1=3-2$$ $$=3-(20-6\cdot 3)$$ $$=7\cdot 3-20.$$

因此，

核心觀念

梅森數定義為

$$M_p=2^p-1。$$

若 $M_p$ 本身為質數，則稱為梅森質數（Mersenne prime）。其中指數 $p$ 必須是質數；若 $p$ 為合成數，則

$$2^{ab}-1=(2^a)^b-1$$

可利用 $x^b-1$ 的因式分解判定為合成數。因此本題先確認 $7$、$11$ 均為質數，再檢查 $M_7$ 與 $M_{11}$ 是否為質數。

---

一、驗證 $M_7$

1. 計算梅森數

$$M_7=2^7-1=128-1=127。$$

2. 判斷 $127$ 是否為質數

只需檢查不超過 $\sqrt{127}$ 的質數因數。因為

$$11^2=121<127<144=12^2，$$

所以

$$\sqrt{127}<12。$$

小於 $\sqrt{127}$ 的質數只有 $2,3,5,7,11$。

逐一檢查：

• $127$ 為奇數，不被 $2$ 整除。
• 數字和為 $1+2+7=10$，不被 $3$ 整除。
• 個位數不是 $0$ 或 $5$，不被 $5$ 整除。
• $127=7\cdot18+1,$ 不被 $7$ 整除。
• $127=11\cdot11+6,$ 不被 $11$ 整除。

因此 $127$ 沒有任何小於或等於 $\sqrt{127}$ 的質因數，所以 $127$ 為質數。

故

$$\boxed{M_7=127\text{ 為梅森質數}}。$$

---

二、驗證 $M_{11}$

1. 計算梅森數

$$M_{11}=2^{11}-1=2048-1=2047。$$

2. 尋找因數

可直接發現

$$2047=23\cdot89。$$

驗算如下：

核心觀念

本題考查模質數下的二次同餘方程，以及「二次剩餘」的判定。

對整數 $a$ 與正整數 $m$，若存在整數 $x$ 使

$$x^2\equiv a\pmod m,$$

則稱 $a$ 是模 $m$ 的二次剩餘；否則稱為二次非剩餘。

本題需判斷 $13$ 是否為模 $101$ 的二次剩餘。因為 $101$ 是質數，若找到一個整數 $x$ 滿足同餘式，即可確定方程有整數解。

解題方法

直接尋找一個平方數，使其除以 $101$ 的餘數為 $13$。

觀察

$$35^2=1225.$$

而

$$1225=12\cdot101+13.$$

因此

$$35^2\equiv13\pmod{101}.$$

令 $X=35$，即得到

$$X^2\equiv13\pmod{101}.$$

所以此二次同餘方程確實有整數解。

由於

$$(-35)^2=35^2,$$

另一個模 $101$ 的解為

$$X\equiv-35\equiv66\pmod{101}.$$

因此全部解為

$$\boxed{X\equiv35,\ 66\pmod{101}}.$$

以勒讓德符號驗證

也可利用二次互反律判斷：

$$\left(\frac{13}{101}\right).$$

因為 $13\equiv1\pmod4$，由二次互反律，

$$\left(\frac{13}{101}\right) = \left(\frac{101}{13}\right).$$

又因為

$$101\equiv10\pmod{13},$$

所以