ax + by (a,bは自然数で互いに素、x,yは自然数)

質問

a,bは自然数で互いに素であるとき，
　ax + by (x,yは自然数)
の形で表せない自然数の個数は
いくつになるのでしょうか？

x,yを0以上の整数に変更するとどうなるのでしょうか？

回答No.5

yoikagari · ベストアンサー

まず、ax+by(x,yは0以上の整数)の形で表せない自然数を考えます。
○よりab-a-bより大きな自然数は必ずax+by(x,yは0以上の整数)の形で表せますから、ab-a-b以下の自然数を考えればよいことがわかります。
あとは、aiueo95240さんの言うとおりの方法で、求める答えは(a-1)(b-1)/2となることがわかります。

次に、ax+by(x,yは自然数)の形で表せない自然数を考えます。
※よりabより大きな自然数は必ずax+by(x,yは自然数)の形で表せますから、ab以下の自然数を考えればよいことがわかります。
求める自然数は、上記のax+by(x,yは0以上の整数)の形で書けない自然数とa，2a，・・・，(b-1)a，b，2b，・・・，(a-1)b，abだから
求める答えは、(a-1)(b-1)/2+(a-1)+(b-1)+1=(ab+a+b-1)/2となります。

お礼

みなさま、ありがとうございます。
よくわかりました。

回答No.4

yoikagari

この問題のポイントとなるのは
「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以上の整数)と書けます。
以上より○が正しいことが示されました。
証明終

回答No.2

oldperson

No.1さんの回答はx,yが整数の場合であり、
質問者はx,yが自然数の場合を質問しているので
かみ合っていないと思います。
また、質問者はa,bを互いに素と規定しているので
a,bの最大公約数を持ち出すのはあまり意味がありません。

ヒント
a,bは互いに素なのでab以上の自然数はすべて
ax+by
の形で表せます。

回答No.1

take_5

フェルマーの小定理から、

整数係数のx,yの一次方程式：ax + by ＝cは、cがaとbの最大公約数の倍数の時に解を持ち、又、解を持つのはそのときに限る。

というのがあります。
ですから、
＞の形で表せない自然数の個数はいくつになるのでしょうか？

cがそのような条件を満たさなければいいんですから、その個数は定まりません。

＞x,yを0以上の整数に変更するとどうなるのでしょうか？

同じです。