N(數論) - HackMD

## 同餘基本概念 ## 範例$1.1.$ 證明質數有無窮多個。 :::spoiler `參考解答在這！！！` :::success 對於任意若干個質數 $p_1, p_2, \dots, p_n$ 設 $M = p_1 \times p_2 \times \dots p_n + 1$, 會發現 $M$ 會跟 $p_1, p_2, \dots, p_n$ 互質，則$M$必有異於$p_1, p_2, \cdots, p_n$ 的質因數，令其為 $p_{n+1}$ 有限個質數可以依據上述不斷找出新的質數，故質數有無窮多個。 ::: ## 範例$1.2.$ 證明兩連續正整數的乘積不是完全平方數。 :::spoiler `參考解答在這！！！` :::success 對於任意正整數 $n$, $n > 0$, 有 $n^2 < n(n + 1) < (n + 1)^2$ 因為 $n(n+1)$ 介於兩連續完全平方數之間，所以 $n(n+1)$ 不為完全平方數。 ::: ## 範例$1.3.$ 一個正整數，加上 $100$ 為一個完全平方數，加上 $168$ 為另一個完全平方數，求此數。 :::spoiler `參考解答在這！！！` :::success 令此正整數為 $N \implies N + 100 = x^2$, $N + 168 = y^2$ $y^2 - x^2 = (y-x)(y + x) = 68 = 4\times17~ _{or} ~2 \times 34~_{or} ~1\times68$ 若兩數為一奇一偶，則 $x,y$ 均非正整數，故只有 $y-x = 2,~ y+x = 34$ 符合。解得 $x = 16, y = 18 \implies N = 156$ ::: ## 範例$1.4.$ 證明存在正整數的無窮數列 $a_1 < a_2 < a_3 <...$使得對所有正整數$n,$ $a_1^2 + a_2^2 + ... +a_n^2$ 都是完全平方數 ::: spoiler `參考解答在這！！！` :::success 我們讓$a_1, a_2, a_3, a_4,... = 3, 4, 12,\cdots$ $(3^2 + 4^2 = 5^2 、 5^2 + 12^2 = 13^2)$ 利用畢氏數易解 $<$ **更多的** $>$ 我們有畢氏三元數 $$(a^2-b^2, 2ab, a^2+b^2)$$ 其中$a>b \in \mathbb{N}$ 又有 $$ a^2-b^2 = (a+b)(a-b)$$ 所以只要$a=b+1$，我們就可以構出所有的奇數 $ex: 13 = (7_{(a)} + 6_{(b)})( 7_{(a)} - 6_{(b)}))$ 只要有$2ab$，我們就可以構出所有的偶數 $ex: 14 = 2 \times 1_{(b)} \times 14_{(a)}$ ::: ## 範例$1.5.$ 設 $\pi(n)$ 表示不大於 $n$ 的質數的個數。求證：對任意正整數 $n$ 和非負整數 $k \le \pi(n)$，總存在 $n$ 個連續正整數，其中恰含有 $k$ 個質數。 :::success 令以 $m$ 為首項的連續 $n$ 數有 $T~(n, m)$ 個整數則 $T~(n, 1) = \pi(n), ~T(~(n + 1)! + 2~) = 0$ $(~ \because (n + 1)! + 2, ... ,(n + 1)! + (n + 1)$中沒有質數 $)$。觀察得 \begin{align*} T(n, m + 1) = \begin{cases} T(n, m) + 1,~~ m ~為合數且 ~(m+n)~ 為質數\\ T(n, m) - 1,~~ m ~為質數且 ~(m+n)~ 為合數\\ T(n, m),~~~~~ m ~與 ~(m + n)~ 皆為質數或合數 \end{cases} \end{align*} 因此 $T(n, m)$ 在整數域中連續。當 $0 \le k \le \pi(n)$ 時，在 $1 \le m \le (n + 1)! + 2$ 中必定找得到 $T(n, m) = k$， ::: ## 範例$2.2.$ 設 $k$ 是正奇數，證明：$\frac{n(n + 1)}{2} \bigg| (1^k + 2^k + \cdots + n^k)$. :::spoiler `參考解答在這！！！` :::success 題目所求等價於證明 $n(n+1) ~~| ~~2(1^k + 2^k + \cdots + n^k)$ $\because ~n, n + 1$互質，$\therefore$ 須證明 $(1^k + 2^k + \cdots + n^k)$ 分別為 $n$, $n+1$ 的倍數 **Part 1 : 證明為 $n$ 的倍數** \begin{align*} &2(1^k + 2^k + \cdots + n^k) \\ &= (1^k + (n-1)^k) + (2^k + (n -2)^k) + \cdots + ((n-1)^k + 1^k) + 2n^k\\\\ \because~ &(1^k + (n-1)^k) + (2^k + (n -2)^k) + \cdots + ((n-1)^k + 1^k) + 2n^k \\ &\equiv (1^k + (-1)^k) + (2^k + (-2)^k) + \cdots + ((-1)^k + 1^k) + 0\\ &\equiv 0~ (mod ~ n)\\ \therefore ~&n ~| ~2(1^k + 2^k + \cdots + n^k) \end{align*} **Part 2 : 證明為 $n + 1$ 的倍數** \begin{align*} &2(1^k + 2^k + \cdots + n^k) = \sum^{n}_{i=1} (i^k + [(n+1)-i]^k)\\ \because~ &\sum^{n}_{i=1} (i^k + [(n+1)-i]^k) \equiv \sum^{n}_{i=1} (i^k + (-i)^k) \equiv 0~ (mod ~ n+1)\\ \therefore ~&n+1 ~| ~2(1^k + 2^k + \cdots + n^k) \end{align*} 綜合上述，$2(1^k + 2^k + \cdots + n^k)$ 為 $n$ 及 $n+1$ 的倍數，有 $$ n(n+1) ~|~ 2(1^k + 2^k + \cdots + n^k) $$ 故得證。 ::: ## 範例$2.4.$ 已知不定方程 \begin{align} x_1^4 + x_2^4 + \cdots + x_n^4 = 799 \end{align} 有正整數解，則正整數 $n$ 的最小值為？ :::spoiler `參考解答在這！！！` :::success 任意正整數$4$次方 $\equiv 0 ~_{or}~ 1~(mod~16)$，$799 \equiv 15~(mod~16)$, 可知 $n$ 至少為 $15$, 又可構造出 $$ x_1 = 5,~x_2 = x_3 = 3,~x_4 = x_5 = \cdots = x_{15} = 1 $$ 使得 $x_1^4 + x_2^4 + \cdots + x_{15}^4 = 1 \times 625 + 2 \times 81 + 12 \times 1 = 799$. 故所求最小值為$15$. ::: ## 範例$2.5.$ 求方程 \begin{align} 2^x + 3^y = z^2 \end{align} 的所有正整數解 $(x, y, z)$. :::spoiler `參考解答在這！！！` :::success **Part 1 ：對 $LHS$ 及 $RHS$ 模 $3$** 顯然 $z$ 不是三的倍數，故 $z^2 \equiv 1~(mod~3)$ $2^x \equiv 2^x + 3^y \equiv 1 ~(mod ~3)$，得$~x~$是偶數，設 $x = 2k$ 原式等價於 $(z - 2^k)(z + 2^k) = 3^y$, 由於括號中兩數之和為$2z$，顯然不能兩個都為三的倍數，故 $z - 2^k = 1$ $\implies z = 2^k + 1, 2^k + z = 3^y$ $\implies 3^y - 1 = 2^{k + 1}$ **Part 2 : 對 $3^y - 1 = 2^{k + 1}$ 模 $4$** 由 $3^y - 1 \equiv 0~(mod ~4)$得知 $y$ 是偶數。設 $y$ 為 $2l$, $3^l = 2u + 1$，則由 $3^y - 1 = 2^{k + 1}$，有 $3^{2l} - 1 = (3^l - 1)(3^l + 1) = 4u(u+1) = 2^{k+1}$ $\implies u(u+1) = 2^{k-1}$ 顯然 $u = 1$，否則 $u(u + 1)$ 將有奇質因數。解得$(x,y,z) = (4,2,5)$ :::