文書ロック中

この文書は、他のユーザーが編集中のためロックされています。編集が完了するか、ロックの期限が切れるまでお待ち下さい。

文書をロックしているユーザー： 172.69.58.134
ロック期限： 2025/08/05 22:56 (11 min)

この文書は読取専用です。文書のソースを閲覧することは可能ですが、変更はできません。もし変更したい場合は管理者に連絡してください。

===== 素数 =====

素数(prime number)とは、1 より大きい自然数で、正の[[#約数]]が 1 と自分自身のみであるもののこと。特に2以外の素数は奇数であり、奇素数と呼ぶ。\\
1 より大きい自然数で素数でないものは合成数という。

例: 2, 3, 5, 7, 11, 13, ...

素数は無限に存在する

==== 約数 ====

整数 $a \ne 0$ が N の**約数**(divisor)であるとは、
$ \exists b \in \mathbb{Z},\, N = ab $ が成立することである。

N が a で割り切れることを N | a と表す。

2つ以上の整数に共通な約数を**公約数**、公約数のうち最大の数を**最大公約数**という。\\
最大公約数が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}(21, 12) = {gcd}(9, 12) = {gcd}(9, 3) = {gcd}(0, 3) = 3$
==== 素数判定 ====

==== 素因数分解 ====

=== 素因数分解の一意性 ===

2 以上の自然数は、素数の積で表せる。
その表し方は積の順序を除けば一意である。

=== ユークリッドの補題 ===

c が a と互いに素であり、かつ c | ab ならば、c | b である。

=== ベズーの補題 ===

$\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) のベズー係数と呼ばれる。
==== 特殊な素数 ====

=== 双子素数 ===

差が 2 である二つの素数の組。双子素数は無数に存在するかという問題は未解決。

例: (3, 5), (5, 7), (11, 13), ...

==== 未解決問題 ====

=== ゴールドバッハ予想 ===

全ての 3 よりも大きな偶数は2つの素数の和として表すことができる

例: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, ...