システムメンテナンスのお知らせ

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

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

gooドクター

A 回答 (4件)

まず、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となります。
    • good
    • 1
この回答へのお礼

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

お礼日時:2007/10/18 07:50

この問題のポイントとなるのは


「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以上の整数)と書けます。
以上より○が正しいことが示されました。
証明終
    • good
    • 0

No.1さんの回答はx,yが整数の場合であり、


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

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

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



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

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

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

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

同じです。
    • good
    • 1

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

gooドクター

人気Q&Aランキング