初等整数論をやらなきゃいかん,と決意して勉強し始めたところ,除法の原理の証明で行き詰った.
定理.(除法の原理)
自然数 に対して
を満たす整数 が存在する.ただし である.
ネットで検索したら,この証明はペアノの公理から始めて,最小値原理を認めなければ証明できないようだ.
最小値原理
自然数の集合の部分集合には最小値が存在する.□
何より知らなかったのは最小値原理と数学的帰納法が同値であることだ.
したがっていずれか一方を認めなければならない,というわけだ.
数学的帰納法から最小値原理を証明する.
感覚的には次のようにして証明できると考えられる.
集合を自然数の集合の部分集合とする.
まず,が集合に属するか否かを調べ,属していれば最小値となる.
属していない場合はが属するか調べる.
以下繰り返し,初めて属している元が現れたときそれが最小元となる.
ここの繰り返し,の部分にあいまいさが残っている.