難しいです

質問

○等式11x-97y=1をみたす整数x,yがある。|x-y|の最小値を求める方法がわかりません。
たとえば(x,y)=(53, 6)
として。（なんでもいいんですか？）簡単に探せる方法はありますか？
すると、11*53-97*6=1なので、とおいて次は？？
全然わからないので、詳しく教えて貰えたらとてもうれしいです。

回答No.8

kony0

もう少し補足をすると、不定方程式（文字数＞式数により解が複数ある方程式）の整数解を求める手法として、

【倍数利用】
「比例の式」Y=(n/m)X（nX=mY, X:Y=m:nも同様）の形に変形して、
X=mk, Y=nkと表現する方法
【約数利用】
「積の形」XY=n（Y=n/Xも同様）の形に変形して、X,Yがnの約数であることを利用

の２つが基本的手法として考えられます。

この問題では、#6で(*1)-(*2)をすることにより「定数項を消去」することで「比例の式」を導き【倍数利用】に持ちこむ・・・という意図が働いています。

なお、他の方の質問ですが、
http://oshiete1.goo.ne.jp/kotaeru.php3?q=850244
の問題で、Xを消去して、
4y-3ay＋24a＋18=0
⇔y=(24a＋18)/(3a-4) = {8(3a-4)+50}/(3a-4) = 8 + 50/(3a-4)
⇔(y-8)=50/(3a-4)
[もしくは(y-8)(3a-4)=50]
と式変形をするのは、後者の意図が働いているからです。
ここで「(24a＋18)/(3a-4)」を「8 + 50/(3a-4)」に変形するのは、慣れてないと「突拍子もない」式変形に見えるかもしれませんが、実は小学校でおなじみの「帯分数化」をしているにすぎません。そして「帯分数化」する根拠は、まさに【約数利用】を念頭におけば自然に受け入れられる発想と考えます。（ただし約数利用を行うために、帯分数化しないといけない・・・という式変形の“知恵”を（解答から読みこむなどして）習得していないと、自分でこの式変形を思いつくのは辛いでしょうけどね）

ちなみに、#7さんの変形で解を１つ見つける方法と、#6で私の書いた方法は、本質的にまったく同じことをしています。

回答No.7

eatern27

#4です。

#5さんへの補足について。
多分,「97のｙ倍に1を足したものが11で割り切れる」という意味だと思います。

#6さんへの補足について。
＞なぜ引き算をするのですか？
引き算をすると上手くいくことが分かっているからです。
(そういうもんだと思ってください)

#6さんへの補足の後半部分について。

例えば,ｘは偶数(＝2の倍数)と言われたら,x=2nとおく、みたいな事をしたことはありませんか？

このときに、nを整数、としなければ、2nは2の倍数とは限らないので,x=2nとおいた意味がなくなってしまいます。
また、「ｘは偶数」という条件を文字を使わずに数字で表そうとすると、「x=0,±2,±4,±6,・・・」と表すことになってしまいます。「x=2n　(nは整数)」とおいた方がシンプルですよね。

ここではxが2の倍数の時,というのを考えましたが,xが3の倍数だったら,x=3n (nは整数)とおけるし、10の倍数なら,x=10n、などとおけます。さらに文字が"n"である必要もなくて、xが4の倍数なら,x=4mとおいてもいいし、x=4kでもいいんです。

ここまでのことが分かったものとして,
＞Xは97の倍数⇒X=97k, Y=11k(kは整数)とおける。
の部分を考えると,「Xは97の倍数」という条件から,「x=97k　(kは整数)」とおくことができます。さらに、Y=(11/97)Xにこれを代入すると,Y=11kとなりますよね。
繰り返しになりますが、「ｋは整数」とおくのは、ｋを整数にしないと、x=97kとおいた意味がなくなってしまうからで,
数字だけでなく,文字を使うのは,
X=97kとおいた方が,「Xは97の倍数」という条件を使いやすいから、とでも思ってください。(他に理由がないことはないですが)

さて、#4への補足についてです。

とりあえず、「どうやって特殊解を求めるか」という部分だけ書きます。
何故、こうすれば、特殊解が求まるのか,という点は、割愛します。どうしても知りたければ補足をしてください。でもその場合は,文字がたくさん出てくることを覚悟してください。

