素数
差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| 素数 [2020/11/18 21:04] – kittttttan | 素数 [2022/04/08 21:40] (現在) – 以前のリビジョンを復元 (2020/11/21 17:59) 162.158.106.110 | ||
|---|---|---|---|
| 行 73: | 行 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)$ | ||
| ==== 特殊な素数 ==== | ==== 特殊な素数 ==== | ||
| 行 120: | 行 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$ | ||
| ==== 未解決問題 ==== | ==== 未解決問題 ==== | ||
素数.1605701061.txt.gz · 最終更新: by kittttttan · 文書をロックしているユーザー： 104.23.243.11