差分

このページの2つのバージョン間の差分を表示します。

--- 素数 [2020/11/11 20:42] – 作成 kittttttan
+++ 素数 [2022/04/08 21:40] (現在) – 以前のリビジョンを復元 (2020/11/21 17:59) 162.158.106.110
@@ 行 1: / 行 1: @@
 ===== 素数 =====
-素数(prime number)とは、1 より大きい自然数で、正の[[#約数]]が 1 と自分自身のみであるもののこと。\\
+**素数**(prime number)とは、1 より大きい自然数で、正の[[#約数]]が 1 と自分自身のみであるもののこと。特に2以外の素数は奇数であり、**奇素数**と呼ぶ。\\
-より大きい自然数で素数でないものは合成数という。
+より大きい自然数で素数でないものは**合成数**という。
 例: 2, 3, 5, 7, 11, 13, ...
@@ 行 10: / 行 10: @@
 ==== 約数 ====
-整数 $a \ne 0$ が N の約数であるとは、
+整数 $a \ne 0$ が N の**約数**(divisor)であるとは、
-$ \exists b \in \mathbb{Z},\, N = ab $ が成立することである
+$ \exists b \in \mathbb{Z},\, N = ab $ が成立することである。
+N が a で割り切れることを N | a と表す。
+つ以上の整数に共通な約数を**公約数**、公約数のうち最大の数を**最大公約数**という。\\
+最大公約数が1であるような2つ以上の整数の組は、**互いに素**であるという。
+公約数は最大公約数の約数である。
+$$\forall a, \forall b \in \mathbb{N},\, {gcd}(a, b)\cdot \operatorname {lcm}(a, b) = ab$$
+最大公約数の計算法として[[#ユークリッドの互除法]]がある。
+=== ユークリッドの互除法 ===
+割って余りを取るという操作。
+$a, b \in \mathbb{N} (a >= b) に対して a を bで割った余りを r とすると gcd(a, b) = gcd(b, r)$
+n と m (n > m) の最大公約数を求める際のユークリッドの互除法の割り算の商は、有理数 n/m の連分数展開になっている。
+例: $gcd(286, 77) = gcd(55, 77) = gcd(55, 22) = gcd(11, 22) = gcd(11, 0) = 11$
+$\frac{286}{77} = 3 + \frac{55}{77} = 3 + \frac{1}{\frac{77}{55}} = 3 + \frac{1}{1 + \frac{22}{55}} = 3 + \frac{1}{1 + \frac{1}{\frac{55}{22}}} = 3 + \frac{1}{1 + \frac{1}{2 + \frac{11}{22}}} = 3 + \frac{1}{1 + \frac{1}{2 + \frac{1}{\frac{22}{11}}}} = 3 + \frac{1}{1 + \frac{1}{2 + \frac{1}{2}}}$
+=== ベズーの補題 ===
+$\forall a, \forall b \in \mathbb{Z} \setminus \{0\},\; d = gcd(a, b) => \exists x, \exists y \in \mathbb{Z}: ax + by = d$\\
+d は ax + by と書ける最小の正の整数であり、ax + by の形のすべての整数は d の倍数である。
+x と y は (a, b) のベズー係数と呼ばれる。
+=== ユークリッドの補題 ===
+c が a と互いに素であり、かつ c | ab ならば、c | b である。
 ==== 素数判定 ====
+=== 決定的素数判定法 ===
+== 試し割り法 ==
+== エラトステネスの篩 ==
+== AKS素数判定法 ==
+=== 確率的素数判定法 ===
+== フェルマーテスト ==
+== ミラー–ラビン素数判定法 ==
 ==== 素因数分解 ====
+**素因数分解**(prime factorization)とは、ある正の整数を素数の積の形で表すことである。1 の素因数分解は 1 とする。
+例: $12 = 2^2 \times 3 \hspace{2em} 123 = 3 \times 41$
+=== 素因数分解の一意性 ===
+以上の自然数は、素数の積で表せる。
+その表し方は積の順序を除けば一意である。
+=== メビウス関数 ===
+$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}
+& (n = 1) \\
+& (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)$
 ==== 特殊な素数 ====
 === 双子素数 ===
-差が 2 である二つの素数の組。双子素数は無数に存在するかという問題は未解決。
+**双子素数**とは、差が 2 である二つの素数の組。双子素数は無数に存在するかという問題は未解決。
 例: (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, ...$
+進法におけるレピュニットは $R_n = \frac{10^n - 1}{9}$ で表される。2進法におけるレピュニットはメルセンヌ数である。
+レピュニット数が素数であるとき、**レピュニット素数**という。
+=== メルセンヌ素数 ===
+メルセンヌ数(Mersenne number) $M_n = 2^n - 1 \; (n \in \mathbb{N})$
+素数であるメルセンヌ数を**メルセンヌ素数**という。
+例: 3, 7, 31, 127, 8191, ...
+$M_n が素数 => n も素数$
+== リュカ–レーマー・テスト ==
+p が奇素数のとき、$S_0 = 4, S_n = S_{n − 1}^2 − 2 \; (n \geq 1)$ と定義すると、\\
+$M_{p} \not \mid S_{k}\ (0 \leq k \leq 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$
 ==== 未解決問題 ====