この問題のポイントとなるのは 「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は互いに素