次: 離散的写像の不動点定理 上: 存在の証明 前: 存在の間接証明−鳩の巣論法

最小自然数の存在

さらにまた高校数学でやや高度な論証に用いられるのが 「$A$ を自然数の部分集合とする． $A$ には最小の要素が存在する．」という事実である． これは自然数の性質に基づくものであり，数学的帰納法の根拠となるものであった．

自然数の部分集合に最小の要素が存在すること自体は証明なしに使ってもよい． その例は先にあげた一次不定方程式の整数解の存在定理の別証明だ． 例題1.18の(4)は次のように(3)を用いず直接に示すことができる．

$a,\ b$ が互いに素なとき， $am+bn=1$ に解が存在することの別証明

$$J=\{am+bn \, \vert \, m , n は整数 \}$$

と置く． $J$ は整数の集合の部分集合であり， $J$ の要素のうち正のもの全体は自然数の集合の部分集合であるから， $J$ の要素のなかで正で最小のものが存在する． それを $am_0+bn_0$ とする．

このとき，$J$ の任意の要素 $am+bn$ は $am_0+bn_0$の倍数であることを示す． $am+bn$ を $am_0+bn_0$ で割り, その除法の式を

$$am+bn=(am_0+bn_0)q+r$$

とする. ただし, $am_0+bn_0>r\ge 0$ である. $r=a(m-m_0q)+b(n-n_0q)$ であるから,

$$r\in J$$

ここでもし $r\ne 0$ なら $r$ が $am_0+bn_0$ より小さい $J$ の正の要素になる． これは$am_0+bn_0$ が正で最小の要素であることに反する．ゆえに$r=0$ でなければならない. つまり, $J$ の要素はすべて $am_0+bn_0$ の倍数である. ところで,

$$a=a\cdot 1+b\cdot 0\in J ,\quad b=a\cdot 0+b\cdot 1\in J$$

であるから, $a$ も $b$ も $am_0+bn_0$ の倍数である. ところが, $a,\ b$ は互いに素であるから, $am_0+bn_0=1$ でなければならない. つまり $am+bn=1$ に整数解 $(m,\ n)=(m_0，n_0)$ が存在した． □

このように $am+bn=1$ に整数解 が存在することが二つの方法で示された． 実はさらに$a$や$b$についての数学的帰納法でも可能である． それはぜひ試みてほしい．