「引き算を使わなくても、大差ない」の証明の一例
引き算はなくてもだいたい大丈夫 - 檜山正幸のキマイラ飼育記にて、
もう少し正確に言うと； a > 0, b > 0 に対して、N > 0 があって、次の2つの集合は一致します。
（引用者注：出てくる数字は全部整数という前提）
- { x | x ≧N で、xは、aとbと足し算だけで作り出せる}
- { x | x ≧N で、xは、aとbと足し算／引き算で作り出せる}
（引用時中略）
僕は、なんか持って回った証明しか思いつかなかったんですが、短くて簡略な方法で示せるのかも知れません。興味と時間がある方は考えてみてください。
ユークリッドの互除法に関する知識を使ってよいなら以下の方法で証明できます。簡単のためにaとbが互いに素の場合について考えますが、一般の場合も初めに最大公約数で割っておけば同様にできます。
- 互いに素という仮定から、整数nとmを使ってna+mb=1とできる（ユークリッドの互除法）。nとmのどちらかは正、どちらかは非正なので、対称性よりとりあえずmが非正と仮定して、-mをmと書き直すとna-mb=1、n>0,m>=0となる。
- N=mb(b-1)とおく*1と、N以上の整数xはx=x(na-mb)=(nx)a-(mx)b、とa,bの足し算と引き算で作り出せる。
- 一方、N以上の整数xはx=qb+r、qはm(b-1)以上の整数、rは0からb-1までの整数、と表わせる（割り算の原理）ので、x=qb+r(na-mb)=(rn)a+(q-rm)b、とa,bの足し算だけで作り出せる（rnとq-rmはどちらも0以上なことに注意）。
- よって、上の二つの集合は一致する。
直感的に言えば、整数xに向かってまずはbの足し算だけでできるだけ（b歩ずつ）近づいておいて、あとはそれまでに貯まった「b」と引き換えに一歩ずつ近づいていくわけです。
「一歩ずつ」モードの回数はb-1回あれば足りるので、xが充分大きければ「b歩ずつ」モードの間に充分な数の「b」を貯めておける、という寸法ですね。
・・・もっと簡潔な証明がないものかなぁと思ってしまいますが。特に、ユークリッドの互除法に関する知識を仮定している辺りに不満が残るので、どなたかエレガントな証明をお知りの方はご教示下さいませ。
*1:元記事の問題ではN>0という条件がついているのにこの与え方だとNが0になる場合がある、という点が気になる方は、Nの代わりにN+1を使って以下の部分を読んでください。
