最小値について

質問

等式についての最大値の求め方が分からなくて、誰か知っている人がいたら教えてくれませんか？
等式の問題は
11x-97y=1を満たす整数xとyについてで。
|ｘ－ｙ｜の最小値を求めるのですが、絶対値がでてくると、なんだ？という感じでさっぱりわかりません。
答えは39ですが、　任意の会はx＝-44＋97t y=-5＋11t　　です。

分かる方がいれば、詳しく教えてくれませんか？
お願いします

回答No.6

eatern27

＞本当にたびたびごめんなさい。
いえいえ、私の説明のしかたが悪いだけです。

＞疑問があるのですが-1÷11＝10の意味がわかりません
-1÷11＝10と書きましたっけ?ちょっと見当たらないのですが、もし書いていたのなら、(-1)÷11=-1余り10 の間違いです。
例えば、25を11で割った余りを求める時は
まず、25÷11をしますね？
25/11=2.・・・
となることから、25-2*11=3 という計算を(無意識に)して
25÷11＝2余り3
というのを求めていますね? これをちょっと難しく説明すると
25/11以下の最大の整数である２が商となり
余り＝25-11*(商)=25-11*2=3、
よって、25÷11＝2余り3
というようなことをしています。

-1でも同じことをしてみましょう
(-1)÷11=-0.・・・
(-1)/11以下の最大の整数が商となりますので、商は-1となります。
だから、余りは(-1)-11*(-1)=10 となります。
∴-1≡10 (mod 11)
-2でも同じことをすればいいです。ここにすべて書いてしまうよりは、pot105さん自身がどうなるかを考えた方がいいので、自分で考えてください。もし、分からなければ、補足に書いてもらっていいですが、その時は、どのように考えたかを書いてください。(考えがまとまってなくてもいいので、書いて下さい)

ちなみに、実際はこういう計算をしているのではなく

よって、-1≡(-1+11=)10 (mod 11)
のようにやりました。

＜97ｙ＋１は11の倍数。　これは分かるのですが、
＜97ｙ≡10の変化がわからないです。
97y+1は11の倍数です。
つまり、97y+1≡0≡11 (mod 11)
となります。だから、(97+1)-1≡11-1 (mod11)
97y≡10
となるのです。
別の説明をすれば、
97yに1を足したら、11の倍数になります。ということは、97yは11の倍数から1を引いたものです。11の倍数は
11,22,33,44,55,66,77,88,99,110,121,132,143,154,164・・・
など無限にありますが、そのどれをとっても、1を引いたものを11で割れば、10余ると思います。(実際にいくつか計算してみて下さい)
だから、97yを11で割れば、10余る。ということは、
97y≡10 (mod 11)
となります。

合同式について知りたいのなら、参考書とか買った方が、分かりやすく説明しているかもしれません。

回答No.5

eatern27

＞9*2≡7 (mod11) は18≡7
＞9*3≡5 (mod11) は27≡５で
＞なんで合同なのかわかりません
#2の補足に97y≡10 (mod 11) が分かったみたいなことが書いてあったので合同式は分かるものと思っていましたが、あまり深くはやってなかったみたいですね。
α≡β (mod n)
これは、αをｎで割った余りと、βをｎで割った余りが等しいという意味です。

18を11で割ると、余りが7です。(商は1)
7を11で割ると、余りが7です。(商は0)
だから、18≡7(mod 11) となります。
同様に27÷11＝2余り5、5÷11＝0余り5 であるから、
27≡5 (mod 11)となります。

ある整数αがあるとします。このαに11の倍数(＝11n)を足しても、αを11で割った余りは変わらないと言うのは感覚的に分かるでしょうか?
この事が#3で書いた、α≡α+11n (mod 11),ｎは整数、の事です。

