Question

ひろみちこ

(3)の解説お願いします🤲

答えは(x,y)=(20,11)です。

553.次の不定方程式を満たす自然数の組(x, y)をすべて求めよ
(2) 3x+4y=30
*1) 3x+7y=28
(3) 77x+20y=1760
6-

Answer 1

✨ ベストアンサー ✨

ブドウくん

合同式を知っていれば合同式を使うのがはやいです。
77x+20y=1760について
20を法として
77x≡1760(mod20)
17x≡0(mod20)
17と20は互いに素なので
x=20kとなります。
77×20k+20y=1760
両辺を20で割ると
77k+y=88
k=1のときy=11
k=2以上のときyは負の数なので
答えは(20,11)

ひろみちこ

回答ありがとうございます。
合同式は知っていますが、この問題を合同式で解いたことがないので、できればユークリッドの互助法を用いる方法が知りたいです🙇‍♀️

ブドウくん

僕は普段から解を見つけるときにユークリッドは使わずに合同式を使う人なので、普段はこのやり方をしていません。それから、自然数が解であると決まっているので、この方法をとるのも無駄です。
77x+20y=1760
77x=1760-20y
77x=20(88-y)
77と20が互いに素なので88-yは77の倍数であり、88-y=77kと置けて、y=11(8-7k)ですね。y>0よりk=1のときが答えです。
ですが、せっかくなのでユークリッドの互除法でやりますね。詳しい解き方の説明は下の動画を見てください。
https://youtu.be/OcrieXuZ2gg

写真の通り、ユークリッドの互除法により
①77-20×3=17
②20-17×1=3
③17-3×5=2
④3-2×1=1
となります。
77=a, 20=bとおくと
①a-3b=17
②の17に①を代入し
②b-(a-3b)=3
簡単にすると-a+4b=3で、これを③に代入し
③(a-3b)-5(-a+4b)=2
6a-23b=2
同様に
④(-a+4b)-(6a-23b)=1
-7a+27b=1
したがってaとbをもとに戻すと
-7×77+27×20=1
つまり
77×(-7)+20×(27)=1となります。
これより
77×(-7×1760)+20×(27×1760)=1760
数字だけで寒気がしますが、ここからは仕方ないので頑張ってやりましょう。
(-7×1760)=p, 27×1760=qとおけば
77(x-p)=-20(y-q)
77と20が互いに素であるから
x-p=20k
x=20k+p
=20k+1760×7
=20(k+88×7)
k+88×7=k'とおくと
x=20k'となり、k'=1のときx=20でちょうど条件を満たします。
あとはx=20を入れてやればよいです。

ひろみちこ

ありがとうございます😭😭
助かりました。

Answer 2

なゆた

頭のいい人たちの会話にはついていけぬ
(1)(2)も互除法や合同式とやらで探すのかな？
この問題限定の中学生レベルの探し方でいいなら。

x,yは自然数なので
大きい方の77で1760を割ると22余りいくつか
22個も整数解探すの大変ですが
もう一つの答は20の倍数

77の倍数+20の倍数で1760を作ればいいのだから
77の倍数は10の倍数(もっといえば20の倍数)ということ

よって77×20+20×11の1組だけ、とわかる

合同式というのはなんか面白そう。
ちょっと勉強してみます

ひろみちこ

回答ありがとうございます🌟

Answer 3

アイス

77x+20y=1760を満たす解の1つは(x,y)=(20,11)であるので
77(x−20)+20(y−11)=0
77(x−20)=−20(y−11)
77と20は互いに素であるので
x−20=20k (kは整数)
x=20k+20
y=−77k+11

x,yが自然数の時はk=0の時のみなので
(x,y)=(20,11)

おそらく最初の解を見つけることが困難だと思うので、ユークリッドの互除法を活用するのがいいと思います。活用の仕方は説明すると長くなるのでYouTubeかなんかで調べてください。

ひろみちこ

回答ありがとうございます🌟