[math][東京工業大学]2018年度前期東京工業大学数学問題2

photo of mountains math
Photo by SAM LIM on Pexels.com

問題

次の問に答えよ。
(1) 35x+91y+65z=3を満たす整数の組(x,y,z)を一組求めよ。
(2) 35x+91y+65z=3を満たす整数の組(x,y,z)の中でx2+y2が最小となるもの、およびその最小値を求めよ。

方針

中国式剰余定理を題材にした問題である。与えられた式を5,7,13で割ったものを考えると、先が見えてくる。

解答

(1) 35=5×7,91=7×13,65=13×5である。したがって、35x+91y+65z=3に対して、5,7,13での剰余を考えると、{y3(mod5)2z3(mod7)9x3(mod13)となる。この剰余式を解くと、順にy3(mod5),z5(mod7),x9(mod13)となる。したがって、p,q,rを整数として、{x=13p+9y=5q+3z=7r+5とおける。これを35x+91y+65z=3に代入すると、35(13p+9)+91(5q+3)+65(7r+5)=3となり、整理すると、5×7×13(p+q+r)=910=5×7×13×2となる。よって、p+q+r=2である。これを満たすp,q,rとして、適当にp=1,q=1,r=0を取ることができて、その時x=4,y=2,z=5となる。これは35x+91y+65z=3を満たす。

(2) (1)から、35x+91y+65z=3を満たす(x,y,z)の組は、{x=13p+9y=5q+3z=7r+5p+q+r=2とおける。p,qは整数を自由に動く事ができる(このときr=2pqrは自由に動けない)ので、x2+y2を小さくするには、x,yをそれぞれ小さくすれば良い。x=,17,4,9,22,y=,7,2,3,8,であるから、x=4,y=2 (p=1,q=1)のときx2+y2は最小である。このとき、r=0で、z=5となる。よって、x2+y2が最小になるのは(x,y,z)=(4,2,5)のときで、x2+y2の最小値は20となる

解説

日本では古来から百五減算という数遊びが知られている。これは、塵劫記という江戸時代の算術書に記載されたもので、次のような問題である。

3で割ると2あまり、5で割ると1あまり、7で割ると2余る一番小さい数は何か?

これには次のような巧妙な解法が知られている。70,21,15というマジックナンバーを考える。なぜこのような数を考えるかというと、{701(mod3)211(mod5)151(mod7)であるから、ある数x3,5,7で割った余りを順にa,b,cとすると、70a+21b+15cは、3で割るとaあまり、5で割るとbあまり、7で割るとcあまる数を代表しているのである。これが3×5×7=105より大きい時は、105を引き、マイナスになっている時は105の整数倍を足せば良い。105を引くので百五減算という訳である。

上の問題の答えは、70×2+21×1+15×2=191として、これは105よりも大きいので、191105=86となる。実際に863,5,7で割った確かめると良い。

以下が中国式剰余定理であり、この定理のおかげで百五減算や、上の東京工業大学の問題に解が存在することが保証されている。

p,q,rはどの2つをとっても互いに素な自然数として、a,b,cを任意の整数とする。このとき、xa(modp)yb(modq)zc(modr)を満たす整数xが、0からpqr1の中に、ただ一つ存在する。

この定理は大学の群論で学ぶので、今はあまり気にしないでも問題ない。

関連問題

2000年京都大学後期理系数学問題3 ax+by=1を満たす整数(格子点)の存在

関連リンク

東京工業大学
東京工業大学の教育、研究、社会連携、国際交流などの活動、東京工業大学に関する概要や最新情報をご覧頂けます。

コメント

タイトルとURLをコピーしました