方程式

質問

○等式11x-97y=1をみたす整数x,yがある。|x-y|の最小値を求める方法がわかりません。
たとえば(x,y)=(53, 6)
として。（なんでもいいんですよね？）
すると、11*53-97*6=1なので、とおいて次は？？
難しいです

○自然数Nの十位、一位をそれぞれa,bとする。このとき(N＾2)の十位,一位とNの十位、一の位が一致するものを求める。
(Nは２けたとします）

NとN^2の下２桁が一致することが条件はわかるのですが。
Nをどのように定めるのかわかりません。

回答No.7

eatern27

#4～6です。長い上に分かり難いかもしれませんね。(すいません)

#6で、「11x-97y=1を変形して、11(x-53)=97(y-6)になる理由」についてぐだぐだ書いてしまいましたが、
11(x-53)=97(y-6) のyの項を左辺に、定数項を右辺に持ってくれば、11x-97y=1になる事から理解できると思います。

ついでですが、#5に書いた事は、下記URLの方が分かりやすいですね。「不定方程式」で検索したら、他にも分かりやすいサイトがあるかもしれません。

参考URL：

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

回答No.6

eatern27

#4,5です。#4への補足についてです。

・11x-97y=1を変形して、11(x-53)=97(y-6)になる理由
まず、(x,y)=(53,6)が11x-97y=1の解であることが分かっている、という前提があります。(この事が分かっていない状況では、上のように変形するのは無理)

考え方はいろいろあると思いますが、
(x,y)=(53,6)が11x-97y=1の解なので、11*53-97*6=1ですね。なので、11x-97y=1は、11x-97y=11*53-97*6と変形(?)できます。
11*○の項を左辺に、97*○の項を右辺に持ってくると
11x-11*53=97y-97*6
左辺を11で、右辺を97でくくって、11(x-53)=97(y-6)となります。

・"11(x-53)＝97(y-6)＝11*97*n (nは整数)とおける"のあたり。
＞x,yは整数だから、11(x-53)は11の倍数、97(y-6)は97の倍数。
の部分は理解できたのでしょうか？とりあえず、11(x-53)＝97(y-6)＝ｋとおきましょう。
ｋ＝11(x-53)なので、kは11の倍数で、
ｋ＝97(y-6)なので、kは97の倍数です。

つまり、kは11の倍数かつ、97の倍数です。
これを満たすkは11*97の倍数のみですね。
ｋは11*97の倍数だから、k＝11*97*n (nは整数)とおける事になります。
11(x-53)＝97(y-6)＝ｋでしたから、
11(x-53)＝97(y-6)＝11*97*n (nは整数)
となります。
11(x-53)＝11*97*nを解いて、x=97n+53
97(y-6)＝11*97*nを解いて、y=11n+6となります。
よって、11x-97y=1の一般解は,(x,y)=(97n+53,11n+6)
（ｎは整数)と表されることが分かります。

・(x,y)＝(53,6)などの求め方
#5を見てください。
他にも行列を使って解を求めているのを見たことがありますが、どんな風に求めていたかは忘れました・・・。

・(2)の問題
#4の最後に、N,N-1の一方は25の倍数、他方は4の倍数。
と書きましたが、これは分かりましたか？
これが分かれば、N,N-1の一方は25の倍数、という条件から、Nは25,26,50,51,75,76に絞られます。この中で、他方は4の倍数という条件にあうのは・・・。と考えれば、答えが出てきます。

回答No.5

eatern27

#4です。
＞|x-y|=｜ (1+86y)/11 ｜
はどうやってでてきたのですか？

11x-97y=1を
x=(1+97y)/11
と変形して、|x-y|に代入しただけです。

＞11x-97y=1を満たす整数はすぐに見つかる方法がありますか？
「すぐに」とまではいきませんが、少なくともx,yの係数が大きくて、具体的な数値を代入していたら、時間がかかる(かもしれない)という場合に有効な方法があります。それが、#4に書いたような方法です。

a,bは互いに素で、a>bとします。このとき、ax+by=1の整数解を求める方法を考えます。

まず、aとbが十分小さい時は、具体的に代入して考えていってもさほど苦労はしないので、具体的に代入して求めてください。例えば、5x+7y=1の整数解を１つ挙げろ、と言われたら、(x,y)=(3,-2)などが、すぐに思い浮かびますよね？

