素数
差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| 素数 [2020/11/12 22:45] – [素因数分解] 162.158.7.177 | 素数 [2022/04/08 21:40] (現在) – 以前のリビジョンを復元 (2020/11/21 17:59) 162.158.106.110 | ||
|---|---|---|---|
| 行 46: | 行 46: | ||
| ==== 素数判定 ==== | ==== 素数判定 ==== | ||
| + | |||
| + | === 決定的素数判定法 === | ||
| + | |||
| + | == 試し割り法 == | ||
| + | |||
| + | == エラトステネスの篩 == | ||
| + | |||
| + | == AKS素数判定法 == | ||
| + | |||
| + | === 確率的素数判定法 === | ||
| + | |||
| + | == フェルマーテスト == | ||
| + | |||
| + | == ミラー–ラビン素数判定法 == | ||
| + | |||
| ==== 素因数分解 ==== | ==== 素因数分解 ==== | ||
| 行 51: | 行 66: | ||
| **素因数分解**(prime factorization)とは、ある正の整数を素数の積の形で表すことである。1 の素因数分解は 1 とする。 | **素因数分解**(prime factorization)とは、ある正の整数を素数の積の形で表すことである。1 の素因数分解は 1 とする。 | ||
| - | 例 $12 = 2^2 \times 3$ | + | 例: $12 = 2^2 \times 3 \hspace{2em} 123 = 3 \times 41$ |
| === 素因数分解の一意性 === | === 素因数分解の一意性 === | ||
| 行 57: | 行 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)$ | ||
| ==== 特殊な素数 ==== | ==== 特殊な素数 ==== | ||
| 行 64: | 行 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, ... | ||
| + | |||
| + | === レピュニット素数 === | ||
| + | |||
| + | レピュニットとは全ての桁の数字が1である自然数のこと。 | ||
| + | |||
| + | 例: $R_1 = 1, R_2 = 11, R_3 = 111, ...$ | ||
| + | |||
| + | 10進法におけるレピュニットは $R_n = \frac{10^n - 1}{9}$ で表される。2進法におけるレピュニットはメルセンヌ数である。 | ||
| + | |||
| + | レピュニット数が素数であるとき、**レピュニット素数**という。 | ||
| === メルセンヌ素数 === | === メルセンヌ素数 === | ||
| 行 80: | 行 137: | ||
| $M_{p} \not \mid S_{k}\ (0 \leq k \leq p - 2) => M_p は合成数$\\ | $M_{p} \not \mid S_{k}\ (0 \leq k \leq p - 2) => M_p は合成数$\\ | ||
| $M_{p} \mid S_{p-2} => M_p は素数$ | $M_{p} \mid S_{p-2} => M_p は素数$ | ||
| + | |||
| + | === フェルマー素数 === | ||
| + | |||
| + | フェルマー数 $F_n = 2^{2^n} + 1 \; (n \in \mathbb{Z}, \, n \geq 0)$ | ||
| + | |||
| + | 素数であるフェルマー数を**フェルマー素数**という。 | ||
| + | |||
| + | 例: 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$ | ||
| + | |||
| ==== 未解決問題 ==== | ==== 未解決問題 ==== | ||
素数.1605188739.txt.gz · 最終更新: by 162.158.7.177 · 文書をロックしているユーザー： 104.23.243.11