[數論] 第一章第一節整理

參考資料

張文忠，基礎數論：原理及題解，中央圖書，2002年出版，ISBN：978-957-637-493

• 數學歸納法(mathematical induction)
• 二項式公式(binomial formula)：連續 $k$ 個整數的乘積能被 $k!$ 整除
• 數的奇偶性(odevity)

定義1
設 $a$, $b$ 是任意兩個整數, 其中 $b\neq 0$, 若存在一個整數 $q$ 使得等式 $a= bq$ 成立, 則稱 $a$ 是 $b$ 的倍數(multiple), $b$ 是 $a$ 的因數(divisor), 記作 $b\mid a$.

1. 若 $b\mid a$, 則有 $b\mid -a$, $-b\mid a$, $\left | b \right |\mid \left | a \right |$
2. 若 $b\mid a$, $c\mid b$, 則 $c\mid a$
3. 若 $b\mid a$, 則對任何整數 $m$, 有 $b\mid ma$
4. 若 $b\mid a_{1}$, $b\mid a_{2}$, 則對任何整數 $m_{1}$, $m_{2}$, 有 $b\mid \left ( m_{1}a_{1}+m_{2}a_{2} \right )$
5. 若 $b\mid a$ 且 $a\mid b$, 則 $a=\pm b$
6. 若 $b\mid a$ 且 $a\neq 0$, 則 $\left | b \right |\leq \left | a \right |$

定理1 (除法定理(division algorithm))
設 $a$, $b$ 是兩個整數, 其中 $b>0$, 則存在兩個唯一的整數 $q$ 和 $r$, 使得 $a=bq+r$, $0\leq r<b$.

例1 試證：若 $3\mid n$ 且 $7\mid n$, 則 $21\mid n$.
例2 設 $a$, $b$ 是兩個非零整數, 且有整數 $x$, $y$, 使得 $ax+by=1$. 試證：若 $a\mid n$ 且 $b\mid n$, 則 $ab\mid n$.
例3 試證：對任何非負整數 $n$, $f\left ( n \right )=10^{n}+18n-28$ 都是$27$的倍數.
例4 設 $n\neq 1$, $k\geq 1$. 試證 $\left ( n-1 \right )^{2}\mid \left ( n^{k}-1 \right )$ 的充分必要條件是 $\left ( n-1 \right )\mid k$.
例5 試證：若 $5\mid \left ( a+b \right )$, 則 $25\mid \left ( a^{5}+b^{5} \right )$.
例10 若正整數 $n$ 的各位數碼之和與 $2n$ 的各位數碼之和相等, 試證： $n$ 必能被 $9$ 整除.
例11 設一個六位數 $n$, 它的前三位數碼組合的數 $a$ 與它後三位數碼組成的數 $b$ 之差 $b-a$ 能被 $7$ 整除, 試證：$7\mid n$.
例12 求能被自己的數碼之積整除的所有兩位數.
例13 試證：整數 $n^{5}$ 的個位數(即末位數碼)與 $n$ 的個位數是相同的.

