素数が無限にあることの証明

【証明】
仮に素数が有限個しかないとすると、
すべての素数をXとして、それらを掛けた数をxとする。
x+1は少なくとも一つの素数で割られる(後で証明する)ので、その素数をpとする。
Xのどの素数についてもx+1は割られないので、pはXにはない。
これはXがすべての素数であることに反する。
したがって、素数は無数にある。 □

自然数nは少なくとも一つの素数で割られることの証明

nが素数の場合には、nで割ればよい。
以下、nは素数でないとする。

【メモ】
ちなみに、自然数とは1以上の整数である。
素数とは自然数nでnと1以外には割られない数である。
aがbで割られること、a=bcであること、bがaの約数であることは同値である。

【証明1】
自然数nは一意に素因数分解されるので、少なくとも一つの素数で割られる。 □

【メモ】
自然数nが一意に素因数分解されることは、算術の基本定理と呼ばれる。
素因数分解とは、自然数nと等しい素数の積を見つけることである。
一意というのは、そのような素数の組が一つに定まるということである。
よく考えると、証明1では一意であることを使っていない。
したがって、次の証明が考えられる。

【証明2】
自然数nが一意に素因数分解されることを用いない。
自然数nにnと1以外の約数があれば、その約数xを一つ取り、同様の操作Tを繰り返す。
操作Tの対象となる約数は、前操作の約数よりも小さくなる。
自然数は下に有限なため、一連の操作はxと1以外に約数のない数を取って終了する。
そのようなxは素数であり、pとする。

次に、自然数nの約数をm、mの約数をlとすると、
n=km、m=k’lより、n=(kk’)lとなり、
lはnの約数となる。
つまり、自然数nの約数の約数は、nの約数でもある。

操作Tは、自然数nの約数を取る操作であったので、
操作Tの繰り返しで取られた素数pはnの約数である。
したがって、自然数nは少なくとも一つの素数pで割られる。 □

公開日:2017/4/19
最終修正日:2017/4/19