素数の一般項を高校数学で理解する

素数とは、約数が $1$ とその数自身のみである $1$ でない自然数のことである．

$n$ 番目の素数は

$$p(n) = 1 + \sum_{m=1}^{2^n}\left\lfloor \sqrt[n]{ \begin{gather*} \frac{n}{\sum_{k=1}^m \left\lfloor \cos^2\frac{(k-1)! + 1}{k}\pi\right\rfloor} \end{gather*} }\right\rfloor$$

これを以下の順で理解する．

$$\begin{align*} (1) &\colon \sum_{k=1}^m \left\lfloor \cos^2\frac{(k-1)! + 1}{k}\pi\right\rfloor \eqqcolon 1 + \phi(m) \\ (2) &\colon \sum_{m=1}^{2^n} \left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor \end{align*}$$

(1) を理解する

$a \equiv b \; (\bmod \; p), \; c \equiv d \; (\bmod \; p)$ のとき $a \pm c \equiv b \pm d \; (\bmod \; p)$

証明

$a \coloneqq q_1p + r, \;b \coloneqq q_2p + r, \; c \coloneqq q_3p + r^\prime, \; d \coloneqq q_4p + r^\prime$ とすると

$$\begin{aligned} a\pm c &= (q_1\pm q_3)p + (r\pm r^\prime) \\ b\pm d &= (q_2\pm q_4)p + (r\pm r^\prime) \end{aligned}$$

余りが一致するので $a\pm c \equiv b\pm d \enspace (\text{mod} \enspace p)$．

$ab \equiv ac \; (\bmod \; p)$ で $a$ と $p$ が互いに素のとき $b \equiv c \; (\bmod \; p)$

証明

$ab - ac = a(b-c) \equiv 0 \; (\bmod \; p)$ より $a(b-c)$ は $p$ の倍数である．

ここで、$p$ の素因数分解を ${p_1}^{e_1}{p_2}^{e_2}\cdots{p_k}^{e_k}$ とする．

• $a(b-c)$ は素因数 $p_1$ を $e_1$ 個以上持つ．
• $a$ と $p$ が互いに素だから、$a$ は素因数 $p_1$ を持たない．

以上より $b-c$ が素因数 $p_1$ を $e_1$ 個以上持つ．

同様に $i = 2, 3, \cdots , k$ に対しても $b-c$ が素因数 $p_i$ を $e_i$ 個以上持つことが分かる．

よって、 $b-c$ が $p$ の倍数だから $b - c \equiv 0 \; (\bmod\; p) \;\xLeftrightarrow{}\; b \equiv c \; (\bmod \; p)$．

フェルマーの小定理
素数 $p$ と互いに素な整数 $a$ について $a^{p-1} \equiv 1 \;(\bmod\; p)$

証明

$${}_p\mathrm{C}_r = \frac{{}_p\mathrm{P}_r}{r!} = \frac{p(p-1)(p-2)\cdots(p-(r-1))}{r!}$$

${}_p\mathrm{C}_r$ は組み合わせの総数だから整数である．

また、$1 \le r \le p-1$ のとき、分母は素因数 $p$ を持たず、また $p$ は素数だから、分子の $p$ は約分されない．

したがって、$p$ が素数で $1 \le r \le p-1$ のとき ${}_p\mathrm{C}_r$ は $p$ の倍数である．$\cdots (1)$

以下 $\bmod\; p$ で考える．

任意の自然数 $a$ に対して $a^p \equiv a \;\cdots (*)$ であることを示す．

$a = 1$ のとき $(*)$ が成立．

$a = m$ のとき $(*)$ が成立すると仮定すると $m^p \equiv m \enspace \cdots(2)$．

$a = m+1$ のとき、

$$\begin{align*} (m+1)^p &\equiv \sum_{r=0}^p {}_p\mathrm{C}_r\cdot1^{p-r}\cdot m^r \\ &\equiv m^p + 1 + \underbrace{\sum_{r=1}^{p-1}{}_pC_r m^r}_{\text{multiples of}\,\, p \enspace \because \,(1)}\\ &\equiv m^p+1 \\ &\equiv m+1 \enspace \because (2) \end{align*}$$

よって、任意の自然数 $a$ に対して $a^p \equiv a$ であることが示された．

ここで、$a$ と $p$ は互いに素だから、両辺を $a$ で割って $a^{p-1} \equiv 1$．

ウィルソンの定理
$p$ が素数 $\xLeftrightarrow{}$ $\{(p-1)! + 1\} \bmod p = 0$

証明

$f(x) \coloneqq x^{p-1}-1 \; (x\in\Z)$ とする．

フェルマーの小定理より、$f(x) \equiv 0\;(1\le x\le p-1)$．

$f(x)$ を $(x-1)$ で割った商を $Q_1(x)$、余りを $R_1$ とする．

$f(x) = Q_1(x)(x-1) + R_1$．

$x = 1$ を代入すると、$f(1) \equiv 0$ より $R_1 \equiv 0$ だから、

$$f(x) \equiv Q_1(x)(x-1)$$

