対称式の最大公約数 – 2022年東工大 数学 第2問
2022年東工大 数学 第2問 は対称式の最大公約数に関する問題です。問題文は以下のとおりです。
3つの正の整数 a,b,c の最大公約数が1であるとき, 次の問いに答えよ.
（１） a+b+c,bc+ca+ab,abc の最大公約数は1であることを示せ.
（２） a+b+c,a^2+b^2+c^2,a^3+b^3+c^3 の最大公約数となるような正の整数をすべて求めよ.
なかなかすっきりした問題文です。回答もこんなふうにすっきり出せると良いのですが。それでは、早速見ていきましょう。
2022年東工大 数学 第2問 小問1の解法
問題文は解と係数の公式を使えと言っているようにしか見えないので、その誘いに乗ってみます。
整数係数の3次式 f(x) を、
\begin{aligned}
f(x) = & x^3 -(a+b+c)x^2 \\
& + (bc+ca+ab)x-abc \\
= &(x-a)(x-b)(x-c)
\end{aligned}と定義します。
a+b+c,bc+ca+ab,abc の最大公約数が1より大きいと仮定します。その最大公約数は少なくとも1つの素因数を持つので、それを p と置きます。
すると、 f(p) は p の倍数なので、当然 (p-a)(p-b)(p-c) も p の倍数です。 p は素数なのですから、 p-a,p-b,p-c の少なくとも1つは p の倍数であり、したがって a,b,c の少なくとも1つは p の倍数です。
そこで、 a が p の倍数であるとします。このとき、 a+b+c は p の倍数なのですから、 b+c も p の倍数です。また、 bc+ca+ab=bc+ a(b+c) は p の倍数なので、 bc も p の倍数です。
ここで改めて、整数係数の2次式 g(x) を、
\begin{aligned}
g(x) & = x^2-(b+c) x +bc \\
& = (x-b)(x-c)
\end{aligned}と定義すると、 g(p) は p の倍数なので、 f(x) の時と同じように、 b,c のいずれかは p の倍数です。
ところが、 b+c は p の倍数なので、一方が p の倍数ならもう一方も p の倍数です。
したがって、素数 p は a,b,c の公約数ですが、これは a,b,c の最大公約数が1であることに矛盾します。ゆえに a+b+c,bc+ca+ab,abc の最大公約数が1であることが証明できました。
2022年東工大 数学 第2問 小問2の解法
１が最大公約数になり得ることを示す
a+b+c,a^2+b^2+c^2,a^3+b^3+c^3 の最大公約数が1であるというのは、普通に有りそうですが、実際、 (a,b,c) =(1,2,4) のとき、
\begin{aligned}
a+b+c &=7 \\
a^2+b^2+c^2 & = 21 \\
a^3+b^3+c^3 &= 73
\end{aligned}であり、確かに最小公倍数は1です。
最大公約数の素因数を求める
a+b+c,a^2+b^2+c^2,a^3+b^3+c^3 の最大公約数が2以上であるとします。このとき、その最大公約数は少なくとも1つの素因数を持つので、それを p と置きます。
小問1の結果を利用するため、 bc+ab+ac,abc を a+b+c,a^2+b^2+c^2,a^3+b^3+c^3 で表します。 bc+ab+ac,abc が p の倍数になるとかならないとか言う議論に持ち込み、互いに素なんだからそれはあり得ない、という背理法的手法によって、 p が満たすべき条件を導出します。
まず、おなじみの等式
a^2+b^2+c^2 = (a+b+c)^2-2(bc+ab+ac)
より、
\begin{aligned}
2(bc+ab+ac) = (a+b+c)^2 -a^2+b^2+c^2 \\
\cdots (1)
\end{aligned}です。また、
\begin{aligned}
& a^3+b^3+c^3 -3abc \\
= &(a+b+c)(a^2+b^2+c^2-(bc+ab+ac)) \\
= &(a+b+c) \\
& \times \left \{ \begin{aligned} & a^2+b^2+c^2 \\
& + \frac{a^2+b^2+c^2-(a+b+c)^2 }{2} \end{aligned} \right \}\\
= &(a+b+c) \\
& \times \left \{\frac{3(a^2+b^2+c^2)-(a+b+c)^2 }{2} \right\} \\
\end{aligned}なので、
\begin{aligned}
6abc= & 2(a^3+b^3+c^3) \\
&+(a+b+c)^3 \\
& -3(a+b+c)(a^2+b^2+c^2) \\
& \text{ } \cdots (2)
\end{aligned}です。
式 (2) において、右辺は p の倍数なので左辺もそうです。したがって、 p が 2 でも 3 でもない場合、 abc は p の倍数です。
また、式 (1) の右辺は p の倍数なので左辺もそうです。 p が2でない場合、 bc+ab+ac は p の倍数です。
a+b+c も p の倍数なので、これは小問1の結果に矛盾します。ゆえに、 p は2か3のどちらかです。すなわち、 a+b+c,a^2+b^2+c^2,a^3+b^3+c^3 の最大公約数を m とおくとき、 m が2以上なら2か3しか素因数を持たず、
m = 2^i3^j \\
(i,j \text{は非負整数)}と素因数分解されます。
素因数の次数の最大値を求める
問題文の内容から見て、m は無限にあるわけではなく、素因数の次数 i,j には上限があると考えられます。その上限を調べます。
まず、 22 = 4 が公約数としてあり得るのかどうかを考えます。
m が4で割り切れると仮定します。すると、式(1)の右辺は4の倍数なので、 bc+ab+ac は2の倍数です。
また、式(2)の右辺も4の倍数なので、 abc は2の倍数でなければなりません。 a+b+c,bc+ab+ac,abc が2を公約数に持つことになるので、これは小問1の結果に矛盾します。したがって、4は公約数ではありません。
４は公約数ではありませんが、8や16など、次数が2以上のすべての2のべき乗は4の倍数なので、やはり公約数ではありません。 したがって、 i は0か1です。
次に、 m が33 = 9で割り切れると仮定します。すると、式(1)により、 bc+ab+ac は9の倍数です。
また、式(2)により、 abc は3の倍数です。 a+b+c,bc+ab+ac,abc が3を公約数に持つことになるので、小問1の結果に矛盾します。したがって9以上の3のべき乗は公約数ではないので、 j は0か1です。
以上をまとめると、 a+b+c,a^2+b^2+c^2,a^3+b^3+c^3 の最大公約数 m が2以上であるための必要条件は、 m の素因数が2か3であり、かつその次数が高々1であることです。言い換えると、最大公約数 m の取り得る値は、1以外では2,3,6です。
最大公約数であるための十分条件
最後に、 m が最大公約数であることの十分条件を確認します。つまり、 2や3や6が本当に最大公約数になりえるのか、実際に計算してみます。実例が示せればOKです。
まず2の場合です。 (a,b,c) = (1,1,2) のとき、
\begin{aligned}
a+b+c &=4 \\
a^2+b^2+c^2 & = 6 \\
a^3+b^3+c^3 &= 10
\end{aligned}なので、2は確かに最大公約数です。
次に3の場合です。 (a,b,c) = (1,1,1) のとき、
\begin{aligned}
a+b+c &=3 \\
a^2+b^2+c^2 & = 3 \\
a^3+b^3+c^3 &= 3
\end{aligned}なので、3は確かに最大公約数です。
残りは6の場合です。 (a,b,c) = (1,1,4) のとき、
\begin{aligned}
a+b+c &=6 \\
a^2+b^2+c^2 & = 18 \\
a^3+b^3+c^3 &= 66
\end{aligned}なので、6は確かに最大公約数です。
以上、１，２，３，６のみが最大公約数になり得ることが示せました。
解法のポイント
対称式の問題なので、まずは解と係数の公式が適用できないか、検討してみましょう。小問1ではこれがハマり、簡単に証明できました。
また、本問のような割った／割れない的問題の場合、割る数の範囲を素数に絞り込めないか、検討してみましょう。 a,b,c が2以上の自然数で、
ab=c
の関係が有り、 c が素数 p の倍数であるとします。
このとき、もし a が p と素なら、 b は p の倍数です。このように、割る数が素数なら、ある数がその数でわり切れるかどうかを、割と簡単に判定できます。重宝するやり方なので、ぜひ覚えておきましょう。