---
# System prepended metadata

title: N(數論)

---

## 同餘基本概念

## 範例$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)$
:::

<!-- $3^{2l} - 1 = 2^{k + 1} \implies (3^l + 1)(3^l - 1) = 2^{k + 1} \implies u(u + 1) = 2^{k - 1}$ 哪有跳太多 -->