東工大2015の整数問題を整数を使わずに解く

1146

はじめに

どうもこんにちは🐟️🍊みかん🍊🐟️です。今回は東工大2015年数学大問5を綺麗に解くことができたのでサクッと溶かしていこうと思います。

こんな問題です。

東工2015年数学大問5

$n$ を相異なる素数 $p_{1}, p_{2}, \dots, p_{k} (k \geq 1)$ の積とする。 $a, b$ を $n$ を約数とするとき、 $a, b$ の最大公約数を $G$ 、最小公倍数を $L$ とし、
$f (a, b) = \frac{L}{G}$
とする。
(1) $f (a, b)$ が $n$ の約数であることを示せ。
(2) $f (a, b) = b$ ならば、 $a = 1$ であることを示せ。
(3) $m$ を自然数とするとき、 $m$ の約数であるような素数の個数を $S (m)$ とする。 $S (f (a, b)) + S (a) + S (b)$ が偶数であることを示せ。

皆さんはどのような解き方をしますか。以下、僕の答案を挙げるので先に解きたい人はスクロールしないようにしてください。念のため少し広めにスペース空けておきます。

↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

解く

小問1

まず $N = {1, 2, \dots, k}$ として、 $A, B$ をその部分集合とすると、 $n, a, b$ は次のように表すことができる。

$\begin{aligned} n & = \prod_{u \in N} p_{u} \\ a & = \prod_{u \in A} p_{u} \\ b & = \prod_{u \in B} p_{u} \end{aligned}$

そこで、既に素因数分解されていることを考えれば、 $G, L$ は直接計算できて、

$\begin{aligned} G & = \prod_{u \in A \cap B} p_{u} \\ L & = \prod_{u \in A \cup B} p_{u} \end{aligned}$

となる。従って各素因数で $f (a, b)$ で割りきれるか割りきれないかを考えることにより

$\begin{aligned} f (a, b) & = \frac{L}{G} \\ = \prod_{u \in (A \cup B) ∖ (A \cap B)} p_{u} \end{aligned}$

となり、 $A, B$ が $N$ の部分集合であるから $(A \cup B) ∖ (A \cap B)$ も $N$ の部分集合になるから、先の表示により $f (a, b)$ は $n$ で割りきれる。

小問2

$f (a, b) = b$ より、
$\prod_{u \in (A \cup B) ∖ (A \cap B)} p_{u} = \prod_{u \in B} p_{u}$
となり、素因数分解の一意性により $B = (A \cup B) ∖ (A \cap B)$ である。さて、ここで $A \cap B$ が空集合ではないと仮定すると、ある $γ \in A \cap B$ がとれ、特に $γ \in B$ となる。しかし、差集合の定義と $γ \in A \cap B$ であることから $γ \notin B$ であることが分かり、これは矛盾である。従って $A \cap B = \emptyset$ となる。よって $a$ と $b$ とが互いに素になるから、 $G = 1, L = a b$ となることが分かる。従って $f (a, b)$ の定義式から
$\begin{array}{r} b = f (a, b) = \frac{L}{G} = a b . \end{array}$
ここで $b \neq 0$ であるから、最右辺と最左辺を $b$ で割ることにより所望の主張、即ち
$a = 1$
を得る。

小問3

$# A - # (A \cap B) + # B = # (A \cup B)$ を用いて直接計算すると、 $A \cap B$ が $A \cup B$ の部分集合になることを踏まえれば
$\begin{aligned} S (f (a, b)) + S (a) + S (b) & = S (\prod_{u \in (A \cup B) ∖ (A \cap B)} p_{u}) + S (\prod_{u \in A} p_{u}) + S (\prod_{u \in B} p_{u}) \\ = # (A \cup B) - # (A \cap B) + # A + # B \\ = # (A \cup B) + # (A \cup B) \\ = 2 # (A \cup B) \end{aligned}$

となり、 $N$ が有限集合であるからその部分集合 $A \cup B$ も有限集合で、即ち $# (A \cup B)$ は整数となるので $2 # (A \cup B)$ は偶数。従って $S (f (a, b)) + S (a) + S (b)$ は偶数である。

終わりに

あまり想定解法ではないことが用意に想定されますが、このようにすると瞬殺できます。整数問題はFermat小定理やLTE、Kummerの補題のような有名な整数の性質を証明する動作をなぞるか、因数分解を用いることで溶かせるもの(要するに典型)が多いなかで、実質的には集合操作のみで解けるものに出会ったことがなかったので記事にしてみました。集合操作でやればほばほぼ作業ゲーですね。

ここからは完全に僕の感想になりますが、この問題は東工の問題としては非常に易しい部類の問題なので、全完するなら大問平均 $36$ 分しか時間がないこと、また平均難易度がそれなりに高いことを踏まえると、数学を得点元にするなら $10$ 分以内に落としておきたいところです。実際 $2015$ の問題なら(数学を得点元にしようとする人なら)普通に全完狙えそうなので早く落とすことに越したことはないですね。実際僕が当該年度の問題を解いた際は4完だった(下らないミスをした)ので、そこまで難易度の高い問題ではなかったでしょうね。