92 - 數論

試題查詢 http://www1c.moex.gov.tw/main/exam/wFrmExamQandASearch.aspx?menu_id=156

一、設 $p$ 是質數，$a$、$b$ 是整數，如果 $\frac{a^p-b^p}{p}$ 是整數，證明 $\frac{a^p-b^p}{p^2}$ 也是整數。

二、設 $x,y,z$ 是整數。如果 $x^3+y^3=z^3$ 是整數，證明這三個數中必有一個是 $7$ 的倍數。

三、證明 $1001!$ (階乘) 以 $249$ 個零為結尾。

四、證明對所有整數 $x,y$，$\frac{x^2+y^2-3}{4}$ 不是整數。

---

解題

一、
Case 1：若 $a$ 和 $b$ 都是 $p$ 的倍數。令 $a=pa_1$，$b=pb_1$，$a_1$、$b_1$ 為整數，則 $$a^p-b^p=(pa_1)^p-(pb_1)^p=p^p(a_1^p-b_1^p)\equiv 0\mbox{ (mod $p$)}$$因為 $p\geq 2$，所以 $p^p(a_1^p-b_1^p)\equiv 0(\mbox{mod $p^2$})$。

Case 2：若 $a,b$ 有一數不是 $p$ 的倍數，不失一般性，設 $p\mid a$ 但 $p\nmid b$。令 $a=pa_1$，$b=pb_1+r$，其中 $r$ 是介於 $1$ 和 $p-1$ 的整數。則$$a^p-b^p=(pa_1)^p-(pb_1+r)^p\equiv r^p\not\equiv 0 \mbox{ (mod $p$)}$$所以不存在整數 $a,b$ 滿足 $\frac{a^p-b^p}{p}$。

Case 3：若 $a,b$ 都不是 $p$ 的倍數。因為 $(a,p)=(b,p)=1$，根據費馬小定理，有 $a^p\equiv a\mbox{ (mod $p$)}$ 及 $b^p\equiv b\mbox{ (mod $p$)}$。所以$$a^p-b^p\equiv a-b\equiv 0\mbox{ (mod $p$)}$$對 $a^p-b^p$ 做因式分解$$
\begin{aligned}
a^p-b^p &= (a-b)(a^{p-1}+a^{p-2}b+\cdots ab^{p-2}+b^{p-1})  \\
&\equiv a^{p-1}+a^{p-2}b+\cdots +ab^{p-2}+b^{p-1}\mbox{ (mod $p$)}
\end{aligned}
$$現在要證明 $a^{p-1}+a^{p-2}b+\cdots +ab^{p-2}+b^{p-1}$ 能被 $p$ 整除。因為 $a-b\equiv 0\mbox{ (mod $p$)}$，設 $a=pt+b$，其中 $t$ 是整數。則$$\begin{aligned}
a^{p-1}+a^{p-2}b+\cdots ab^{p-2}+b^{p-1} &=(pt+b)^{p-1}+(pt+b)^{p-2}b+\cdots +(pt+b)b^{p-2}+b^{p-1} \\
&=\left \{ \left [ \sum_{i=0}^{p-2}\binom{p-1}{i}(pt)^{p-1-i}\cdot b^i \right ]+b^{p-1} \right \}+
\left \{ \left [ \sum_{i=0}^{p-3}\binom{p-2}{i}(pt)^{p-2-i}\cdot b^i \right ]+b^{p-2} \right \}b+\cdots +(pt+b)b^{p-2}+b^{p-1} \\
&\equiv b^{p-1}+b^{p-2}\cdot b+\cdots b\cdot b^{p-2}+b^{p-1}\equiv p\cdot b^{p-1}\equiv 0\mbox{ (mod $p$)}
\end{aligned}
$$故原命題成立。

---

二、
模 $7$ 的完全剩餘系 $\left \{ -3,-2,-1,0,1,2,3 \right \}$，對每一元素取三次方、再除以 $7$，得到 $\left \{-1,0,1  \right \}$。把 $x^3+y^3$ 除以 $7$ 的所有可能情況列出如下：$$x^3+y^3\equiv \left\{\begin{matrix}
\begin{aligned}
(-1)+(-1)&\equiv 0\\
-1+0&\equiv -1\\
-1+1&\equiv 0\\
0+(-1)&\equiv 0\\
0+0&\equiv 0\\
0+1&\equiv 0\\
1+(-1)&\equiv 0\\
1+0&\equiv 1\\
1+1&\equiv 2
\end{aligned}
\end{matrix}\right.\mbox{ (mod $7$)}$$除了最後一條同餘式不合之外，其餘八條式子都有 $0$ 的存在，所以 $x,y,z$ 中必有一數是 $7$ 的倍數。

---

三、
對於一數 $a$，若要在 $a$ 後面加一個零，我們會將 $a$ 乘以 $10$，這樣 $a$ 的尾數就多了一個零。而 $10=2\times 5$，換句話說，要算一個數的尾數有多少個零，我們只要算該數有多少個 $2$ 及 多少個 $5$ 組成，然後取兩者個數中的較小者，這樣就知道該數的尾數有幾個零了。

我們要算 $1001!$ 的質因數分解式裡、$2$ 的次方及 $5$ 次方為何。
$\left \lfloor \frac{1001}{2} \right \rfloor+\left \lfloor \frac{1001}{2^2} \right \rfloor+\left \lfloor \frac{1001}{2^3} \right \rfloor+\left \lfloor \frac{1001}{2^4} \right \rfloor+\left \lfloor \frac{1001}{2^5} \right \rfloor+\left \lfloor \frac{1001}{2^6} \right \rfloor+\left \lfloor \frac{1001}{2^7} \right \rfloor+\left \lfloor \frac{1001}{2^8} \right \rfloor+\left \lfloor \frac{1001}{2^9} \right \rfloor=500+250+125+62+31+15+7+3+1=994$

$\left \lfloor \frac{1001}{5} \right \rfloor+\left \lfloor \frac{1001}{5^2} \right \rfloor+\left \lfloor \frac{1001}{5^3} \right \rfloor+\left \lfloor \frac{1001}{5^4} \right \rfloor=200+40+8+1=249$

故 $1001!$ 的質因數乘積中，有 $994$ 個 $2$、$249$ 個 $5$，$\mbox{min{$994$,$249$}}=249$，所以 $1001!$ 的結尾有 $249$ 個零。

---

四、
對於模 $4$ 的完全剩餘系 ${-1,0,1,2}$，平方後除以 $4$，得到 ${0,1}$。所有 $x^2+y^2$ 模 $4$ 的可能值為 $0,1,2$ 三種，故 $x^2+y^2\equiv 0\mbox{ ,1 or 2}\not\equiv 3\mbox{ (mod $4$)}$，即 $\frac{x^2+y^2-3}{4}$ 不是整數。