方程式

質問

以前も質問したのですが、よくわからなくて、教えてください。

等式11x-97y=1をみたす整数x,yがある。|x-y|の最小値を求める方法

Ｅｕｃｌｉｄの互除法より求めると早いときいたのですが、調べたのですが難しくてよくわかりません。

他に、簡単に求める方法がありましたらおしえていただけないでしょうか？

答は
39(x=-44＋97t,y=-5＋11ｔ（tは整数のとき）
よろしくお願いします

回答No.4

kony0

Step1. まず割ってみる。
97÷11=8…9
11÷9=1…2
9÷2=4…1

Step2. 上の割算を、A=BQ+Rの形で表現すると
97=11*8+9...(*1)
11=9*1+2...(*2)
9=2*4+1...(*3)

Step3. 与えられた式の係数に、Step2.の式を適用する。
(START)11x-97y=1
((*1)を適用)11x-(11*8+9)y=1
11(x-8y)-9y=1
ここで、x-8y=Aとおく。(11A-9y=1)

これに(*2)を適用：(9*1+2)A-9y=1
9(A-y)+2A=1
ここで、A-y=Bとおく。(9B+2A=1)

これに(*3)を適用：(2*4+1)B+2A=1
2(4B+A)+B=1

さて、4B+A=kとおくと、2k+B=1⇒B=-2k+1
（4B+A=kだから）A=k-4B=9k-4
（A-y=Bだから）y=A-B=11k-5
（x-8y=Aだから）x=A+8y=97k-44

ということで、(x,y)=(97k-44,11k-5)がいえます。

x,yがいずれも整数であることから、A,B,kはいずれも整数であることが言えます。
また逆にkが整数であるならばx,yがいずれも整数であることも言えます。

ということで、kは任意の整数をとることも言えます。

回答No.3

keyguy

代入はできたのですが、どうやってまとめるのかわかりません。:
97と11が係数として残るようにまとめる

の２つの式はどうやってでたのですか？：
(6)は先にまとめた結果
(7)は問題文から
(ただしxはかけるに使ったのでxをaにyをbとした)

「(2)を2=の形にしてそれを(3)'に代入して」は
「(2)'を2=の形にしてそれを(3)'に代入して」の間違いです

(a+44)x11=(b+5)x97・・・(8)
97が11を因子に持たないからkを整数として
とはどんな意味ですか？：
右辺は97で割れるから左辺が97で割れ(a+44)は97で割れると書きなおしてください
だから(9)が成り立つのです

回答No.2

keyguy

97=11x8+9・・・(1):97を11で割ると商8余り11
11=9x1+2・・・(2):11を9で割ると商1余り2
9=2x4+1・・・(3):9を2で割ると商4余り1
(1)を9=の形にしてそれを(2)に代入して(2)'を得
(1)を9=の形にしてそれを(3)に代入して(3)'を得
(2)を2=の形にしてそれを(3)'に代入して
5x97-44x11=1・・・(6)となる
11xa-97xb=1=1・・・(7)とすると
(6)-(7)より
(a+44)x11=(b+5)x97・・・(8)
97が11を因子に持たないからkを整数として
a+44=97xk・・・(9)
と置ける
これを(8)に代入して
11xk=b+5・・・(10)
を得る
すなわち
a=97xk-44
かつ
b=11xk-5

補足

また、質問してすいません。
いろいろとHPでユークリッドの互除法
を調べたのですがむずかしいですね。

だんだん、頭がおかしくなってきて、だんだんわからなくなってしまいました。
独学でやっているので、難しいです。
もうすこし、初心者的におしえてもらってもいいですか？

(1)を9=の形にしてそれを(2)に代入して(2)'を得
(1)を9=の形にしてそれを(3)に代入して(3)'を得
(2)を2=の形にしてそれを(3)'に代入して

代入はできたのですが、どうやってまとめるのかわかりません。
できれば、代入してどのような形にまとめるかわかりません

5x97-44x11=1・・・(6)となる
11xa-97xb=1=1・・・(7)とすると

の２つの式はどうやってでたのですか？
(6)-(7)より
(a+44)x11=(b+5)x97・・・(8)
97が11を因子に持たないからkを整数として
とはどんな意味ですか？
できれば、例をつけておしえてください
a+44=97xk・・・(9)
と置ける
どうしてですか？

回答No.1

keyguy

97=11x8+9
11=9x1+2
9=2x4+1
すなわち
9-2x4=1
2=11-9x1
9=97-11x8
よって
(97-11x8)-2x4=1
2=11-(97-11x8)x1
よって
(97-11x8)-(11-(97-11x8)x1)x4=1
よって
5x97-44x11=1
後は至極簡単ですね?

補足

すいません。
よくわかりません。
もう少し、具体的におしえてください