$Q_1(x)$ を $(x-2)$ で割った商を $Q_2(x)$、余りを $R_2$ とする．

$Q_1(x) = Q_2(x)(x-2) + R_2$ だから、

$$\begin{align*} f(x) &= \{ Q_2(x)(x-2) + R_2 \}(x-1) + R_1 \\ &\equiv \{ Q_2(x)(x-2) + R_2 \}(x-1) \end{align*}$$

$x = 2$ を代入すると、$f(2) \equiv 0$ より $R_2 \equiv 0$ だから、

$$f(x) \equiv Q_2(x)(x-2)(x-1)$$

以下同様にして、

$$f(x) \equiv Q_{p-1}(x)(x-(p-1))\cdots(x-2)(x-1)$$

ここで、

	次数	最高次の係数
$f(x)$	$p-1$	$1$
$Q_1(x)$	$p-2$	$1$
$Q_2(x)$	$p-3$	$1$
$\vdots$	$\vdots$	$\vdots$
$Q_{p-1}(x)$	$p-((p-1)+1) = 0$	$1$

より $Q_{p-1}(x) = 1$ だから

$$\def\mytxt#1{\text{\sf\footnotesize #1}} f(x) \equiv (x-1)(x-2)\cdots(x-(p-1)) \enspace \cdots \enspace (\mytxt{剰余の定理})$$

$x = 0$ を代入すると

$$-1 \equiv (-1)(-2)\cdots(-(p-1)) = (-1)^{p-1}(p-1)!$$

$p = 2$ のとき成立．

$p \ne 2$ のとき $p$ は奇数なので、$-1 \equiv (p-1)!$ となる．

以上より $\{ (p-1)! + 1 \} \equiv 0 \; (\bmod \; p)$ が成立．

ウィルソンの定理を用いると、ある整数 $k\ge2$ について

