math

素数(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(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) \Rightarrow \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 である。

素因数分解(prime factorization)とは、ある正の整数を素数の積の形で表すことである。1 の素因数分解は 1 とする。

例: $12 = 2^2 \times 3 \hspace{2em} 123 = 3 \times 41$

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

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

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

メルセンヌ数(Mersenne number) $M_n = 2^n - 1 \; (n \in \mathbb{N})$

素数であるメルセンヌ数をメルセンヌ素数という。

例: 3, 7, 31, 127, 8191, …

$M_n が素数 \Rightarrow 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) \Rightarrow M_p は合成数$
$M_{p} \mid S_{p-2} \Rightarrow M_p は素数$

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

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