昨日の話の続編

昨日の話の続きで、「二つだけじゃなくn個の正整数について同様の方法を知りたい」とのことですので、昨日の方法をn個の場合に一般化してみます。

a₁,...,a_nを正の整数、dをそれらの最大公約数とすると、ユークリッドの互除法により「a₁,...,a_nから足し算と引き算で作れる数の全体」はdの倍数全体に等しい*1ので、証明すべきは「ある整数Nがあって、N以上のdの倍数は全てa₁,...,a_nの足し算だけで作れる」ことです。
以下証明。

• a_i=db_iとおくと、b_iたちは互いに素な正の整数です。
• 上の話から、b_iたち（a_iたち）を上手いこと並び替えることで、
  1=c₁b₁+ … +c_jb_j-c_j+1b_j+1- … -c_nb_n、　・・・（＊）
  

ただしc_iたちは全て0以上の整数、と書けます。

• b_iたちの最小値をmとおいて、
  N'=(m-1)(c_j+1b_j+1+ … +c_nb_n)　・・・（＊＊）
  

とおきます。また、b_k=mとなるkを決めておきます。

• すると、N'以上の整数は、N'+qb_k+r、qは0以上の整数、rは0からb_k-1までの整数、という形に表わせますので（N'を引いてからb_kで割り算すればよい）、そこに式（＊）（の両辺をr倍したもの）と（＊＊）を代入すると、b_iたちの整数倍の和、という形の式が出てきます。ここで各b_iの係数を見てみると、
  • iが1からjまでのときは、係数はrc_i（i=kなら、さらにqを足した数）で、これは0以上の整数
  • iがj+1からnまでのときは、係数は(m-1)c_i-rc_i=(m-1-r)c_i（i=kなら、さらにqを足した数）で、rとmの取り方からこれも0以上の整数

となり、確かにb_iたちの足し算だけで表わせています。

• 最後に、N=N'dとおけば、上の結果からN以上のdの倍数は全てa_iたちの足し算だけで表わることがわかります。

昨日のような比喩を使うと、まずN'というベースキャンプまで進んでおいて、そこからm歩ずつ接近していき（この過程で「b_i」たちは減らない）、残りを一歩ずつ進んで行く（多くてもm-1回で済む）のですが、N'まで進む間に最後のステップで必要な分の「b_i」たちが貯まっているのでOK、という寸法です。mをb_iたちの最小値としているのは、最後のステップの回数をできるだけ減らしたいからです。

もっと真面目に考えるとNの値は更に減らせる気もしますが、時間の関係でそこまでは考えません。

引き続き、エレガントな解答を募集中です。

*1:最も難しい点はdを作れることの証明ですが、「a₁,...,a_n-1の最大公約数」とa_nの最大公約数はdになるので、整数二つの場合（通常のユークリッドの互除法）から始めて帰納的に証明できます。