試題查詢 http://www1c.moex.gov.tw/main/exam/wFrmExamQandASearch.aspx?menu_id=156
一、
（一）$x=10+35t$, where $t$ is an integer.
（二）$x=10+1190k$, where $k$ is an integer.
二、
$(u,v)=(30,34)$
三、
因為 $(3,13)=1$，根據費馬小定理，有 $3^{12}\equiv 1\mbox{ (mod $13$)}$。所以 $3^{19}\equiv 3^7 \equiv (3^3)^2\cdot 3\equiv 3\mbox{ (mod $13$)}$。
原式 $u^2\equiv 3^{19}\equiv 3\mbox{ (mod $13$)}$，此乃二次同餘式。易知 $u\equiv 4,9\mbox{ (mod $13$)}$。因為 $1\leq u\leq 12$，所以有 $u=4$ 及 $u=9$ 兩解。
當 $u=4$，$i^u=i^4=1$；當 $u=9$，$i^u=i^9=i=\sqrt{-1}$。
四、
因為 $p$ 是質數，所以存在原根。設 $y$ 是模 $p$ 之原根，則有 $y^{p-1}\equiv 1\mbox{ (mod $p$)}$。
用反證法。假設 $(p-1)\nmid (v-1)$，則 $y^{v-1}\not\equiv 1\mbox{ (mod $p$)}$。因為 $p|v$，所以 $y^{v-1}\not\equiv 1\mbox{ (mod $v$)}$，或寫為 $y^v\not\equiv y\mbox{ (mod $v$)}$，與題目所設條件矛盾！故 $(p-1)\mid (v-1)$。
五、
對於tobeornottobe，$D=292411142427232429241114=\underset{u}{\underbrace{2924111424272}}\times 10^{13}+\underset{v}{\underbrace{3242929241114}}$
對於yes，$Y=241428$；對於not，$N=232429$
我們知道 $i^2=-1$，$i^4=1$。$\left\{\begin{matrix}
u\equiv 0\mbox{ (mod $4$}\\
v\equiv 2\mbox{ (mod $4$)}\\
Y\equiv 0\mbox{ (mod $4$)}\\
N\equiv 1\mbox{ (mod $4$)}
\end{matrix}\right.$
所以 $2i^u+i^v=2+(-1)=1=1+0i$，而 $i^Y+i^N=1+i$。
比較兩式後，只有實部相同，所以會選 yes。
2015年6月26日 星期五
100 - 數論
試題查詢 http://www1c.moex.gov.tw/main/exam/wFrmExamQandASearch.aspx?menu_id=156
一、
$\left\{\begin{matrix}
\begin{aligned}
x&=-5+11v+33r\\
y&=-1+7r\\
z&=3-5v-20r
\end{aligned}
\end{matrix}\right.\mbox{ , where $v$ and $r$ are integers.}$
四組解$\left\{\begin{matrix}
\begin{aligned}
x_0&=-5\\
y_0&=-1\\
z_0&=3
\end{aligned}
\end{matrix}\right.$、$\left\{\begin{matrix}
\begin{aligned}
x_1&=6\\
y_1&=-1\\
z_1&=-2
\end{aligned}
\end{matrix}\right.$、$\left\{\begin{matrix}
\begin{aligned}
x_2&=28\\
y_2&=6\\
z_2&=-17
\end{aligned}
\end{matrix}\right.$、$\left\{\begin{matrix}
\begin{aligned}
x_3&=39\\
y_3&=6\\
z_3&=-22
\end{aligned}
\end{matrix}\right.$
二、
$n=2^{15}\times 3^{10}\times 5^6$
三、
考慮 $(1+x)^n$ 之展開式：$$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots +\binom{n}{n}x^n$$對 $x$ 積分，積分範圍從 $-1$ 到 $0$。
將上式展開，得到$$
\begin{aligned}
\frac{1}{n+1}&=0-\left [ \binom{n}{0}(-1)+\frac{1}{2}\binom{n}{1}(-1)^2+\frac{1}{3}\binom{n}{2}(-1)^3+\cdots +\frac{1}{n+1}\binom{n}{n}(-1)^{n+1} \right ] \\
&=\binom{n}{0}-\frac{1}{2}\binom{n}{1}+\frac{1}{3}\binom{n}{2}-\cdots +\frac{(-1)^n}{n+1}\binom{n}{n}
\end{aligned}
$$
四、
解 $f(n)=n^9+n^6+n^3+1\equiv 0\mbox{ (mod $36$)}$
利用 Hensel's lemma，先算 $f(n)=n^9+n^6+n^3+1\equiv 0\mbox{ (mod $6$)}$，得到 $n=-1+6t$，其中 $t$ 是整數。將 $n=-1+6t$ 代入 $f(-1)+6tf'(-1)\equiv 0\mbox{ (mod $36$)}$，得到 $36t\equiv 0\mbox{ (mod $36$)}$，由此知 $t$ 可取任意實數，故 $n$ 即為 $-1+6t$。將 $t$ 以 $1,2,3,4,5,6$ 代入 $n=-1+6t$，得到 $n=5,11,17,25,29,35$。
五、
(一) 假設存在非負整數 $x,y$ 滿足 $ab-a-b=ax+by$。則有 $\left\{\begin{matrix}
\begin{aligned}
-b&\equiv by\mbox{ (mod $a$)}\\
-a&\equiv ax\mbox{ (mod $b$)}
\end{aligned}
\end{matrix}\right.$。因為 $(a,b)=1$，所以 $\left\{\begin{matrix}
\begin{aligned}
-1&\equiv y\mbox{ (mod $a$)}\\
-1&\equiv x\mbox{ (mod $b$)}
\end{aligned}
\end{matrix}\right.$，即 $x=bt_2-1$，$y=at_1-1$。因為 $x,y$ 都是非負整數，所以限制 $t_1,t_2$ 是正整數。
將 $x=bt_2-1$，$y=at_1-1$ 代入 $ax+by$，得到 $a(bt_2-1)+b(at_1-1)=ab(t_2+t_1)-a-b=ab-a-b$。比對係數後，得到 $t_2+t_1=0$，但是 $t_1,t_2$ 是正整數，$t_2+t_1>0$，故原假設不成立。
(二)
這個問題叫「Postage Stamp Problem」
https://math.dartmouth.edu/archive/m25f10/public_html/homework/m25hw2sol.pdf
https://crazyproject.wordpress.com/2010/10/22/solve-the-postage-stamp-problem-in-two-denominations-over-the-integers/
設整數 $d>ab-a-b$。對於 $ax+by=d$，令 $x_0,y_0$ 是 $ax+by=d$ 的一組整數解，則全解可表示為 $\left\{\begin{matrix}
x=x_0-bt\\
y=y_0+at
\end{matrix}\right.\mbox{, where $t\in \mathbb{Z}$.}$
我們總是能找到能使 $x$ 為最小非負整數的 $t$ 值（取 $t=\left \lfloor \frac{x_0}{b} \right \rfloor$ 即可 ）。當取了 $t=\left \lfloor \frac{x_0}{b} \right \rfloor$ 後，此時的 $x$ 會介於 $0$ 和 $b$ 之間，即 $0\leq x < b$，或寫成 $0\leq x \leq b-1$。
因為 $0\leq x \leq b-1$，所以有 $$d=ax+by\leq a(b-1)+by$$即$$d-a(b-1)\leq by$$因為$$d-a(b-1)>(ab-a-b)-a(b-1)=-b$$最後得到$$-b<d-a(b-1)\leq by$$即$$-b<by\mbox{, or $-1<y$}$$證明了 $y\geq 0$。所以原命題成立。
一、
$\left\{\begin{matrix}
\begin{aligned}
x&=-5+11v+33r\\
y&=-1+7r\\
z&=3-5v-20r
\end{aligned}
\end{matrix}\right.\mbox{ , where $v$ and $r$ are integers.}$
四組解$\left\{\begin{matrix}
\begin{aligned}
x_0&=-5\\
y_0&=-1\\
z_0&=3
\end{aligned}
\end{matrix}\right.$、$\left\{\begin{matrix}
\begin{aligned}
x_1&=6\\
y_1&=-1\\
z_1&=-2
\end{aligned}
\end{matrix}\right.$、$\left\{\begin{matrix}
\begin{aligned}
x_2&=28\\
y_2&=6\\
z_2&=-17
\end{aligned}
\end{matrix}\right.$、$\left\{\begin{matrix}
\begin{aligned}
x_3&=39\\
y_3&=6\\
z_3&=-22
\end{aligned}
\end{matrix}\right.$
二、
$n=2^{15}\times 3^{10}\times 5^6$
三、
考慮 $(1+x)^n$ 之展開式：$$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\cdots +\binom{n}{n}x^n$$對 $x$ 積分，積分範圍從 $-1$ 到 $0$。
將上式展開，得到$$
\begin{aligned}
\frac{1}{n+1}&=0-\left [ \binom{n}{0}(-1)+\frac{1}{2}\binom{n}{1}(-1)^2+\frac{1}{3}\binom{n}{2}(-1)^3+\cdots +\frac{1}{n+1}\binom{n}{n}(-1)^{n+1} \right ] \\
&=\binom{n}{0}-\frac{1}{2}\binom{n}{1}+\frac{1}{3}\binom{n}{2}-\cdots +\frac{(-1)^n}{n+1}\binom{n}{n}
\end{aligned}
$$
四、
解 $f(n)=n^9+n^6+n^3+1\equiv 0\mbox{ (mod $36$)}$
利用 Hensel's lemma，先算 $f(n)=n^9+n^6+n^3+1\equiv 0\mbox{ (mod $6$)}$，得到 $n=-1+6t$，其中 $t$ 是整數。將 $n=-1+6t$ 代入 $f(-1)+6tf'(-1)\equiv 0\mbox{ (mod $36$)}$，得到 $36t\equiv 0\mbox{ (mod $36$)}$，由此知 $t$ 可取任意實數，故 $n$ 即為 $-1+6t$。將 $t$ 以 $1,2,3,4,5,6$ 代入 $n=-1+6t$，得到 $n=5,11,17,25,29,35$。
五、
(一) 假設存在非負整數 $x,y$ 滿足 $ab-a-b=ax+by$。則有 $\left\{\begin{matrix}
\begin{aligned}
-b&\equiv by\mbox{ (mod $a$)}\\
-a&\equiv ax\mbox{ (mod $b$)}
\end{aligned}
\end{matrix}\right.$。因為 $(a,b)=1$，所以 $\left\{\begin{matrix}
\begin{aligned}
-1&\equiv y\mbox{ (mod $a$)}\\
-1&\equiv x\mbox{ (mod $b$)}
\end{aligned}
\end{matrix}\right.$，即 $x=bt_2-1$，$y=at_1-1$。因為 $x,y$ 都是非負整數，所以限制 $t_1,t_2$ 是正整數。
將 $x=bt_2-1$，$y=at_1-1$ 代入 $ax+by$，得到 $a(bt_2-1)+b(at_1-1)=ab(t_2+t_1)-a-b=ab-a-b$。比對係數後，得到 $t_2+t_1=0$，但是 $t_1,t_2$ 是正整數，$t_2+t_1>0$，故原假設不成立。
(二)
這個問題叫「Postage Stamp Problem」
https://math.dartmouth.edu/archive/m25f10/public_html/homework/m25hw2sol.pdf
https://crazyproject.wordpress.com/2010/10/22/solve-the-postage-stamp-problem-in-two-denominations-over-the-integers/
設整數 $d>ab-a-b$。對於 $ax+by=d$，令 $x_0,y_0$ 是 $ax+by=d$ 的一組整數解，則全解可表示為 $\left\{\begin{matrix}
x=x_0-bt\\
y=y_0+at
\end{matrix}\right.\mbox{, where $t\in \mathbb{Z}$.}$
我們總是能找到能使 $x$ 為最小非負整數的 $t$ 值（取 $t=\left \lfloor \frac{x_0}{b} \right \rfloor$ 即可 ）。當取了 $t=\left \lfloor \frac{x_0}{b} \right \rfloor$ 後，此時的 $x$ 會介於 $0$ 和 $b$ 之間，即 $0\leq x < b$，或寫成 $0\leq x \leq b-1$。
因為 $0\leq x \leq b-1$，所以有 $$d=ax+by\leq a(b-1)+by$$即$$d-a(b-1)\leq by$$因為$$d-a(b-1)>(ab-a-b)-a(b-1)=-b$$最後得到$$-b<d-a(b-1)\leq by$$即$$-b<by\mbox{, or $-1<y$}$$證明了 $y\geq 0$。所以原命題成立。
99 - 數論
試題查詢 http://www1c.moex.gov.tw/main/exam/wFrmExamQandASearch.aspx?menu_id=156
一、將 $540792$ 分解成質數的乘積。
二、試求 $6497$ 與 $11899$ 的最大公因數。
三、試求方程式 $29x-19y=5$ 的最小正整數解，再利用最小正整數解寫出此方程式的所有整數解。
四、已知 $729=27^2$、$71289=267^2$。試證：$71111288889$ 等於某個正整數的平方。
五、已知：$$
\begin{aligned}
&3^2+4^2+5^2=0^2+1^2+7^2 \\
&6^2+7^2+8^2=1^2+2^2+12^2 \\
&9^2+10^2+11^2=2^2+3^2+17^2
\end{aligned}
$$試對正整數 $n$ 寫出一個等式，使得：該等式在 $n=1$ 時就是上述第一式，在 $n=2$ 時就是上述第二式，在 $n=3$ 時就是上述第三式。並證明所寫等式對每個正整數 $n$ 都成立。
六、試證：若 $n$ 是大於 $9$ 的正整數，而且 $n-4$、$n-2$、$n+2$、$n+4$ 都是質數，則 $n$ 必是 $15$ 的倍數。並寫出滿足此假設條件的兩個最小正整數 $n$。
七、設 $n$ 等於兩個相異質數 $p$ 與 $q$ 的乘積。已知 $n$ 的所有正因數之和為 $768$，而小於 $n$ 且與 $n$ 互質的正整數共有 $660$ 個，試求 $n$ 的值。
八、試找出滿足下述條件的所有整數 $n$：$$9n\equiv 8\mbox{ (mod 13)}，11n\equiv -4\mbox{ (mod 12)}，0\leq n \leq 500$$請注意：所謂 $9n\equiv 8\mbox{ (mod 13)}$，乃是表示 $9n-8$ 是 $13$ 的倍數。
解題
一、
$540792=2^3\times 3^2\times 7\times 29\times 37$
二、
Greatest Common Divisor (GCD) for $6497$, $11899$ is $73$.
三、
最小正整數解 $(x_0,y_0)=(10,15)$，全部解$\left\{\begin{matrix}
x=10+19t\\
y=15+29t
\end{matrix}\right.,\; t\in \mathbb{Z}$
四、
觀察 $1$ 和 $8$ 有四個，答案是 $266667$.
五、
$(n+2)^2+(n+3)^2+(n+4)^2=(n-1)^2+n^2+(5n+2)^2$
六、
如果 $n\equiv 1\mbox{ mod($3$)}$，則 $n-4$、$n-2$、$n+2$、$n+4$ 除以 $3$ 的最小正剩餘分別為 $0$、$2$、$0$、$2$，表示其中 $n-4$ 和 $n+2$ 皆可被 $3$ 整除，與題目所設四數皆為質數矛盾，故 $n\not \equiv 1\mbox{ mod($3$)}$。
若 $n\equiv 2\mbox{ mod($3$)}$，四數之最小正剩餘分別為 $1$、$0$、$1$、$0$，表示其中 $n-2$ 和 $n-4$ 可被 $3$ 整除。
若 $n\equiv 0\mbox{ mod($3$)}$，四數之最小正剩餘分別為 $2$、$1$、$2$、$1$。
同理，若 $n\not \equiv 0\mbox{ mod($5$)}$，四數之最小正剩餘中，其中必有一為 $0$，即當中會有一個數是 $5$ 的倍數，與題目所述矛盾。當 $n\equiv 0\mbox{ mod($5$)}$，四數之最小正剩餘分別為 $1$、$3$、$2$、$1$。
因為 $3\mid n$，$5\mid n$，所以 $15\mid n$。
當 $n=15$，$\left\{\begin{matrix}
n-4=11\\
n-2=13\\
n+2=17\\
n+4=19
\end{matrix}\right.$
當 $n=7\times 15=105$，$\left\{\begin{matrix}
n-4=101\\
n-2=103\\
n+2=107\\
n+4=109
\end{matrix}\right.$
所以兩個最小的 $n$ 為 $15$ 和 $105$。
七、
正因數的和 $=(p^0+p^1)(q^0+q^1)=1+p+q+pq=768$；Euler's phi function $\varphi (n)=\varphi (pq)=\varphi (p)\varphi (q)=(p-1)(q-1)=660$。解 $pq=n=713$。
八、
$x\equiv 76\mbox{ (mod $156$)}$
一、將 $540792$ 分解成質數的乘積。
二、試求 $6497$ 與 $11899$ 的最大公因數。
三、試求方程式 $29x-19y=5$ 的最小正整數解，再利用最小正整數解寫出此方程式的所有整數解。
四、已知 $729=27^2$、$71289=267^2$。試證：$71111288889$ 等於某個正整數的平方。
五、已知：$$
\begin{aligned}
&3^2+4^2+5^2=0^2+1^2+7^2 \\
&6^2+7^2+8^2=1^2+2^2+12^2 \\
&9^2+10^2+11^2=2^2+3^2+17^2
\end{aligned}
$$試對正整數 $n$ 寫出一個等式，使得：該等式在 $n=1$ 時就是上述第一式，在 $n=2$ 時就是上述第二式，在 $n=3$ 時就是上述第三式。並證明所寫等式對每個正整數 $n$ 都成立。
六、試證：若 $n$ 是大於 $9$ 的正整數，而且 $n-4$、$n-2$、$n+2$、$n+4$ 都是質數，則 $n$ 必是 $15$ 的倍數。並寫出滿足此假設條件的兩個最小正整數 $n$。
七、設 $n$ 等於兩個相異質數 $p$ 與 $q$ 的乘積。已知 $n$ 的所有正因數之和為 $768$，而小於 $n$ 且與 $n$ 互質的正整數共有 $660$ 個，試求 $n$ 的值。
八、試找出滿足下述條件的所有整數 $n$：$$9n\equiv 8\mbox{ (mod 13)}，11n\equiv -4\mbox{ (mod 12)}，0\leq n \leq 500$$請注意：所謂 $9n\equiv 8\mbox{ (mod 13)}$，乃是表示 $9n-8$ 是 $13$ 的倍數。
解題
一、
$540792=2^3\times 3^2\times 7\times 29\times 37$
二、
Greatest Common Divisor (GCD) for $6497$, $11899$ is $73$.
三、
最小正整數解 $(x_0,y_0)=(10,15)$，全部解$\left\{\begin{matrix}
x=10+19t\\
y=15+29t
\end{matrix}\right.,\; t\in \mathbb{Z}$
四、
觀察 $1$ 和 $8$ 有四個，答案是 $266667$.
五、
$(n+2)^2+(n+3)^2+(n+4)^2=(n-1)^2+n^2+(5n+2)^2$
六、
如果 $n\equiv 1\mbox{ mod($3$)}$，則 $n-4$、$n-2$、$n+2$、$n+4$ 除以 $3$ 的最小正剩餘分別為 $0$、$2$、$0$、$2$，表示其中 $n-4$ 和 $n+2$ 皆可被 $3$ 整除，與題目所設四數皆為質數矛盾，故 $n\not \equiv 1\mbox{ mod($3$)}$。
若 $n\equiv 2\mbox{ mod($3$)}$，四數之最小正剩餘分別為 $1$、$0$、$1$、$0$，表示其中 $n-2$ 和 $n-4$ 可被 $3$ 整除。
若 $n\equiv 0\mbox{ mod($3$)}$，四數之最小正剩餘分別為 $2$、$1$、$2$、$1$。
同理，若 $n\not \equiv 0\mbox{ mod($5$)}$，四數之最小正剩餘中，其中必有一為 $0$，即當中會有一個數是 $5$ 的倍數，與題目所述矛盾。當 $n\equiv 0\mbox{ mod($5$)}$，四數之最小正剩餘分別為 $1$、$3$、$2$、$1$。
因為 $3\mid n$，$5\mid n$，所以 $15\mid n$。
當 $n=15$，$\left\{\begin{matrix}
n-4=11\\
n-2=13\\
n+2=17\\
n+4=19
\end{matrix}\right.$
當 $n=7\times 15=105$，$\left\{\begin{matrix}
n-4=101\\
n-2=103\\
n+2=107\\
n+4=109
\end{matrix}\right.$
所以兩個最小的 $n$ 為 $15$ 和 $105$。
七、
正因數的和 $=(p^0+p^1)(q^0+q^1)=1+p+q+pq=768$；Euler's phi function $\varphi (n)=\varphi (pq)=\varphi (p)\varphi (q)=(p-1)(q-1)=660$。解 $pq=n=713$。
八、
$x\equiv 76\mbox{ (mod $156$)}$
2015年6月25日 星期四
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}$ 不是整數。
一、設 $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}$ 不是整數。
訂閱：
文章 (Atom)