初等整数論/素数
本記事では、いよいよ初等整数論の中心的概念というべきであり、様々な問題の源泉でもある、素数について述べる。
素数・合成数

自然数内で考える。1 以外の自然数は次の2つに分類できる。
素数・合成数

前者は合成数といい、後者は素数という。奇数の素数を奇素数という。素数は小さい順から、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... と続いていく。また、合成数を素数のみの積にすることを素因数分解という。
素数・合成数

このとき以下のような疑問が生ずる。
素数・合成数

中には初等的な議論で証明できるものもあるが、多くは難問で現在もよく分かっていないものが多い。
素数・合成数

任意の合成数は素因数分解される。
素数・合成数

証明 最小の合成数 4 は 4 = 2 ⋅ 2 {\displaystyle 4=2\cdot 2} と素因数分解される。仮に n {\displaystyle n} より小さい任意の合成数について定理が成り立っていたとする。すると、定義より n = a b {\displaystyle n=ab} となる。このとき、 a , b < n {\displaystyle a,b<n} だから、これらが素数のときは定理の主張を満たし、合成数の場合素因数分解され、よって n {\displaystyle n} も素因数分解される。
素数・合成数

以上より累積帰納法から、定理が証明される。
素数・合成数

例
素数・合成数

65 = 5 ⋅ 13 {\displaystyle 65=5\cdot 13}
素数・合成数

素数は無限に存在する。(参考 : w:素数が無数に存在することの証明)
素数・合成数

証明 1 仮に素数が有限個だとすると、最大の素数 p {\displaystyle p} が存在する。このとき、全素数をかけあわせ 1 足した数を考える。すなわち、
素数・合成数

q = 2 ⋅ 3 ⋅ 5 ⋯ p + 1 {\displaystyle q=2\cdot 3\cdot 5\cdots p+1}
素数・合成数

このとき、もちろん q > p > 1. {\displaystyle q>p>1.}
素数・合成数

q は合成数ではない。なぜなら、 2 m + 1 {\displaystyle 2m+1} という形をしており、1余るので、 2 {\displaystyle 2} の倍数ではないからである。また同様に、 3 {\displaystyle 3} の倍数でも、 5 , ⋯ p {\displaystyle 5,\cdots p} の倍数でもない。したがって定理 1.10 より、これは素数にほかならない。しかし、これは p {\displaystyle p} の最大性に反する。
素数・合成数

以上より、素数は無限個あると分かる。
素数・合成数

注意 : + 1 ではなく - 1 にしても同様に証明できる。
素数・合成数

証明 2 ( n , n + 1 ) = 1 {\displaystyle (n,n+1)=1} である。なぜなら、仮に ( n , n + 1 ) = g > 1 {\displaystyle (n,n+1)=g>1} ならば、定理 1.1 より g | ( n + 1 ) − n ⟺ g | 1 {\displaystyle g\,|\,(n+1)-n\iff g\,|\,1} となり矛盾するからである。
素数・合成数

よって、適当に数 N 0 > 1 {\displaystyle N_{0}>1} を取ってくる。すると、 N 1 = N 0 ( N 0 + 1 ) {\displaystyle N_{1}=N_{0}(N_{0}+1)} は、互いに素な2数をかけているから、定理 1.10 より少なくとも2つは異なる素因数を持つ。次に、 N 2 = N 1 ( N 1 + 1 ) {\displaystyle N_{2}=N_{1}(N_{1}+1)} とすると、次に述べる算術の基本定理から、少なくとも異なる素因数を3つは持つ。これを繰り返していけばいくらでも素数が生成できる。よって素数は無限に存在する。(循環論法にはなっていない)
素数・合成数

証明 3 フェルマー数 を F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{n}}+1} と定義する。そして、数学的帰納法によって F n = F 1 F 2 F 3 ⋯ F n − 1 + 2 {\displaystyle F_{n}=F_{1}F_{2}F_{3}\cdots F_{n-1}+2} を証明する。
素数・合成数