$$\frac{(k-1)! + 1}{k} \left\{\begin{aligned} &\in \Z \; \xLeftrightarrow{} \; k \,\, \text{is prime} \\ &\notin \Z \; \xLeftrightarrow{} \; k \,\, \text{is not prime} \end{aligned}\right.$$

だから、

$$\def\mytxt#1{\text{\sf\footnotesize #1}} \begin{align*} \left|\cos\frac{(k-1)! + 1}{k}\pi\right| &\left\{\begin{aligned} &= 1 \;(k \,\,\text{is prime}) \\ &\ne 1 \;(k \,\,\text{is not prime}) \end{aligned}\right. \\ \cos^2\frac{(k-1)! + 1}{k}\pi &\left\{\begin{aligned} &= 1 \;(k \,\,\text{is prime}) \\ &\ne 1 \;(k \,\,\text{is not prime}) \end{aligned}\right. \\ \left\lfloor\cos^2\frac{(k-1)! + 1}{k}\pi\right\rfloor &=\left\{\begin{aligned} &1 \;(k \,\,\text{is prime}) \\ &0 \;(k \,\,\text{is not prime}) \end{aligned}\right. \\ \sum_{k=1}^m \left\lfloor \cos^2\frac{(k-1)! + 1}{k}\pi\right\rfloor &= 1+( m \,\,\mytxt{以下の素数の個数})\colon\phi(m) \\ &\quad \because \; k=1 \,\,\mytxt{のとき}\,\,1\,\,\mytxt{だが}\,\,1\,\,\text{is not prime} \end{align*}$$

(2) を理解する

$\displaystyle \frac{n}{1+\phi(m)}$ について

• $1 + \phi(m) \le n$ のとき

  $$\begin{align*} \frac{n}{1+\phi(m)} &\ge 1 \\ \sqrt[n]{\frac{n}{1+\phi(m)}} = \frac{n^\frac{1}{n}}{(1+\phi(m))^\frac{1}{n}} &< n^\frac{1}{n} \;\because\;(1+\phi(m))\ge 1 \end{align*}$$

  ここで、$\mathrm{max}(x^\frac{1}{x}) = e^\frac{1}{e} < 2$ である．

  証明

  $y = x^\frac{1}{x} \; (x \ge 1 \;\because\; n \ge 1)$ について

  $$\def\mytxt#1{\text{\sf\footnotesize #1}} \begin{align*} \log y &= \log x^\frac{1}{x} = \frac{1}{x}\log x \\ \frac{1}{y}y^\prime &= - \frac{1}{x^2}\log x + \frac{1}{x}\frac{1}{x} = \frac{1}{x^2}(1 - \log x) \\ y^\prime &= \frac{x^\frac{1}{x}}{x^2}(1-\log x) = 0 \\ &\xRightarrow{}\; x = e \end{align*}\enspace\enspace\enspace\enspace\enspace \begin{align*} \begin{array}{l|cccc} x & 1 &\cdots & e & \cdots \\ y^\prime & + & + & 0 & - \\ y & \nearrow & \nearrow & \mathrm{max} & \searrow \end{array} \\\\ \therefore \;\mathrm{max}(x^\frac{1}{x})=e^\frac{1}{e} \end{align*}$$

  $e^\frac{1}{e},2 > 0$ であることと $\log x$ が単調増加であることより、両者の対数をとる．

  $$\begin{align*} \log e^\frac{1}{e} &= \frac{1}{e} = 0.36... \\ \log 2 &= [ \log x ]_1^2 = \int_1^2 \frac{1}{x}\,dx \end{align*}$$

  $\log 2$ は $\displaystyle \frac{1}{x} \; (1 \le x \le 2)$ の接線を 1 辺とする台形の面積よりも大きい．

  $\displaystyle y = \frac{1}{x}$ の $x = a$ における接線は $\displaystyle y - \frac{1}{a} = - \frac{1}{a^2}(x - a) \;\xRightarrow{}\;y = -\frac{1}{a^2}x+\frac{2}{a}$．

  $\displaystyle x = 1.5 = \frac{3}{2}$ における接線は

  $$\def\mytxt#1{\text{\sf\footnotesize #1}} \begin{align*} &y = \frac{2^2}{3^2}x + 2\frac{2}{3} = \frac{4}{9}(3-x) \\ &\xRightarrow{} \; y(1) = \frac{4}{9}\cdot2 = \frac{8}{9}, \; y(2) = \frac{4}{9}\cdot1 = \frac{4}{9} \\ &\xRightarrow{} \; (\mytxt{台形の面積}) = 1 \cdot \left(\frac{8}{9} + \frac{4}{9} \right) \cdot \frac{1}{2} = \frac{6}{9} = \frac{2}{3} > 0.36... = \log e^\frac{1}{e} \\ &\xRightarrow{} \; \log e^\frac{1}{e} < (\mytxt{台形の面積}) < \log 2 \end{align*}$$

  以上より $e^\frac{1}{e} < 2$．

  $$\begin{align*} &1 \le \sqrt[n]{\frac{n}{1+\phi(m)}} < n^\frac{1}{n} < 2 \;\xRightarrow{} \; \left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = 1 \end{align*}$$

• $1 + \phi(m) > n$ のとき

  $$\begin{align*} 0 < \frac{n}{1+\phi(m)} < 1 \;\xRightarrow{}\; 0 < \sqrt[n]{\frac{n}{1+\phi(m)}} < 1 \;\xRightarrow{}\; \left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = 0 \end{align*}$$

以上より

$$\left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = \left\{\begin{aligned} 1 \; (1 + \phi(m) \le n) \\ 0 \; (1 + \phi(m) > n) \end{aligned}\right.$$

ベルトランの仮説 (定理)
任意の自然数 $n$ に対して $n < p \le 2n$ を満たす素数 $p$ が存在する

$2^n$ でなくても、十分に大きい数であれば何でも良い．ベルトランの仮説より

$$1 + \phi(2^n) \ge 1+n > n$$

だから、$2^n$ を用いる．

加算は以下のようになる．

$$\sum_{m=1}^{2^n} \left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = 1 + 1 + \cdots + 1 + 0 + 0 + \cdots + 0$$

それでは、初めて $1 + \phi(m) > n$ となる $m$ はどんな数だろうか．

$$\begin{array}{c|c:c:c:c:c:c:c:c:c} m & 1 & \dot{2} & \dot{3} & 4 & \dot{5} & 6 & \dot{7} & 8 & 9 \\ \hline 1 + \phi(m) & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 5 \end{array}$$

例えば $n = 4$ のとき $m = 7$．ここで $7$ は $4$ 番目の素数である．

一般に、$1 + \phi(m) > n$ は $m = p(n)$ のとき初めて満たす．( $\phi(p(n)) = n$ )

よって、以下のように書き直せる．

$$\left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = \left\{\begin{aligned} &1 \; (m < p(n) \;\xLeftrightarrow{} m\le p(n)-1) \\ &0 \; (m \ge p(n)) \end{aligned}\right.$$

したがって

$$\sum_{m=1}^{2^n} \left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = \underbrace{1 + 1 + \cdots + 1}_{p(n)-1} + 0 + 0 + \cdots + 0 = p(n)-1$$

$$p(n) = 1 + \sum_{m=1}^{2^n} \left\lfloor \sqrt[n]{\frac{n}{1+\phi(m)}} \right\rfloor = \sum_{m=1}^{2^n}\left\lfloor \sqrt[n]{ \begin{gather*} \frac{n}{\sum_{k=1}^m \left\lfloor \cos^2\frac{(k-1)! + 1}{k}\pi\right\rfloor} \end{gather*} }\right\rfloor$$

参考

• 高校数学でわかる素数の一般項
  https://youtu.be/me9nj0M46eM
• log2の値【数値計算】
  https://youtu.be/iJjKji6h1SE
• フェルマーの小定理の証明と例題
  https://manabitimes.jp/math/680
• ウィルソンの定理とその２通りの証明
  https://manabitimes.jp/math/744
• 【(p-1)!≡-1】ウィルソンの定理とその4通りの証明
  https://mathlandscape.com/wilson-theorem/