解答題
7. 試證：若 $\left ( m-a \right )\mid \left ( mn+ab \right )$, 則 $\left ( m-a \right )\mid \left ( mb+na \right )$.
16. 試證：對任何正整數 $n$, $\left ( 3+\sqrt{5} \right )^{n}+\left ( 3-\sqrt{5} \right )^{n}$ 恆為整數且能被 $2^{n}$ 整除.
19. 試證：超過 $\left ( \sqrt{3}+1 \right )^{2n}$ 的最小整數可被 $2^{n+1}$ 整除.
20. 若 $a$, $b$ 為正整數, $a^{n}\mid b$, 試證：$a^{n+1}\mid \left ( a+b \right )^{b}-1$, $n=0,1,2,...$.
29. 試證： $3^{n}+1$ 能被 $2$ 或 $2^{2}$ 整除, 而不能被 $2$ 的更高次冪整除.
30. 試證：對於任何正整數 $n$ 和 $k$, 數 $N=2n^{3k}+4n^{k}+10$ 都不能表示為若干個連續正整數的乘積.
33. 試證：形如 $2^{k}$($k$ 為正整數)的數不能是幾個連續正整數的和.
<pf> 假設 $2^{k}$ 可以表示成連續 $n$ 個正整數的和, 亦即 $2^{k}=a_{1}+a_{2}+...+a_{n}=\frac{[a_{1}+a_{n}]n}{2}$. 上式可改寫為 $2^{k+1}=[a_{1}+a_{n}]n$. 如果 $n$ 是偶數, 則 $[a_{1}+a_{n}]$ 為奇數, 表示 $[a_{1}+a_{n}]n$ 含有 $2$ 以外的質因數, 無法表示成單純的 $2$ 的次方, 與原本的假設矛盾; 反之, 若 $n$ 是奇數, $[a_{1}+a_{n}]n$ 一樣含有 $2$ 以外的質因數. 所以原命題成立.
35. 若 $n>1$, 試證 $\underset{n}{\underbrace{11...1}}$ 不是整數的平方.
36. 有 $n$ 個數 $a_{1},a_{2},...,a_{n}$, 它們中的每一個數均為 $+1$ 或 $-1$, 若 $a_{1}a_{2}+a_{2}a_{3}+...+a_{n-1}a_{n}+a_{n}a_{1}=0$, 試證 $n$ 是 $4$ 的倍數.
<pf> 對每個 $a_{i}a_{j}$ 而言, $a_{i}a_{j}$ 不是 $1$ 就是 $-1$, 若有 $k$ 個 $-1$, 表示也同樣有 $k$ 個 $1$, 所以總數 $n=2k$. 若 $a_{i}a_{j}=1$, 表示 $a_{i}=a_{j}=1$ 或 $a_{i}=a_{j}=-1$, 兩數皆為同號; 若 $a_{i}a_{j}=-1$, 表示兩數為異號.
從起始的 $a_{1}a_{2}$ 到最後的 $a_{n}a_{1}$, 中間有 $k$ 個 $-1$, 表示從 $a_{1}$ 開始, 中間歷經了 $k$ 次變號. 若經歷奇數次變號,  $a_{1}a_{2}$ 的 $a_{1}$ 和 $a_{n}a_{1}$ 的 $a_{1}$ 的正負符號會不一樣. 所以經歷的變號次數為偶數次, 亦即 $k$ 為偶數, 所以 $n=2k$ 是 $4$ 的倍數.
37. 試證：若正整數 $n$ a_{i}a_{j}可以寫成兩個整數的平方和, 則 $2n$ 也可以寫成兩個整數的平方和, 反之亦然.
39. 試證：對任何整數 $n$, 下述的方程式無整數解：$x^{2}-y^{2}=4n+2$.
40. 若 $n$ 為正整數, 但不是 $4$ 的倍數, 試證：$5\mid \left (1^{n}+2^{n}+3^{n}+4^{n} \right )$.
<pf> 可用末位數是否為 $0$ 或 $5$ 去判斷. 會發現末位數字以四個數字為一循環，依序是 $0$, $0$, $0$ 及 $4$.
41. 有 $n$ 個整數, 其積為 $n$, 其和為 $0$, 試證：$4\mid n$.
42. 設整數 $a>0$, $b>2$, 試證：$(2^{b}-1)\nmid  (2^{a}+1)$.
<pf> 假設 $a>b$, $(2^{a}+1,2^{b}-1)=\left (  2^{a}+1+(1)(2^{b}-1),2^{b}-1\right )=(2^{a}+2^{b},2^{b}-1)$, 因為 $2^{a}+2^{b}$ 是偶數, $2^{b}-1$ 是奇數, 故 $(2^{a}+2^{b},2^{b}-1)=1$, 表示 $2^{a}+1$ 和 $2^{b}-1$ 兩數互質. 同理, 當 $a<b$ 時, 一樣得到 $2^{a}+1$ 和 $2^{b}-1$ 兩數互質的結論.
當 $a=b$ 時, $(2^{a}+1,2^{b}-1)=(2^{a}+1,2^{a}-1)=\left ( 2^{a}+1+(-1)(2^{a}-1),2^{a}-1 \right )=(2,2^{a}-1)=1$, $2^{a}+1$ 和 $2^{b}-1$ 仍為互質.
因為兩數互質, 故一數必不為另一數的倍數.
44. 若正整數 $n>1$, 試證：(1) $2^{n}-1$ 不是任何整數的平方 (2) $2^{n}-1$ 不是任何整數的立方.
46. 若 $k$ 是正奇數, 試證：對任何正整數 $n$, 有 $(1+2+3+\cdots +n)\mid (1^k+2^k+3^k+\cdots n^k)$.
47. (1) 試求出所有的正整數 $n$, 使 $2^{n}-1$ 能被 $7$ 整除.
49. 是否存在 $2n$ 個正奇數的倒數之和等於 $1$?
50. 試證：對於任意的正整數 $n$, 一定存在 $n$ 的一個倍數 $m$, 它是僅由數字 $0$ 和 $1$ 組成的.
51. 任給 $7$ 個不同的整數, 試證：必有兩個整數, 其和或差是 $10$ 的倍數.
52. 任給 $n+1$ 個不同的整數, 且它們都小於 $2n$, 試證：必可從中選出三個數, 使其中兩個之和等於第三個.
53. 將 $1,2,\cdots ,10$ 這 $10$ 個數任何擺成一個圈圈(即放在一個圓周上), 試證：必有 $3$ 個相鄰的數, 它們的和不小於 $17$
54. 設正整數 $n$ 有如下的性質：從 $1,2,,\cdots ,n$ 中任取 $50$ 個不同的數, 這 $50$ 個數中必有兩個數之差等於 $7$. 試求 $n$ 的最大值.
55. 從 $1,2,3,\cdots ,100$ 這 $100$ 個正整數中, 隨意選出 $51$ 個數, 試證：其中一定有兩個數, 它們之中的一個可以整除另一個.
56. 試證：$1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}\left ( n>1 \right )$ 不是整數.
<pf> 在分母中找出含因數$2$最多個的數, 令其為 $2^{m}$. 令 $t$ 為所有不大於 $n$ 之奇數的乘積. 原式乘上 $2^{m-1}t$ 後,  其中 $\frac{1}{2^{m}}\cdot 2^{m-1}t$ 為 $\frac{1}{2}t$, 其餘各項皆為整數. 由於整數乘上整數後仍為整數, 但今乘上 $2^{m-1}t$ 後卻不為整數, 故原式非整數
57. 試證：$\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\cdots +\frac{1}{2n+1}(n\geq 1)$ 不是整數.

解答 https://drive.google.com/folderview?id=0ByvpOhgGXKImNldGZVlsdG1ORzQ&usp=sharing