素数
差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| 素数 [2020/11/18 21:03] – [双子素数] kittttttan | 素数 [2022/04/08 21:40] (現在) – 以前のリビジョンを復元 (2020/11/21 17:59) 162.158.106.110 | ||
|---|---|---|---|
| 行 67: | 行 67: | ||
| 例: $12 = 2^2 \times 3 \hspace{2em} 123 = 3 \times 41$ | 例: $12 = 2^2 \times 3 \hspace{2em} 123 = 3 \times 41$ | ||
| + | |||
| === 素因数分解の一意性 === | === 素因数分解の一意性 === | ||
| 行 72: | 行 73: | ||
| その表し方は積の順序を除けば一意である。 | その表し方は積の順序を除けば一意である。 | ||
| + | === メビウス関数 === | ||
| + | |||
| + | $n \in \mathbb{N}, | ||
| + | \begin{eqnarray} | ||
| + | \mu(n) = \left\{ \begin{array}{ll} | ||
| + | ０ & (n が平方因子を持つとき) \\ | ||
| + | (-1)^k & (n が相異なる k 個の素因数に分解されるとき) \\ | ||
| + | \end{array} \right. | ||
| + | \end{eqnarray}$ | ||
| + | |||
| + | == 基本公式 == | ||
| + | |||
| + | $\begin{eqnarray} | ||
| + | \sum_{d \mid n} \mu(d) = \left\{ \begin{array}{ll} | ||
| + | 1 & (n = 1) \\ | ||
| + | 0 & (n \neq 1) \\ | ||
| + | \end{array} \right. | ||
| + | \end{eqnarray}$ | ||
| + | |||
| + | == 反転公式 == | ||
| + | |||
| + | $\forall n \in \mathbb{N}, | ||
| + | g(n) = \sum_{d \mid n} f(d) | ||
| + | <=> | ||
| + | f(n) = \sum_{d \mid n} \mu(d) g(n/d)$ | ||
| ==== 特殊な素数 ==== | ==== 特殊な素数 ==== | ||
| 行 79: | 行 105: | ||
| 例: (3, 5), (5, 7), (11, 13), ... | 例: (3, 5), (5, 7), (11, 13), ... | ||
| + | |||
| + | === オイラー素数 === | ||
| + | |||
| + | $n^2 + n + 41$ の素数。$0 \leq n \leq 39$ではすべて素数。 | ||
| + | |||
| + | 例: 41, 43, 47, 53, 61, 71, ... | ||
| === レピュニット素数 === | === レピュニット素数 === | ||
| 行 89: | 行 121: | ||
| レピュニット数が素数であるとき、**レピュニット素数**という。 | レピュニット数が素数であるとき、**レピュニット素数**という。 | ||
| - | === オイラー素数 === | ||
| - | $n^2 + n + 41$ の素数。$0 \leq n \leq 39$ではすべて素数。 | ||
| - | |||
| - | 例: 41, 43, 47, 53, 61, 71, ... | ||
| === メルセンヌ素数 === | === メルセンヌ素数 === | ||
| 行 117: | 行 145: | ||
| 例: 3, 5, 17, 257, 65537 | 例: 3, 5, 17, 257, 65537 | ||
| + | |||
| + | ==== 素数計数関数 ==== | ||
| + | |||
| + | 正の実数にそれ以下の素数の個数を対応させる関数 | ||
| + | |||
| + | $\pi(N) = \pi({\sqrt{N}}) - 1 + \sum_{d} \mu(d) \left[{\frac{N}{d}}\right]$\\ | ||
| + | $\mu(d)$ はメビウス関数、$[x]$ はガウス記号、和は √N 以下のすべての素数の積 P のすべての正の約数 d を動く | ||
| + | |||
| + | この式から | ||
| + | $\lim_{x \to \infty} {\frac{\pi(x)}{x}} = 0$ | ||
| + | |||
| + | === 素数定理 === | ||
| + | |||
| + | $\lim_{x \to \infty}{\frac{\pi(x)}{x / \operatorname{ln} x}} = 1$ | ||
| + | |||
| ==== 未解決問題 ==== | ==== 未解決問題 ==== | ||
素数.1605701007.txt.gz · 最終更新: 2020/11/18 21:03 by kittttttan · 文書をロックしているユーザー： 108.162.241.90