たとえば、11x-97y=1・・・☆の特殊解を求める場合,
まず、97(=x、yの係数のうち、大きい方)を11(=x、yの係数のうち、小さい方)で割った余りを求めます。
97÷11=8あまり9です。→97＝11*8+9・・・★

次に,☆の97を、今求めた余り(=9)で置き換えます。
11x-9y＝1・・・◎

同じように11を9で割った余りを求めます
11÷9＝1あまり２です。→11＝1＊9＋2・・・●
◎の11を今求めたあまりで置き換えます。

2x－9y＝1・・・◇

ここまでくれば,◇の整数解の１つとして、(5,1)が見つかると思います。
よって、
2*5-9*1＝1です。
●から2＝11-1*9なので、
(11-1*9)*5-9*1＝1

11*5-9*6=1
さらに、★から、9＝97-11*8なので、
11*5-(97-11*8)*6=1

11*53-97*6=1

よって、(x、y)=(53,6)が11x-97y=1の整数解の１つとして見つかりした。

ここでは、11x-97y=1の整数解を求める方法を書きましたが,同じようにやれば,110x-971y=1の整数解も求まります。

回答No.6

kony0

11x-97y=1を満たす整数(x,y)の組はいろいろあります。
そのうちの1つの解(x,y)=(53,6)を見つけられていますね。
あとは、この方程式を満たす整数が(x,y)=(53+97k, 6+11k)とあらわせることを理解して欲しいと思います。（これが重要）

ちょっと“ベタ”な説明かもしれませんが・・・
11x-97y=1・・・(*1)
11*53-97*6=1・・・(*2)
(*1)-(*2)を行うと、11(x-53)-97(y-6)=0
x-53=X, y-6=Yと置くと、11X-97Y=0⇒Y=(11/97)X
X,Yは整数だから、Xは97の倍数⇒X=97k, Y=11k(kは整数)とおける。
よって、(x,y)=(97k+53, 11k+6)（ただしkは整数）
（ここまでで“ベタ”な説明おわり）

ここまでわかればあとは“オマケ”みたいな問題です。
|x-y|=|86k+47|
kは整数なので、この右辺はk=-1のとき最小値39となる。
k=-1ということは、(x,y)=(-44,-5)

（ここからは無駄話^^;）
ちなみに、はじめの１つの整数解を求めるところについて、11x-97y=1あたりだと、yに0～10を代入すれば必ず見つかるのでなんとかなりますが、
110x-971y=1
だと見つかりますか？難しいですね。
これは式変形（“互除法”と呼ばれる方法です）で求めることができます。

110x-(110*9-19)y=1
110(x-9y)+19y=1
(19*6-4)(x-9y)+19y=1
19{6(x-9y)+y}-4(x-9y)=1
19(6x-53y)-4(x-9y)=1
(4*5-1)(6x-53y)-4(x-9y)=1
4{5(6x-53y)-(x-9y)}-(6x-53y)=1
4(29x-256y)-(6x-53y)=1
これより
29x-256y=k, 6x-53y=4k-1と置くことができます。
これを解くと(x,y)=(-971k+256, -110k+29)

補足

いくつか質問してもよいですか？
>(*1)-(*2)を行うと、11(x-53)-97(y-6)=0
なぜ引き算をするのですか？

＞x-53=X, y-6=Yと置くと、11X-97Y=0⇒Y=(11/97)X
X,Yは整数だから、Xは97の倍数⇒X=97k, Y=11k(kは整数)とおける。

において
X,Yは整数だから、Xは97の倍数⇒X=97k, Y=11k(kは整数)とおける。
がよくかからないです。
Xは97の倍数⇒X=97k, Y=11k(kは整数)はどこからでたのですか？
なぜKは整数とおくのですか？
このとき、なぜ文字をつかうのですか？
数字だけはだめなのでしょうか？
こちらこそ、説明が下手ですいません。
よろしくお願いします。

回答No.5

mirage70