＞何で9≡-2になるのかがわかりません。
その前に
a≡b,c≡d (mod q)が成り立っている時に
a+c≡b+d (mod q)
a*b≡b*d (mod q)
というのが成り立ちます。
これは、a=pk+α、b=ql+α、c=qm+β、d=qn+β(0≦α＜q,0≦β＜q、k,l,m,nは整数)とおけば、容易に証明できると思います。
α≡α+11n (mod 11)もα≡α、0≡11n (mod 11)だから、
α+0≡α+11n
α≡α+11n
と示せます。
α≡α+11n (mod 11)が成り立つことを認めてくれるのなら、α=9,n=-1を代入すれば、9≡-2 (mod 11) となります。
もし、認めないなら、原始的な方法で説明します。
0,1,2,3,4,・・・・・10,11,12,13,14,15,・・・・・・・・(1)
0.1.2.3.4.・・・・・10, 0, 1, 2, 3, 4,・・・・・・・・(2)
（(2)は(1)を11で割った余りです)
となり、11で割った余りは
0,1,2,3,4,5,6,7,8,9,10を永遠に繰り返します。とすると、
(2)の0の左隣は10,10の左隣は9ですね？
(1)の一番左は0となっていますが、本当はその左には-1があります。それを11で割った余りは(2)の0の左隣にある数字、つまり、10です。(1)の-1の左には-2があり、(2)で-2に対応する数字は10の左隣、つまり、9です。表にすると、
・・・・・,-4,-3,-2,-1,0,・・・・・
・・・・・, 7, 8, 9,10,0,・・・・・
となり、9≡-2となります。

補足

