数学の問題

質問

すいません。
全然わからなくて、どこから考えていいのか全然わかりません

35x-151y=1 ｘ、ｙは整数とすします。
(1)一般解を求めます
(2)|x＋y|の最小値とそのときのx,yの値はどうやってもとめるのですか？

参考書によると

(1)151=35×4＋11 …(1)
　35=11×3＋2 …(2)
　11=2×5＋1 …(3)

この式はどこからでるのでてきたのでしょうか？

そして、
(3)に(2)を代入し、さらに(1)を代入して
1=11-2×5
=11-(35-11×3)×5
=11×16ー35×5
=(151-35×4)×16-35×5
=151×16-35×69
これより、x=-69,y=-16は１組の解である。
これより、
35x-151y=1
35(-69)-151(y＋16)=35×151K
ｋは整数
答え
x=151k-69
y=35k-16

(2)
|x＋y|=|186k-85|
k=0のとき、|x＋y|=85
x=-69,y=-16
k=1のとき
|x＋y|=101

答えは
最小値85(x=-69,y=-16)

これが、参考書の答えです。
これを、何度も読んだのですがよくわからなくて、
くわしく（途中計算）もつけてくれませんか？
要求が多くてごめんなさい

回答No.3

kony0

なぜユークリッドの互除法が出てきたかの考え方の由来ですが、
35x-151y=1
35(x-4y)-11y=1→x-4y=aとおいて35a-11y=1
11(3a-y)+2a=1→3a-y=bとおいて11b+2a=1
2(5b+a)+b=1→5b+a=kとおいて2k+b=1

ここで、b=-2k+1
a=k-5b=k-5(-2k+1)=11k-5
y=3a-b=3(11k-5)-(-2k+1)=35k-16
x=a+4y=(11k-5)+4(35k-16)=151k-69
という感じで解けます。

要は、係数がでかすぎてわからんので、係数同士で割算してくくっていこうという発想です。
この発想が、まさにユークリッドの互除法と相通ずるところとなるわけです。

ちなみに、この発想から、aとbが互いに素な整数であるとき、必ずax+by=1を満たす整数解(x,y)の組が存在することが証明できます。

回答No.2

fushigichan

suu141さん、こんにちは。
このやり方と同じやり方を書いてあるページを見つけました。
ちょっと参考にのぞいて来てくださいね。

＞35x-151y=1 ｘ、ｙは整数とすします。

この整数解(x,y)の組を求めるには、参考URLのような「ユークリッドの互除法」が有効です。
151=35*4+11
35=11*3+2
11=2*5+1
なので、（順番に、余りで割っている）
最後の式から、35x-151y=1の１を表せます。
11-2*5=1
さらに、一つ前の式の余り２は
35-11*3=2
その前の余り１１は
151-35*4=11
と、それぞれかけるので
11-2*5=1
に、それぞれ入れてみましょう。

11-(35-11*3)*5=1
11-35*5+11*15=11*16-35*5←まず、１１と３５でまとめる
=(151-35*4)*16-35*5←その１１のところに代入
=151*16-35*(4*16)-35*5
=151*16-35*(64+5)
=151*16-35*69=1
=35*(-69)-151*(-16)=1・・・（★）
とかけることが分かりました。
よって、(x,y)=(-69,-16)は一つの解になります。

また、ここで（★）の両辺に
35*151k-35*151kを足しても変わらないので
35*(-69)-151*(-16)+35*151k-35*151k=1
35*(151k-69)-151(35k-16)=1
と変形できるので、一般解は
(x,y)=(151k-69,35k-16)k:整数　と書けます。

＞(2)
|x＋y|=|186k-85|
k=0のとき、|x＋y|=85
x=-69,y=-16
k=1のとき
|x＋y|=101

答えは
最小値85(x=-69,y=-16)

これは、
x=151k-69
y=35k-16
-----------上下足す。
x+y=186k-85

この絶対値を考えるとき、k=0か1で最小になりそうだ、
という予測ができます。
なぜなら、絶対値がついているので|186k-85|≧0
|186k-85|=0が最小
だけど、ｋは整数なので、一番小さい値をとりうるｋは
k=0またはk=1であると予想します。
(186k=85をといて、0<85/186<1より）

実際k=1のとき、|186*1-85|=101
k=0のと|186*0-85|=85
となるので、k=0のとき|x+y|=85・・・最小値となります。

ご参考になればうれしいです。
(1)の割り算していくやり方は、覚えておくと便利ですよ。

参考URL：

http://www.hokuriku.ne.jp/fukiyo/math-obe/euclid.htm

回答No.1

noname#5277

（１）の式は、ユークリッドの互除法と呼ばれるものです。
最大公約数を求めるときなどに使われる方法です。
大きいほうで小さいほうを割り、あまりで小さいほうを割る。
そのあまりで、先ほどのあまりを割る。
あとはこの繰り返しです。
詳しくはお調べください。

で、解答の長い式の１行目の左辺は、
35x-151y=1の右辺の１です。
右辺を変形して、左辺にならないかどうかを試しているのです。
そして、そのために、先ほどの互除法を利用しています。
今のヒントを元に、もう一度読み直していてください。