ですので、a,bが大きい場合について考えます。
aをbで割った時の商をq,余りをrとすると、
a=bq+r⇔r=a-bqとなります。
ここで、bx+ry=1の整数解が１つ求まって、その整数解を(n,m)とします。
そうすると、bn+rm=1となりますが、r=a-bqなので、
bn+(a-bq)m=1となります。これを変形すると、
am+b(n-qm)=1となりますが、m,n,qは整数なので、mとn-qmも整数です。
なので、(m,n-qm)はax+by=1の整数解の１つ、という事が分かります。

つまり、bx+ry=1の整数解が１つでも求まれば、ax+by=1の整数解も自動的に求まるということです。

なので、bx+ry=1の整数解を求めればいいわけですが、この式は最初のaの部分をbに、bの部分をrに置換えた式です。
だから、ax+by=1で行った議論がそのまま適用できます。

bをrで割った余りpとおくと、rx+py=1の整数解を求めればいいことが分かります。このように進めれば、

αx+βy=1のα,βに相当する部分が、いずれは十分小さくなるので、いずれは具体的な数値を代入することで、求めることができます。

なお、ax-by=1のパターンも、ax+b(-y)=1なので、-yを改めてyとおけば、ax+by=1のパターンに帰着できます。

これだけではわかりにくいかと思いますが、これを具体的な数値を代入して進めたものが、#4に書いたものです。もう1度、11x-97y=1の方程式の整数解の求め方を書きます。

97=8*11+9なので、11x+9y=1の整数解を求めます。・・・☆

☆の整数解が見つからない場合、
11=1*9+2
から、9x+2y=1の整数解を求めればいいのですが、整数解は(1,-4)が見つかったとします。

9*1+2*(-4)=1
これに2=11-1*9を代入して
9*1+2*(-4)=9*1+(11-1*9)*(-4)=11*(-4)+9*5=1

上の続きと☆の整数解(-4,5)が見つかった場合
9=97-8*11を11*(-4)+9*5=1に代入して
11*(-4)+(97-8*11)*5=11*(-44)-97*(-5)=1
よって、(x、y)=(-5,-44)は方程式11x-97y=1の整数解

このように解けば、「すぐに」とか「簡単に」とは言えませんが、少なくとも具体的に代入するよりは「早く」「楽に」求めることができます。(x,yの係数が大きい場合のみ)

分からなければ補足をください。

回答No.4

eatern27

1つめ。
(x,y)＝(53,6)という解が分かっているなら、後もうすこしです。(こういう問題って、(x,y)=(53,6)みたいな具体的な解を求めるのが大変なんです)

11x-97y=1を変形すると、
11(x-53)=97(y-6)となります。
x,yは整数だから、11(x-53)は11の倍数、97(y-6)は97の倍数。よって、
11(x-53)＝97(y-6)＝11*97*n (nは整数)とおける。
一般解は、(x,y)=(97n+53,11n+6) (nは整数)

という感じです。ここまでできれば、|x-y|=|86n+47|とｎが整数という条件から、|x-y|の最小値が求まります。

あと、#2さんのご回答に
＞これが整数となるようにy=1,2,3を順々に入れていきましょう。それで最初に見つかったものが答えになります。
とありますが、x,yの条件が"自然数"ではなく、"整数"なので、間違いです。
y=0,1,2,3・・・とy=-1,-2,-3・・・
で順々に入れて、それぞれについて最初に見つかったもののうち、小さい方が答えです。
実際、|x-y|を最小にする(x,y)は(-44,-5)ですから、答えも違ってきますね。

参考までですが、「11x-97y=1の整数解を探すのが大変」と思うのなら、次のような方法があります。

11n+9m=1を満たす整数の組(n,m)が見つかったとします。
9=97-11*8を代入して、11n+(97-11*8)m=1
11(n-8m)+97m=1
となるので、(x,y)=(n-8m,m)が整数解になります。
つまり、11n+9m=1の整数解を求めればいいことになります。(11x-97y=1の整数解を求めるよりは楽です)

なお、11n+9m=1の11は11x-97y=1の11、9は97を11で割った余りです。

11n+9m=1の整数解を探すのも面倒なら、同じ様に考えて、
9a+2b=1の整数解を探せばいいことになります。