本当にたびたびごめんなさい。
＜(1)の一番左は0となっていますが、本当はその左には-1があります。それを11で割った余りは(2)の0の左隣にある数字、つまり、10です。(1)の-1の左には-2があり、(2)で-2に対応する数字は10の左隣、つまり、9です。表にすると、
・・・・・,-4,-3,-2,-1,0,・・・・・
・・・・・, 7, 8, 9,10,0,・・・・・
となり、9≡-2となります。
は分かりましたが、
ちょっと、疑問があるのですが-1÷11＝10の意味がわかりません(計算方法）
同様に-2÷11=9
お願いします

それから、
＜97ｙ＋１は11の倍数。　これは分かるのですが、
＜97ｙ≡10の変化がわからないです。
何度も質問してごめんなさい。

回答No.4

eatern27

#2、3です。
＞α≡α+11n (mod 11),ｎは整数
＞は公式なんですか？
公式か？と聞かれると微妙です。
合同式がわかるのなら、これが成り立つことは分かりますよね?

＞α＝9、ｎ=-1を代入すれば、9≡-2 となりますがなんで
＞現れるのかがわかりません。
何で9≡-2になるのかは、いいですよね?
何で9≡-2にわざわざ変形したのか、ということを聞いているのでしょうか?

結論から言うと、絶対に変形しなければいけないものではありません。
9を何倍したら、11で割って10余るかを求めてもいいです。
ですが、
9*1≡9 (mod11)
9*2≡7 (mod11)
9*3≡5 (mod11)
と考えていって、すぐに見つかれば、いいのですが、見つかるまでが長かっそうだったので別の方法はないものかと考えました。
そこで、絶対値を小さくすることを考えました。
97≡9≡9-11=-2 (mod11)
だから、
97y≡-2y (mod11)
だから、-2y=10となる整数ｙがあればいいと考えてみると、y=-5の時になる、という事が分かるのです。

この解き方は、俺が、回答を書いている時に、最初に思い浮かんだ方法なので、ベストの解法ではないと思います。負の数をとるか、数字がでかいのをとるか人それぞれですので、pot105さんが、やりやすい方法でやるのが1番です。

絶対値が大きいのをとるのなら、
9*1、9*2、9*3、・・・と考えるよりは、
かける数が1増えれば、余りは２減る。つまり、かける数が1減れば余りは２増える
ということを考えて、
9*0≡0 (mod11)
10/2=5
だから、9*(-5)≡10 となる。
のように考えるのがいいでしょうか？

でも、とにかくここでは、11x-97y=1を満たす整数が求まればどんな方法でもいいです。ですが、今はテストではないので、どんな方法なら、簡単かつすぐに求まるかを考えた方が、テストのためにはなります。

補足

なんども、すみません。
何で9≡-2になるのかがわかりません。
9*1≡9 (mod11)
9*2≡7 (mod11)
9*3≡5 (mod11)
についてなのですが、
9*2≡7 (mod11) は18≡7
9*3≡5 (mod11) は27≡５で
なんで合同なのかわかりません。
ぜんぜん知識がなくてごめんなさい

回答No.3

eatern27

#2です。
＞9≡-2はどうして合同なのでしょうか？
合同式に負の数を使っていいかは謎です。(先生に確認するか、テストの時に使わないか、した方がいいかも知れません)
負の数を使っても何も困ることはないと思うので、負の数の時にも定義されてると思い、使いました。
α≡α+11n (mod 11),ｎは整数
というのはいいですか？
α＝9、ｎ=-1を代入すれば、9≡-2 となります。

なお、この問題がテストで出たら、
11x-97y=1を変形して、
11(x+44)=97(y+5)
と書き始めて問題はないと思います。

＞なぜ、x+44は97の倍数は倍数なのでしょうか？
x+44=X,y+5=Y,とおくと、
11X=97Y
となります。右辺は97の倍数です。従って、左辺も97の倍数です。
つまり、11Xが97の倍数です。
Xが97の倍数でないとすると、11と97は互いに素だから、Xに11をかけても97の倍数にはなりません。だから、X=x+44は97の倍数となります。
同様の理由でy+5は11の倍数となります。

こんな説明で分かったでしょうか?
分からなかったり、納得できないことがあれば、補足ください。

補足

なんどもごめんなさい
α≡α+11n (mod 11),ｎは整数
は公式なんですか？
α＝9、ｎ=-1を代入すれば、9≡-2 となりますがなんで
現れるのかがわかりません。
おんなじ所でなんどもきいてごめんなさい

回答No.2

eatern27

11x-97y=1を満たす整数の組み合わせを考えます。
11x=97y+1だから、
97y+1は11の倍数。よって、
97y≡10 (mod 11)
となります。
97≡9≡-2 (mod 11)
であるから、
y=-5の時x,整数になります。この時(x,y)=(-44,-5)となります。

11x-97y=1を変形すると
11(x+44)=97(y+5)
11と97は互いに素だから
x+44は97の倍数。tを整数として
x+44=97tと置けます。この時y+5=11tとなり、
x=-44+97t、y=-5+11t
となります。
ここで、x-y=-39+86tだから、t=1の時x-y=47、t=0の時x-y=-39
よって|x-y|はt=0の時最小でmin|x-y|=39となる。

補足

11x-97y=1を満たす整数の組み合わせを考えます。
11x=97y+1だから、
97y+1は11の倍数。よって、
97y≡10 (mod 11)
となります。
は分かりましたが。
97≡9≡-2 (mod 11)がわかりません。9≡-2はどうして合同なのでしょうか？
また、
11x-97y=1を変形すると
11(x+44)=97(y+5)
11と97は互いに素だから
x+44は97の倍数。なぜ、x+44は97の倍数は倍数なのでしょうか？
せっかく、教えてもったのに理解ができなくてごめんなさい

回答No.1

0shiete

わからなければ、実際に数字を入れてやってみる
というのは鉄則です。

11x-97y=1を変形して
x=(1+97y)/11

これから、yに順番に整数をいれて、xが整数になるかどうか見ていきます。
ちょっとたいへんですが、y=1,2,3、、、と入れていくと
y=6,17でxが整数になることがわかります。

ここで、11づつ増えていくのかな？とめぼしをつけ、
それでたしかめるためにy=17+11=28でやってみると
x=247となり、整数になります。

ここで、yを11づつ増やしていけば、(x,y)の整数ペアを次々と
見つけることができると確信します。

(x,y)の整数ペアを、書き出してみると
(6,53)
(17,150)
(28,247)
...

ここで、上のペアに対して、|x-y|を計算してみると、
どんどん値が増加しています。それで、逆方向を探そうと
思い立ちます。
yを11づつ減らしていって、

(-5,44)
(-16,-141)
(-27,-238)
....

また、|x-y|を計算してみると、(-5,44)で39となり、その後
また、増加していきます。

したがって、(-5,44)のペアで39が答えです。

答案用紙用の回答には、きちんと書かないといけませんが、
考え方としては上のようになると思います。