【2022東京工業大学・第２問】
(１)考え方・解答
(１)考え方
\(3\) 文字における最大公約数
よくあるパターン問題としは、
\(2\) 文字 \(a\)、\(b\) の最大公約数が \(g\) のとき
互いに素な整数 \(s\)、\(t\) を 用いて、\(a=gs\)、\(b=gt\) とおく
と言う設定から問題をスタートしていきます。
上と同様に、\(3\) 文字 \(a\)、\(b\)、\(c\) の最大公約数を \(g\) として、
互いに素な整数 \(s\)、\(t\)、\(u\) を用いて、\(a=gs\)、\(b=gt\)、\(c=gu\) とおいても悪くはないのですが、条件として弱くなります。
その理由としては、\(3\) 文字が互いに素だからと言って、それぞれの \(2\) 文字の関係までは分からないという点です。
《例》『 \(2\) と \(3\) と \(6\) 』について考えると、
この \(3\) つの数の最大公約数は \(1\) になりますが、
\(2\) と \(6\) だけに注目すると最大公約数は \(2\) になりますし、
\(3\) と \(6\) だけに注目すると最大公約数は \(3\) になります。
\(3\) 文字が互いに素という条件よりも、もっと強い条件で設定した方がよい！
そこで、
\(3\) 文字 \(a\)、\(b\)、\(c\) の最大公約数が \(2\) 以上のとき
素数 \(p\) を用いて、\(a\)、\(b\)、\(c\) はすべて \(p\) の倍数
つまり、\(a=px\)、\(a=py\)、\(a=pz\) とおける
(１)の問題では、
最大公約数が \(1\) ではないと仮定し、(背理法の利用)
\(a+b+c=px\)、\(ab+bc+ca=py\)、\(abc=pz\) とおくことからスタート．
手が出なかった人は、ここからもう一度考えてみよう！
(１)解答
\(a+b+c\)、\(ab+bc+ca\)、\(abc\) の最大公約数が \(1\) でないと仮定する．
このとき、整数 \(x\)、\(y\)、\(z\) と、素数 \(p\) を用いて、
\(a+b+c=px\) ・・・①
\(ab+bc+ca=py\) ・・・②
\(abc=pz\) ・・・③ とおける．
③より、\(p\) は素数であるから、\(a\)、\(b\)、\(c\) の少なくとも \(1\) つは \(p\) の倍数となる．
\(a\)、\(b\)、\(c\) には対称性があるので、\(a\) が \(p\) の倍数としても一般性は失わない．
よって、整数 \(k\) を用いて \(a=pk\) ・・・④ とおける．
①、④より、\(b+c=px-pk=p(x-k)\) となり、\(b+c\) は \(p\) の倍数 ・・・⑤
②、④より、\(bc=py-pkb-cpk=p(y-bk-ck)\)
となり、\(bc\) は \(p\) の倍数 ・・・⑥
⑥より、\(b\)、\(c\) の少なくとも一方は \(p\) の倍数となり、対称性から \(b\) が \(p\) の倍数であるとして一般性を失わない．
このとき⑤から、上と同様に考えていくと、\(c\) も \(p\) の倍数であることが分かる．
よって \(b\)、\(c\) はともに \(p\) の倍数．
また、\(a\) も \(p\) の倍数であることから、条件の \(a\)、\(b\)、\(c\) の最大公約数が \(1\) であることに矛盾するため、\(a+b+c\)、\(ab+bc+ca\)、\(abc\) の最大公約数は \(1\) である．
(２)考え方
\(3\) 文字の対称式
\(a^2+b^2+c^2\)、\(a^3+b^3+c^3\) の形、さらには(１)において基本対称式を扱った流れから、
・\(a^2+b^2+c^2=(a+b+c)^2-2(ab+bc+ca)\)
・\(a^3+b^3+c^3-3abc=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)\)
の公式が頭の中に浮かんでほしい！
ユークリッド互除法の利用
【ユークリッドの互除法】
\(2\) つの自然数 \(a\) 、\(b\) において、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) とすると
\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい
(２)解答
\(a^2+b^2+c^2=(a+b+c)^2-2(ab+bc+ca)\) より、ユークリッド互除法から
\(a+b+c\) と \(a^2+b^2+c^2\) の最大公約数は、
\(a+b+c\) と \(2(ab+bc+ca)\) の最大公約数に等しい
また、
\(a^3+b^3+c^3=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)+3abc\) より、ユークリッド互除法から
\(a+b+c\) と \(a^3+b^3+c^3\) の最大公約数は、
\(a+b+c\) と \(3abc\) の最大公約数に等しい
つまり、\(a+b+c\)、\(a^2+b^2+c^2\)、\(a^3+b^3+c^3\) の最大公約数は、
\(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数に等しい．
(１)の結果から、\(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数の候補は、
\(1\) または \(2\) または \(3\) または \(6\) のいずれか．
\(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数の候補は、
\(1\) または \(2\) または \(3\) または \(6\) のいずれかであるので、それぞれを満たす \(a\)、\(b\)、\(c\) が存在するかどうかを考える．
現時点では答えの可能性(候補)です。
それぞれを満たす \(a\)、\(b\)、\(c\) が \(1\) つでも
存在すればＯＫ！
とりあえず適当に実験をしてみましょう！
・\((a,b,c)=(1,1,1)\) のとき
\(a+b+c=3\)、\(2(ab+bc+ca)=6\)、\(3abc=3\) より、
この \(3\) つの最大公約数は \(3\) となる．
・\((a,b,c)=(1,1,2)\) のとき
\(a+b+c=4\)、\(2(ab+bc+ca)=10\)、\(3abc=6\) より、
この \(3\) つの最大公約数は \(2\) となる．
・\((a,b,c)=(1,1,3)\) のとき
\(a+b+c=5\)、\(2(ab+bc+ca)=14\)、\(3abc=9\) より、
この \(3\) つの最大公約数は \(1\) となる．
・\((a,b,c)=(1,1,4)\) のとき
\(a+b+c=6\)、\(2(ab+bc+ca)=18\)、\(3abc=12\) より、
この \(3\) つの最大公約数は \(6\) となる．
実験の結果、答えの候補の『 \(1\) または \(2\) または \(3\) または \(6\) 』 のすべてが存在することが確認できました！
したがって、求める値は、\(1\) または \(2\) または \(3\) または \(6\)
コメント