上に書いたことが分からなければ、補足に書いてくれて問題ないですが、用事があるので、返事を書くのは早くても火曜の夜になるって事だけ頭に入れておいてください(分かりやすく書けるかは分かりませんが)

２つめ。
N^2－N＝N(N-1)は１００の倍数。
ここから、N,N-1のうち、一方が25の倍数で他方が4の倍数である事が分かります。(理由は自分で考えてください)

補足

(1)について教えてください
（x,y)＝(53,6)どうやったら見つけることができるのでしょうか？
コツとかありますか？

11x-97y=1を変形すると、
どうして変形すると↓のようになるのでしょうか？

11(x-53)=97(y-6)となります。
x,yは整数だから、11(x-53)は11の倍数、97(y-6)は97の倍数。よって、
↓の意味がよくわかりません
11(x-53)＝97(y-6)＝11*97*n (nは整数)とおける。
一般解は、(x,y)=(97n+53,11n+6) (nは整数)

(2)はまだ考えているので、もしわからなかったら教えてください

回答No.3

eiji2003

＃２のものです。
＞(1)なのですが、例えば(x,y)=(2,3)でも良いのでしょうか？
だめです。11x-97y=1を満たす整数になっていないからです。先ほど回答したように
|x-y|=｜ (1+86y)/11 ｜・・・ (1)
これにｙ＝1,2・・・を順々に入れていくと(1)が整数になるものが見つかります。(1)式は11x-97y=1　を使ってｘを消去しているので、この方法で見つけたｙは当然、11x-97y=1を満たしています。

＞はどうして100A＋Nというのが出るのでしょうか？
すいません。間違えました。
NとN^2の下２桁が一致するので
N^2=1000A+100B+N 　（例1234=*1*1000＋2*100+3*10＋4）
　　　　↑　　　↑
　1000の位　100の位
と置けます。

変形すると
N(N-1)=100(10A+B)

あとは＃１の方がおっしゃている
b^2の１の位がbになるのは1,5,6の３通りというヒントと併せて
解いていくと良いでしょう。
（つまり、N=11,15,16,21,25,26,31,35,36・・・,96を
入れていって、これが100の倍数になるものを見つければOK。）

補足

(1)なのですが
|x-y|=｜ (1+86y)/11 ｜
はどうやってでてきたのですか？

11x-97y=1を満たす整数はすぐに見つかる方法がありますか？
数字を１から代入すると時間がかかるので

回答No.2

eiji2003

ヒントです。

>11*53-97*6=1なので、とおいて次は？？
これだと(x,y)の組をすべて見つけないといけないので非常に大変です。

11x-97y=1をｘ＝・・・の形に変形して
それを使うと
|x-y|=｜ (1+86y)/11 ｜
となります。
これが整数となるようにy=1,2,3を順々に入れていきましょう。それで最初に見つかったものが答えになります。

2番目の質問ですが、
題意より
N^2＝100A＋N（Aは1以上9以下の整数）
とおけます。
これを変形すると
N(N-1)=100A　・・・(1)
となります。

A=1,2・・・を代入していくと
A=6のときに(1)が成立することがわかります。
あとはN＝10a+b とおけばa,bが見つかりNがわかります。

補足

せっかく、教えていただいたのに分かりません。
すいません。
(1)なのですが、例えば(x,y)=(2,3)でも良いのでしょうか？

(2)
はどうして100A＋Nというのが出るのでしょうか？
Nは10の位だから10×10で100なのでしょうか？

せっかく、ヒントを頂いたのによくわかりません。
すいません。

回答No.1

gatyan

○等式…
11x-97y=1 を y=…に変形，|x-y|に代入して絶対値が０になる実数のxを求める
整数ではないxなので、両隣の整数で絶対値を計算しなおすで求まるのでは？|x-y|のグラフ（x,yが実数のとき）はｖ字型だからどっちかが答えのはず。
○自然数
b^2の１の位がbになるのは1,5,6の３通りだから、あとは力技？
ちなみにExcelで力技させたら２個ありました。
N=10a+bで計算すると、100*a^2が出てくるのでこの項を無視！！…１００掛けてるから下２桁とは無関係。
残った式でbに上の３つを代入しながら計算すると少し楽かも。