Marriage Theorem 新居 このページをアンテナに追加 RSSフィード

2008年05月21日(Wed)

昨日の話の続編

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


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

以下証明。

  • ai=dbiとおくと、biたちは互いに素な正の整数です。
  • 上の話から、biたち(aiたち)を上手いこと並び替えることで、
    1=c1b1+ … +cjbj-cj+1bj+1- … -cnbn、 ・・・(*)

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

  • biたちの最小値をmとおいて、
    N'=(m-1)(cj+1bj+1+ … +cnbn) ・・・(**)

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

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

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

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

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


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


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

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

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト

コメントを書くには、なぞなぞ認証に回答する必要があります。