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

• 一個數加上另一個數的整數倍後, 它們的最大公因數不變
• 輾轉相除法
• 最小公倍數
• 整值多項式(integral valued polynomial)不一定是整係數
• 整點(integral point), 或稱格點(lattice point)

定理1

假設 $a, b, c$ 是任意三個不全為零的整數, 並且 $a=bq+c$, 其中 $q$ 是整數, 則 $(a,b)=(b,c)$.

定理3

若 $a, b$ 是任意兩個正整數, 則存在兩個整數 $s, t$ 使得 $sa+tb=(a, b)$.

定理4

若 $a\mid bc$, $(a, b)=1$, 則 $a \mid c$.

定理9

若 $a, b$ 為正整數, $(a, b)=1$, 則 $[a, b]=ab$.

定理10

設  $a, b$ 為任意兩個正整數, 則 $[a, b]=\frac{ab}{(a, b)}$.

<pf> 令 $(a, b)=g$, $[a, b]=l$. $a=gh$, $b=gk$, $h,k\in \mathbb{Z}$, $(h, k)=1$. 則 $[a, b]=l=ghk$. $(a, b)[a, b]=g\cdot l=g\cdot ghk=gh\cdot gk=a\cdot b$.

定義3

當變數 $x$ 取整數時, 若多項式 $f(x)=a_{k}x^{k}+a_{k-1}x^{k-1}+...+a_{1}x+a_{0}$ 之值恆為整數, 則稱此多項式為整值多項式(integral valued polynomial). 整值多項式不一定是整係數的, 例如組合數.

公式：定義 $\Delta f(x)=f(x+1)-f(x)$, 則 $\Delta \binom{x}{k}=\binom{x+1}{k}-\binom{x}{k}=\binom{x}{k-1}$.

定理12
任何 $k$ 次整值多項式 $f(x)$ 必可表示為 $f(x)=C_{k}\binom{x}{k}+C_{k-1}\binom{x}{k-1}+...+C_{1}\binom{x}{1}+C_{0}$, 其中 $C_{k}, C_{k-1},..., C_{0}$ 皆為整數.

定理13
對任意整數 $x$, 整值多項式 $f(x)=C_{k}\binom{x}{k}+C_{k-1}\binom{x}{k-1}+...+C_{1}\binom{x}{1}+C_{0}$ 的值皆為 $m$ 的倍數的充分必要條件為 $m\mid \left ( C_{k}, C_{k-1},...,C_{0} \right )$.

定理14
設 $k$ 次多項式為 $f(x)=a_{k}x^{k}+a_{k-1}x^{k+1}+...+a_{0}, (a_{k}\neq 0)$, 若 $x$ 取 $k+1$ 個連續整數 $a, a+1, ..., a+k$ 的值恆為整數, 則 $f(x)$ 為整值多項式.

定理14'
設 $f(x)$ 為 $k$ 次多項式, 若 $x$ 取 $k+1$ 個連續整數 $a, a+1, ..., a+k$ 時, $f(x)$ 的值皆能被 $m$ 整除, 則對任意整數 $x$, $f(x)$ 皆能被 $m$ 整除.

定義4
平面上座標 $x, y$ 都是整數的點稱為整點(integral point)或格點(lattice point).

例1 對任何整數 $q$, 試證 $(a_{1} ,a_{2})=(a_{1}, a_{2}+a_{1}q)$, i.e., 一個數加上另一個數的整數倍後, 它們的最大公因數不變.

例6 試證：$f(n)=\frac{1}{3}n^{3}+\frac{1}{2}n^{2}+\frac{1}{6}n$ 是一個整值多項式.

例8 試證：$f(n)=n^{3}+\frac{3}{2}n^{2}+\frac{1}{2}n-1$ 對任意整數 $n$ 都是整數, 且 $3$ 除時餘 $2$.

例10 試求在方程 $x^{2}+y^{2}=625$ 的圖像的圓上有多少整點.

例11 試證：方程 $x^{2}-y^{2}=6$ 所畫出的雙曲線上沒有整點.

例12 設 $m$ 和 $n$ 為正整數. 試證：在平面內以 $(0,0), (n,0), (0,m)$ 為頂點的三角形中(包括三條邊上)整點的個數為 $M=\frac{1}{2}[(m+1)(n+1)+d+1], d=(m,n)$.

