差分

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

--- 素数 [2020/11/21 23:41] – kittttttan
+++ 素数 [2022/04/08 21:40] (現在) – 以前のリビジョンを復元 (2020/11/21 17:59) 162.158.106.110
@@ 行 20: / 行 20: @@
 公約数は最大公約数の約数である。
-$\forall a, \forall b \in \mathbb{N},\, \gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab$
+$$\forall a, \forall b \in \mathbb{N},\, {gcd}(a, b)\cdot \operatorname {lcm}(a, b) = ab$$
 最大公約数の計算法として[[#ユークリッドの互除法]]がある。
@@ 行 26: / 行 26: @@
 === ユークリッドの互除法 ===
-割って余りを取るという操作。\\
+割って余りを取るという操作。
-$a, b \in \mathbb{N} \,(a \geq b) に対して a を b で割った余りを r とすると \gcd(a, b) = \gcd(b, r)$
+$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$
+例: $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}}}$
@@ 行 37: / 行 37: @@
 === ベズーの補題 ===
-$\forall a, \forall b \in \mathbb{Z} \setminus \{0\},\; d = \gcd(a, b) => \exists x, \exists y \in \mathbb{Z}: ax + by = d$\\
+$\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) のベズー係数と呼ばれる。
@@ 行 44: / 行 44: @@
 c が a と互いに素であり、かつ c | ab ならば、c | b である。
+==== 素数判定 ====
+=== 決定的素数判定法 ===
+== 試し割り法 ==
+== エラトステネスの篩 ==
+== AKS素数判定法 ==
+=== 確率的素数判定法 ===
+== フェルマーテスト ==
+== ミラー–ラビン素数判定法 ==
 ==== 素因数分解 ====
@@ 行 60: / 行 77: @@
 $n \in \mathbb{N},
 \begin{eqnarray}
-\mu(n) := \left\{ \begin{array}{ll}
+\mu(n) = \left\{ \begin{array}{ll}
- & (n が平方因子を持つとき) \\
+０ & (n が平方因子を持つとき) \\
 (-1)^k & (n が相異なる k 個の素因数に分解されるとき) \\
 \end{array} \right.
@@ 行 81: / 行 98: @@
 <=>
 f(n) = \sum_{d \mid n} \mu(d) g(n/d)$
-==== 素数判定 ====
-=== 決定的素数判定法 ===
-== 試し割り法 ==
-== エラトステネスの篩 ==
-== AKS素数判定法 ==
-=== 確率的素数判定法 ===
-== フェルマーテスト ==
-== ミラー–ラビン素数判定法 ==
 ==== 特殊な素数 ====
@@ 行 124: / 行 124: @@
 === メルセンヌ素数 ===
-メルセンヌ数(Mersenne number) $M_n := 2^n - 1 \; (n \in \mathbb{N})$
+メルセンヌ数(Mersenne number) $M_n = 2^n - 1 \; (n \in \mathbb{N})$
 素数であるメルセンヌ数を**メルセンヌ素数**という。
@@ 行 140: / 行 140: @@
 === フェルマー素数 ===
-フェルマー数 $F_n := 2^{2^n} + 1 \; (n \in \mathbb{Z}, \, n \geq 0)$
+フェルマー数 $F_n = 2^{2^n} + 1 \; (n \in \mathbb{Z}, \, n \geq 0)$
 素数であるフェルマー数を**フェルマー素数**という。
@@ 行 158: / 行 158: @@
 === 素数定理 ===
-$\lim_{x \to \infty}{\frac{\pi(x)}{x / \ln x}} = 1$
+$\lim_{x \to \infty}{\frac{\pi(x)}{x / \operatorname{ln} x}} = 1$
 ==== 未解決問題 ====