この問題のポイントとなるのは 「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は互いに素
![ax + by (a,bは自然数で互いに素、x,yは自然数)](https://cdn-ak-scissors.b.st-hatena.com/image/square/7c62d28777cb1c971ce08d0679b025d4a0a53357/height=288;version=1;width=512/https%3A%2F%2Foshiete.xgoo.jp%2Fimages%2Fsp%2Fqa_recommend%2F2063_3.jpg)