解答題
7. 試證：若 $(a,b)=1$, 則 $(a,bc)=(a,c)$.
9. 試證：$\left ( \frac{a_{1}}{\left ( a_{1},a_{2},...,a_{n} \right )},  \frac{a_{2}}{\left ( a_{1},a_{2},...,a_{n} \right )},..., \frac{a_{n}}{\left ( a_{1},a_{2},...,a_{n} \right )}\right )=1$.
11. 設 $n$ 是奇數, 試證：(1) 當 $n\geq 3$ 時, 一定存在正整數 $k\leq n-1$, 使得 $n\mid (2^{k}-1)$. (2) 必存在正整數 $t$, 使 $(2^{t}-3,n)=1$.
17. 試證：若 $(a,b)=1$, 則 $(d,ab)=(d,a)(d,b)$.
18. 設 $a>b>0, n>1$, 試證：$(a^{n}-b^{n})\nmid (a^{n}+b^{n})$.
19. 設 $a>b, (a,b)=1$, 試證：$(a^{m}-b^{m},a^{n}-b^{n})=a^{(m,n)}-b^{(m,n)}$.
25. 若 $(a,b)=1$, 試證：$(a+b,a^{2}+b^{2})=1$ 或 $2$.
27. 設 $m, n$ 是正整數且 $m$ 是奇數, 試證：$(2^{m}-1,2^{n}+1)=1$.
28. 設 $(m,n)=1$, 試證：$m!n!\mid (m+n-1)!$.
30. 設 $a, b, c$ 為任意三個整數, 且 $c\neq 0$, 試證：總能找到兩個互質的整數 $k, m$, 使得 $c\mid (ak+bm)$.
32. 當 $n$ 為什麼樣的正整數時, $n^{4}+n^{2}$可被 $2n+1$ 整除？
<pf> $n^{4}+n^{2}=\left ( 2n+1 \right )\left ( \frac{n^{3}}{2} \right )+\left ( -\frac{n^{3}}{2} +n^{2}\right )$. 因為餘數要為零, 所以 $\left ( -\frac{n^{3}}{2} +n^{2}\right )=0$, 算出 $n=0,0,2$. 又$n$ 是正整數, 故 $0$ 不合, 所以 $n=2$.
33. 已知正整數 $m>n$, 當 $4^{m}+4^{n}$ 為 $100$ 的倍數時, $m+n$ 最小為多少?
34. 若 $6\mid (a_{1}+a_{2}+a_{3})$, 試證：$6\mid (a_{1}^{3}+a_{2}^{3}+a_{3}^{3})$.
35. 若 $n$ 和 $A$ 是正整數, 且 $\sqrt[n]{A}$ 不是整數, 試證：$\sqrt[n]{A}$ 一定不是有理數.
36. 設 $a, b, c, d$ 為任意的四個整數, 試證：$12\mid (a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$.
39. 設 $a, b, c$ 是兩兩互素的正整數, 且 $\frac{1}{a}+\frac{1}{b}=\frac{1}{c}$, 試證：$a+b, a-c, b-c$ 都是平方數.
40. 試證：存在無窮多個 $n$, 使 $n\mid (2^{n}+1)$.
41. (1) 若 $n\mid (2^{n}+2), (n-1)\mid (2^{n}+1)$, 試證：當 $m=2^{n}+2$ 時, 恆有 $m\mid (2^{m}+2)$, $(m-1)\mid (2^{m}+1)$.
      (2) 試證：存在無窮多個 $n$, 使 $n\mid (2^{n}+2)$.
42. 若正整數 $a, b$ 滿足 $[a,b]=(a,b)$, 試證：$a=b$.
44. 設 $a, b, c$ 是正整數, 試證：(1) $[a, b, c](ab, bc, ca)=abc$; (2) $[a, b, c]=abc$ 的充分必要條件是 $(a, b)=(b,c)=(c,a)=1$.
45. 試證：$[a_{1},a_{2},...,a_{n}]=\frac{a_{1}a_{2}...a_{n}}{(A_{1},A_{2},...,A_{n})}$, $n\geq 2$, 其中 $A_{i}=\frac{a_{1}a_{2}...a_{n}}{a_{i}}, i=1,2,...,n$.
46. 試證：$(a,b,c)\leq (a,b)$, $[a,b,c]\geq [a,b]$.
47. 試求滿足 $(a,b)=10$, $[a,b]=100$ 的全部正整數組 $a, b$.
49. 試求滿足 $(a,b)=8$, $[a,b]=48$的全部正整數組 $a, b$.
54. 試證：對任何整數 $n$, 多項式 $f(n)=\frac{1}{5}n^{5}-\frac{2}{3}n^{3}-\frac{8}{15}n$ 皆取整數值.
57. 試求能整除 $f(n)=n^{3}+5n$ 的一切整數, 並確定其中的最大者.
58. 試證：對任何整數 $n$, $7\mid (n^{7}+6!n)$. (試用費馬定理)
59. 設 $f(x)$ 為整係數多項式, 對於整數 $x_{0}$, $a$, 當 $f(a)\neq 0$ 時, 試證：$x_{0}-a$ 整除 $f(x_{0})$ 的充分條件是 $x_{0}-a$ 整除 $f(a)$.
60. 試求最大的正整數 $n$, 使 $n^{3}+100$ 能被 $n+10$ 整除.
61. 試求使 $n^{3}+m^{2}$ 能被 $n+m$ 整除的正整數 $n$ 的最大值.
62. 設有整係數 $k$ 次多項式 $f(x)$ 與一次多項式 $ax-b$ ($a\neq 1, (a,b)=1$), 試證：整數 $x_{0}$ 使 $ax_{0}-b$ 整除 $f(x_{0})$ 的充分必要條件是 $(ax_{0}-b)\mid a^{k}f\left ( \frac{b}{a} \right )$.
63. 已知 $n$ 是正整數, 且 $n^{2}-71$ 能被 $7n+55$ 整除, 試求 $n$.
64. 當 $n$ 是何正整數時, $2n+1$ 整除 $n^{4}+n^{2}$？
65. 設 $m_{1}, m_{2}, n_{1}, n_{2}$ 都是整數, 且 $m_{1}\neq m_{2}$, 試證：存在一個整係數多項式 $f(x)$ 滿足 $f(m_{1})=n_{1}$, $f(m_{2})=n_{2}$ 的充分必要條件是 $(m_{1}-m_{2})\mid (n_{1}-n_{2})$.
66. 若整數 $b$ 為整係數多項式 $f(x)$ 的根, 即 $f(b)=0$, 試證：對任意整數 $a$, 有 $(a-b)\mid f(a)$.
67. 試證：任何整係數多項式 $f(x)$ 都不能同時滿足 $f(7)=5$, $f(15)=9$.