質問: ax + by (a,bは自然数で互いに素、x,yは自然数) a,bは自然数で互いに素であるとき, ax + by (x,yは自然数) の形で表せない自然数の個数は いくつになるのでしょうか? x,yを0以上の整数に変更するとどうなるのでしょうか?
回答: この問題のポイントとなるのは 「abより大きい自然数kは、k=ax+by(ただしx,yは自然数) と書けること」・・・※ と 「ab-a-bより大きい自然数hは、h=ax+by(ただしx,yは0以上の整数) と書けること」・・・○ です。 まず、※の 「abより大きな自然数kはk=ax+by(ただしx,yは自然数)とか書けること」を証明します。 証明 b個の数k-a,k-2a,・・・,k-abの中に、bで割り切れる数が存在することを証明します。・・・● ●が成立しないと仮定します。 k-a,k-2a,・・・,k-abのをbで割った余りはb-1通りしかないので、これらの中にbで割ったときの余りが等しい2数が必ず存在します。 その2数をk-ua,k-vaとします。 (ただし、u,vは0<u<v≦bなる自然数) このとき(k-ua)-(k-va)=(v-u)aはbで割り切れる。 aとbは互いに素だから、v-uがbで割り切れることになる。 しかし、0<v-u<bだから不合理 よって、●が成立します。 つまり、k-a,k-2a,・・・,k-abの中にbで割り切れる数が存在します。 それをk-saとします。 (ただし、sは0<s≦bなる自然数) k-sa=bt(ただし、tは整数)と書けます。 bt=k-sa>k-ab>0よりt>0となります。 以上よりk=as+bt(s,tは自然数)と書けます。 よって、※が正しいことが示されました。 証明終 次に○の 「ab-a-bより大きな自然数hはk=ax+by(ただしx,yは自然数)とか書けること」を証明します。 証明 h+a+b>abだから、※より h+a+b=am+bn(m,nは自然数)と書けます。 したがって、h=a(m-1)+b(n-1) (m-1,n-1は0以上の整数)と書けます。 以上より○が正しいことが示されました。 証明終