計算機科学のブログ

帰納的定義と証明技法 整数論の基本定理、素数の積、帰納法

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第3章(帰納的定義と証明技法)、章末問題の問3.5の解答を求めてみる。

2は素数。

2以上n以下の自然数が 素数、あるいは素数の積であると仮定する。

このとき、

n + 1

が素数ではない場合、 ある自然数

1 < m ≤ n

が存在して、 mは素数または素数の積で、

n + 1

はmで割り切れる。

また、

n + 1 m ≤ n

なので、

n + 1 m ∈ ℕ

は素数または素数の積である。

よって、

n + 1 = m · n + 1 m

は素数の積である。

ゆえに、 帰納法により、 2以上の自然数は素数または素数の積である。

（証明終）