一、
$\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$。所以原命題成立。
沒有留言:
張貼留言