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

【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$ の最大公約数が $7$ だと仮定する

このとき、

$a+b+c$ は $7$ の倍数となる．

$2$ と $7$ は互いに素であることから、 $ab+bc+ca$ も $7$ の倍数．

$3$ と $7$ は互いに素であることから、 $abc$ も $7$ の倍数．

しかしこれは(１)に矛盾する．

よって $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$ つでも

存在すればＯＫ！

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

・ $(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$