整数問題

質問

次のような方程式をユークリッドの互除法で
とくことはできますか？

30x+56y=2000

もし解けるのであれば、詳しい解説をお願いします。

また、このような方程式の問題で、
どのような条件がそろえば、
ユークリッドの互除法を使うことができるのでしょうか？
教えてください

よろしくお願いします

回答No.3

WiredLogic · ベストアンサー

まず、このような方程式が解ける条件ですが、

「自然数a,bに対して、整数x,yを用いて、ax+byの形に書ける最小の自然数は、aとbの最大公約数である」
という定理があります。(長くなるので、証明はパス)

互除法を使うまでもなく^^、30と56の最大公約数=2で、
2000≧2 ですから、この不定方程式には解があります。
(1＜2 なので、30x+56y=1だと、解はないことが解ります)

この方程式を満たす１つの解(x0,y0)が見つかれば、
dをa,bの最大公約数とすると、
一般解は、(x,y) = (x0+(b/d)t, y0-(a/d)t) (tは任意の整数)
のような形で表すことができます。

この１つの解を見つけるのに、a,bに対しての、互除法を使います。

56＞30 なので、
56÷30 = 1 … 26 ⇔ 56 = 30*1 + 26 …(a)
30÷26 = 1 … 4 ⇔ 30 = 26*1 + 4 … (b)
26÷4 = 6 … 2 ⇔ 26 = 4*6 + 2 … (c)
6÷2 = 3 ⇔ 6 = 2*3、
これで、最大公約数が求まりました。ここで、

(c)より、2 = 26 - 4*6、(b)より、4 = 30 - 26*1 ですから、
前の式に、後の式を代入してみます。すると、
2 = 26 - (30 - 26*1)*6 = 26*7 - 6*30 です。
これに、(a)より、26 = 56 - 30*1、を代入してみます。すると、
2 = (56 - 30*1)*7 - 6*30 = 56*7 - 30*13 = 30*(-13) + 56*7、
が出てきます。
(手順としては、割り切れる前の式から、余り＝～という形を作り、
下から順に１つ上を代入、上から順に１つ下に代入、どちらでも
いいのでくりかえしていく、a,bをいじらないようにする、という
のがポイントです)

つまり、30x + 56y = 2 の解の１つは(-13,7)ということです。
これが解れば、#1さんのおっしゃるように、
この解の、x,y両方を1000倍して、(-13000,7000)とすると、
30x + 56y = 2000の解の１つになることは明らかで、
(x,y) = (-13000 + (56/2)t, 7000 - (30/2)t)
= (-13000 + 28t, 7000 - 15t) (tは任意の整数)
と一般解が出てきます。

#2さんが、１つの解として挙げてらっしゃる(20,25)は、
上の解の、t = 465 の場合に相当します。

おそらく、30x + 56y = 2000 だから、
30xと2000は１の位が0なので、56yもそうなるように、
yが5の倍数、y=0,5,10,…を代入していき、
xが整数になる場合を探した結果、だと思いますが、
こういうふうに、試行錯誤ベースでやると、
割と扱いやすい数が出てきやすいのに対し、
(ただ、最悪の場合、チェック回数がかなり多くなることも)

ax+by=何とかの場合を互除法でやると、
最初に見つかるのは。ax+by=a,bの最大公約数の解で、
それを、何倍かして求めるため、何とかが大きくなると、
求まる１つの解が、どうしても大きくなってしまう、
そういうことになってしまいます。

比較的扱いやすい解を求めて、普通はそれほどで
なくても、どうかすると、チェック回数が多くなる
ことを覚悟で、試行錯誤をするか、

扱いにくい解が出るかもしれず、手順が平均的には
長めになることを覚悟で、機械的に解けて、
最悪でも、そこまで手順が長くならない互除法を選ぶか、

どっちが有利かは、ケースバイケースです。

お礼

ありがとうございました
反応がおそくてすいません

回答No.5

alice_44

だから、A No.3 の後半が重要なんだね。

お礼

ありがとうございました
反応がおそくてすいません

回答No.4

mister_moonlight

この手の問題は、特別解を如何に見つけるかがポイントなのに、その特別解の発見をおろそかにした回答なんて何の意味もない。

30x+56y=2000　→　30(x+2y)-4y＝2000。
x+2y＝αとすると　30α-4y＝2000　→　15α-2y＝1000　→　15α＝2(y＋500)
2と15は互いに素から、kを整数として、α＝2k、y＋500＝15k。
よって、x＝-2y＋α＝1000-28k。以上から　(x、y)＝(1000-28k、15k-500)。但し、kは整数。

(注)
一般解の表し方は　一つしかないわけではない。

お礼

ありがとうございました
反応がおそくてすいません

回答No.2

brosisther

30x+56y=2000…(1)を満たすx,yを一つでいいので見つけましょう。
x=20,y=25が一つの解ですので、

30*20+56*25=2000…(2)

となります。
次に(1)-(2)を考えると、

30(x-20)+56(y-25)=0
∴15(x-20)=-28(y-25)

となります。ここで15と28は互いに素ですので、

x-20=28m,y-25=15n（m,nは整数）

とおけます。
よってもとめるx,yはx=28m+20,y=15n+25となります。

お礼

ありがとうございました
反応がおそくてすいません

回答No.1

Tacosan

ユークリッドの互除法で 30 と 56 の最大公約数が 2 であること, そして
30x + 56y = 2
であるような整数 x, y が存在することはわかるはず. そして, それがわかれば
30x+56y=2000
も解ける (1000倍するだけ).

お礼

ありがとうございました
反応が遅くてすいません