11x-97y=1は、x,yは整数より、97のn倍+1が11で割り切れるというものです。
此が成り立つものとして、n=6が見つかります。
よって、11x-97y=11×53-97×6
11(x-53)=97(y-6)ここで11,97は互いに素であるので、
x=97k+53,y=11k+6
｜x-y｜=｜86k+47｜そしてk=0のとき47、k=-1のとき39
よって、k=-1のとき、即ちx=-44,y=-5

補足

<97のn倍+1が11で割り切れるというものです。
について良くわかりません。

回答No.4

eatern27

前にした回答は難しすぎたかもしれませんね。

具体的な解を１つ求める方法は、#2さんのように具体的に求めるか、
以前書いたように、「余り」を使って求めるかです。
(他にも行列とか使って求める方法もありましたが)

簡単に探す方法はありません。
x、yの係数が小さければ、#2さんの方法が一番いいですが、xやyの係数が大きいと、しらみつぶし、ってのは効率が悪いですね。

なので、x、yの係数が大きい場合は、下記URL(前にも載せたやつです)のように余りを使って求めれば、
多少は面倒だけど、しらみつぶしに探すよりは、楽に、効率的に探せます。

下記URLに書いてあることを読むだけではなく、具体的な数字を当てはめて、計算してみれば、理解しやすいと思います。分からない点は補足してください。

なお、|x-y|の最小値は39ですね。(x、y)＝(-44,-5)のとき

参考URL：

http://www.shinko-keirin.co.jp/kosu/mathematics/kirinuki/kirinuki12.html

補足

参考URLを読みました。
しかし、なんど読んでもよくわからないです。
もしよければ詳細付きで教えてもらってよいですか？

回答No.3

youjin

No.2の者です。肝心な答えを書き忘れてました。

最小値は|53-6|=47です。

補足

答は３９だそうです。

回答No.2

youjin

まず、11x-97y=1を変形して、x=(97y+1)/11とします。

これを|x-y|に代入すると、
|x-y|
=|{(97y+1)/11}-y|
=|(97y+1-11y)/11|
=|(86y+1)/11|
となります。

ここでyは整数なので、(86y+1)/11は常に正の値をとります。
よって(86y+1)/11の値が小さければ絶対値をつけた|(86y+1)/11|の値も小さくなります。
また、(86y+1)/11の値はyが小さいほど小さくなります。
したがって、|x-y|はyが小さいほど小さい値をとるということがわかります。

ここからはちょっと地道な作業になります。

yは整数なので、yに０、１、２というように小さいものから当てはめていって、xも整数になるときを探します。そうやって最初に見つかった(x,y)の組み合わせが|x-y|を最小にする組み合わせとなります。

では最初の式の、x=(97y+1)/11にy=0から順に当てはめていきます。

y=0のとき、x=(97*0+1)/11=1/11　割り切れないのでダメ
y=1のとき、x=(97*1+1)/11=98/11　これもダメ
y=2のとき、x=(97*2+1)/11=195/11　これもダメ
y=3のとき、x=(97*3+1)/11=292/11　これもダメ
y=4のとき、x=(97*4+1)/11=389/11　これもダメ
y=5のとき、x=(97*5+1)/11=486/11　これもダメ
y=6のとき、x=(97*6+1)/11=583/11=53　割り切れた

したがって、(x,y)=(53,6)のときに|x-y|は最小値をとる。

ちなみに最初の変形でy=～の形に変えても解けますが、この場合だと
y=(11x-1)/97となり、分母がかなり大きくなってしまいます。
x=～と変形したときの分母も11ということでちょっと大きいですけど、これなら数値を最高でも11回ほど代入すれば答えが見つかりますが、
分母が97だと最高で97回も代入しないといけなくなります。
なので、この問題ではx=～の形に変形して解くべきでしょう。

回答No.1

mikelucky

方針だけ書きます

11x-97y=1 のグラフを書きます

|x-y|=k　とおき、そのグラフを書きます
このグラフは正方形で対角線がｘ軸ｙ軸になってます
対角線の長さは2kです。

kを少しずつ大きくしていくとやがて11x-97y=1のグラフと交わります（|x-y|=kのx,yが11x-97y=1の関係を満たしたということ）。そのときのkが最小値です。

これで大jobと思うけど自信ないです