【2018東京工業大学】35x+91y+65z=3を満たす整数解、x^2+y^2の最小値

【2018東京工業大学・第２問】

(１)　\(35x+91y+65z=3\) を満たす整数の組 \(( x , y , z )\) を一組求めよ．

(２)　\(35x+91y+65z=3\) を満たす整数の組 \(( x , y , z )\) の中で \(x^2+y^2\) の値が最小となるもの，およびその最小値を求めよ．

整数問題のPoint

まず整数問題すべてに共通して言えるPointは

整数問題の多くが、上の１から３のいずれかで処理できます。

本問では，『３．倍数や余りに注目』で考えていきましょう！

\(35x+91y+65z=3\) の係数に注目すると，

\(35=5\times 7\) , \(91=7\times 13\) , \(65=5\times 13\) であるから，

\(mod 5\) または \(mod 7\) または \(mod 13\) に注目して考えていく．

合同式について不安な方、学習していない方は、

を参考にまず合同式をマスターしましょう！

大学の難易度に関わらず、合同式は整数問題を扱う上で必須アイテムです！

初めに，\(mod 13\) として考える．

\(35≡-4\) , \(91≡65≡0\) であるから与式より

\(-4x≡3\)

両辺を \(3\) 倍すると

\(-12x≡9\)

よって，\(x≡9\)

したがって，整数 \(a\) を用いて

\(x=13a+9\) ・・・① と表せる．

次に，\(mod 5\) として考える．

\(91≡1\) , \(35≡65≡0\) であるから与式より

\(y≡3\)

したがって，整数 \(b\) を用いて

\(y=5b+3\) ・・・② と表せる．

①，②より

\(35(13a+9)+91(5b+3)+65z=3\)

\(\iff\) \(z=-7a-7b-9\)

よって整数解は，\(( x , y , z ) = ( 13a+9 , 5b+3 , -7a-7b-9 )\)

したがって，\(a=b=0\) としたとき整数解の一組は \(( 9 , 3 , -9 )\)

※ 答えは何か一組見つければ良いため，\(a\) , \(b\) には何を代入しても良い．

※ 本問では(２)にて『 \(x=\) 』,『 \(y=\) 』の形が必要となり，できるだけ簡単な形で表したかったため， \(mod 13 , 5\) で考えた．もちろん \(mod 7\) としても良い．

(１)の①，②より，\(x=13a+9\) , \(y=5b+3\) であるから

\(x^2+y^2=(13a+9)^2+(5b+3)^2\)

これが最小となるのは \(| x |\) , \(| y |\) がそれぞれ最小となるときである．

つまり，\(a=b=-1\) のとき \(| x |\) , \(| y |\) が最小値をとるので，

\(( x , y , z ) = ( -4 , -2 , 5 )\) のとき最小値：\((-4)^2+(-2)^2=20\)