スポンサーリンク

2022東京工業大学・第2問【整数問題】3文字の対称式の最大公約数

数学(大学入試問題)

【2022東京工業大学・第2問】

(1)考え方・解答

(1)考え方

\(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)の問題では、

最大公約数が \(1\) ではないと仮定し、(背理法の利用)

\(a+b+c=px\)、\(ab+bc+ca=py\)、\(abc=pz\) とおくことからスタート.

手が出なかった人は、ここからもう一度考えてみよう!

 

(1)解答

\(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\) である.

(2)考え方

\(3\) 文字の対称式

\(a^2+b^2+c^2\)、\(a^3+b^3+c^3\) の形、さらには(1)において基本対称式を扱った流れから、

・\(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\) の最大公約数に等しい

(2)解答

\(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\) の最大公約数に等しい.

(1)の結果から、\(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数の候補は、

\(1\) または \(2\) または \(3\) または \(6\) のいずれか.

仮に \(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数が \(7\) だと仮定する

このとき、

\(a+b+c\) は \(7\) の倍数となる.

\(2\) と \(7\) は互いに素であることから、\(ab+bc+ca\) も \(7\) の倍数.

\(3\) と \(7\) は互いに素であることから、\(abc\) も \(7\) の倍数.

しかしこれは(1)に矛盾する.

よって \(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数は \(7\) とはならないことが分かる.

同様に考え、最大公約数の候補は \(1\) または \(2\) または \(3\) または \(6\) のいずれかと分かる.

\(a+b+c\)、\(2(ab+bc+ca)\)、\(3abc\) の最大公約数の候補は、

\(1\) または \(2\) または \(3\) または \(6\) のいずれかであるので、それぞれを満たす \(a\)、\(b\)、\(c\) が存在するかどうかを考える.

現時点では答えの可能性(候補)です。

それぞれを満たす \(a\)、\(b\)、\(c\) が \(1\) つでも

存在すればOK!

とりあえず適当に実験をしてみましょう!

・\((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\)

 

 

 

コメント

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