トップ› 東京工業大学› 2022年› 理系第2問

東京工業大学 2022年理系第2問解説

方針・初手

(1) は背理法を用い、最大公約数が $1$ より大きい（共通の素因数 $p$ をもつ）と仮定して、与えられた $\gcd(a, b, c) = 1$ という条件に矛盾することを示す。 (2) は基本対称式を用いて $a^2+b^2+c^2$ と $a^3+b^3+c^3$ を和・積で表し、ユークリッドの互除法の原理を用いて最大公約数の候補を絞り込む。その際、(1) で示した結果を有効活用する。

解法1

(1)

$A = a+b+c, B = bc+ca+ab, C = abc$ とおく。

$A, B, C$ の最大公約数が $1$ より大きいと仮定し、その素因数の $1$ つを $p$ とする。すなわち、$p \mid A, p \mid B, p \mid C$ と仮定する。

$p \mid C$ つまり $p \mid abc$ であり、$p$ は素数であるから、$p$ は $a, b, c$ のうち少なくとも $1$ つを割り切る。対称性から、$p \mid a$ と仮定してよい。

このとき、$B = a(b+c) + bc$ について考える。$p \mid B$ かつ $p \mid a$ であるから、

$$ p \mid bc $$

が成り立つ。$p$ は素数であるから、$p \mid b$ または $p \mid c$ である。対称性から $p \mid b$ と仮定してよい。

さらに、$A = a+b+c$ について考える。$p \mid A, p \mid a, p \mid b$ であるから、

$$ p \mid c $$

が成り立つ。

以上より $p \mid a, p \mid b, p \mid c$ となり、$p$ は $a, b, c$ の公約数となる。

しかし、これは $\gcd(a, b, c) = 1$ であることに矛盾する。したがって、$A, B, C$ の最大公約数は $1$ である。

(2)

$x = a+b+c, y = bc+ca+ab, z = abc$ とおく。(1)より、$\gcd(x, y, z) = 1$ である。

与えられた $3$ つの式を基本対称式 $x, y, z$ で表すと、以下のようになる。

$$ a+b+c = x $$

$$ a^2+b^2+c^2 = x^2 - 2y $$

$$ a^3+b^3+c^3 = x^3 - 3xy + 3z $$

これらの最大公約数を $g$ とする。

ユークリッドの互除法の原理 $\gcd(A, B) = \gcd(A, B - qA)$ を用いて $g$ を言い換える。

$$ g = \gcd(x, x^2 - 2y, x^3 - 3xy + 3z) $$

$$ = \gcd(x, (x^2 - 2y) - x \cdot x, (x^3 - 3xy + 3z) - x^2 \cdot x) $$

$$ = \gcd(x, -2y, -3xy + 3z) $$

公約数は $x$ の約数でもあるため、第 $3$ 項に含まれる $-3xy$ は公約数で割り切れる。したがってこれを消去し、符号を正に直すことで、

$$ g = \gcd(x, 2y, 3z) $$

となる。

$g$ の素因数 $p$ を考える。$p \mid x, p \mid 2y, p \mid 3z$ である。

もし $p \ge 5$ の素数ならば、$p \nmid 2$ かつ $p \nmid 3$ であるから、 $p \mid 2y \implies p \mid y$ $p \mid 3z \implies p \mid z$ となり、$p$ は $x, y, z$ の公約数となる。これは $\gcd(x, y, z) = 1$ に矛盾する。ゆえに、$g$ の素因数は $2$ と $3$ のみであり、$g = 2^m 3^n$ （$m, n$ は $0$ 以上の整数）と表せる。

(i)

$m$ について

$m \ge 2$ と仮定する。このとき $4 \mid g$ であり、$4 \mid x$ かつ $4 \mid 2y \implies 2 \mid y$ が成り立つ。$a, b, c$ の偶奇の組合せを考える。$\gcd(a, b, c) = 1$ より $3$ つとも偶数であることはない。

$1$ つが偶数、$2$ つが奇数のとき：$x = \text{偶}+\text{奇}+\text{奇} = \text{偶}$、$y = \text{偶}\cdot\text{奇}+\text{偶}\cdot\text{奇}+\text{奇}\cdot\text{奇} = \text{奇}$ となり、$2 \mid y$ に矛盾する。
$2$ つが偶数、$1$ つが奇数のとき：$x = \text{偶}+\text{偶}+\text{奇} = \text{奇}$ となり、$4 \mid x$ に矛盾する。
$3$ つとも奇数のとき：$x = \text{奇}+\text{奇}+\text{奇} = \text{奇}$ となり、$4 \mid x$ に矛盾する。

いずれの場合も矛盾するため、$m \le 1$ である。

(ii)

$n$ について

$n \ge 2$ と仮定する。このとき $9 \mid g$ であり、$9 \mid x, 9 \mid 2y \implies 3 \mid y, 9 \mid 3z \implies 3 \mid z$ が成り立つ。

$3 \mid z$ すなわち $3 \mid abc$ より、$a, b, c$ のうち少なくとも $1$ つは $3$ の倍数である。$\gcd(a, b, c) = 1$ より $3$ つとも $3$ の倍数であることはない。

$1$ つだけが $3$ の倍数のとき（例：$a$ が $3$ の倍数）：$y = ab+bc+ca \equiv bc \pmod 3$ となるが、$b, c$ は $3$ の倍数でないため $3 \mid y$ に矛盾する。
$2$ つが $3$ の倍数のとき（例：$a, b$ が $3$ の倍数）：$x = a+b+c \equiv c \pmod 3$ となるが、$c$ は $3$ の倍数でないため $9 \mid x$ に矛盾する。

いずれの場合も矛盾するため、$n \le 1$ である。

以上より $m \le 1, n \le 1$ となり、$g = 2^m 3^n$ の候補は $1, 2, 3, 6$ に限られる。これらが実際に最大公約数として現れるかを確かめる。

$(a, b, c) = (1, 2, 2)$ のとき、$x=5, x^2-2y=9, x^3-3xy+3z=17$ より $g = \gcd(5, 9, 17) = 1$
$(a, b, c) = (1, 1, 2)$ のとき、$x=4, x^2-2y=6, x^3-3xy+3z=10$ より $g = \gcd(4, 6, 10) = 2$
$(a, b, c) = (1, 1, 1)$ のとき、$x=3, x^2-2y=3, x^3-3xy+3z=3$ より $g = \gcd(3, 3, 3) = 3$
$(a, b, c) = (1, 1, 4)$ のとき、$x=6, x^2-2y=18, x^3-3xy+3z=66$ より $g = \gcd(6, 18, 66) = 6$

すべて条件を満たす $(a, b, c)$ の組が存在する。

解説

整数分野における「最大公約数の絞り込み」の典型的な難問である。(1) の結果を (2) にどう結びつけるかが鍵となる。

基本対称式を用いた式の変形は受験数学の定石だが、最大公約数を求める際に「ユークリッドの互除法」を用いることで、$\gcd(x, x^2 - 2y, x^3 - 3xy + 3z)$ という複雑な式を $\gcd(x, 2y, 3z)$ という非常に扱いやすい形に帰着できるのが最大のポイントである。あとは素因数を $2$ と $3$ に絞り、偶奇や $3$ の剰余に関する場合分けを丁寧に行うことで完答を目指す。