すると、任意の異なるフェルマー数についてそれらは互いに素である。なぜなら、とある F n , F m {\displaystyle F_{n},F_{m}} について最大公約数が1以上の数 g {\displaystyle g} だったとすると、 n > m {\displaystyle n>m} とすれば F n = F 1 F 2 F 3 ⋯ F m ⋯ F n − 1 + 2 {\displaystyle F_{n}=F_{1}F_{2}F_{3}\cdots F_{m}\cdots F_{n-1}+2} となり、 g {\displaystyle g} は 2を割りきらなければならず、 g > 1 {\displaystyle g>1} より g = 2. {\displaystyle g=2.}
素数・合成数

しかし、フェルマー数は明らかに奇数。よって矛盾を起こし、主張は証明された。
素数・合成数

証明 2 と同様、新しいフェルマー数を考えると先ほどの議論から、異なる素因数を見つけることができる。よって素数は無限に存在する。
素数・合成数

注意 : q = 2 ⋅ 3 ⋅ 5 ⋯ p + 1 {\displaystyle q=2\cdot 3\cdot 5\cdots p+1} の形の数をユークリッド数という。この形の数自体が素数であるとは限らない。たとえば p = 13 {\displaystyle p=13} のとき q = 2 ⋅ 3 ⋅ 5 ⋯ 13 + 1 = 59 ⋅ 509 {\displaystyle q=2\cdot 3\cdot 5\cdots 13+1=59\cdot 509} である。 p = 2 , 3 , 5 , 7 , 11 , 31 , 379 , 1019 , 1021 , 2657 , 3229 , 4547 , 4787 , 11549 , 13649 , 18523 , 23801 , 24029 , 42209 , 145823 , 366439 , 392113 {\displaystyle p=2,3,5,7,11,31,379,1019,1021,2657,3229,4547,4787,11549,13649,18523,23801,24029,42209,145823,366439,392113} のときユークリッド数は素数になることが知られている。素数であるユークリッド数が無限にあるか否か、合成数であるユークリッド数が無限にあるか否か、未だわかっていない。
素数・合成数

同様に、フェルマー数自体が素数であるとは限らない。フェルマーは F 0 = 3 , F 1 = 5 , F 2 = 17 , F 3 = 257 , F 4 = 65537 {\displaystyle F_{0}=3,F_{1}=5,F_{2}=17,F_{3}=257,F_{4}=65537} が素数であることを確かめ、フェルマー数はすべて素数だろうと予想したが、オイラーは F 5 = 4294967297 = 641 ⋅ 6700417 {\displaystyle F_{5}=4294967297=641\cdot 6700417} であることから F 5 {\displaystyle F_{5}} は素数でないことを示した。その後 n = 6 , 7 , 8 , ... , 32 , 36 , 37 , 38 , 39 , 42 {\displaystyle n=6,7,8,\ldots ,32,36,37,38,39,42} など多くの n について F n {\displaystyle F_{n}} が素数でないことが示されている。フェルマー数で素数であるものは 最初の5つしかないと予想されているが、これも未だにわかっていない。
素数・合成数

定理1.11 に書いた通り素数は無限に多くあるが、与えられた数が素数かどうか確かめるにはどのようにすればよいだろうか? 定義によれば素数は 1 とその数自身以外に約数を持たない数である。N の約数は N 自身を除けば N よりは小さいから、2 から N-1 までの数の中に N の約数が1つでもないか確かめればよいことがすぐにわかる。
素数・合成数

さらに、次の事実がわかる。
素数・合成数

実際 N が合成数で N < m < N {\displaystyle {\sqrt {N}}<m<N} の範囲に約数 m を持つとき d = N / m {\displaystyle d=N/m} も N の約数で 1 < d ≤ N {\displaystyle 1<d\leq {\sqrt {N}}} となる。
素数・合成数

したがって、N が素数かどうか確かめるには N {\displaystyle {\sqrt {N}}} までの数のみを確かめれば良い。 しかし、これでも N が大きいときには計算に非常に時間を要するため、素数判定法としては実用的ではない。より高速な素数判定法が求められる。実際、現在では log N の多項式程度の時間で可能な素数判定法が知られている。