トップ› 東京工業大学› 2015年› 理系第5問

東京工業大学 2015年理系第5問解説

方針・初手

本問は、整数 $a, b$ が「相異なる素数の積」である $n$ の約数という特殊な条件を持っていることが最大の鍵である。この条件により、$n$ のすべての約数は平方因子を持たず、各素因数の指数は $0$ または $1$ に限られる。約数や倍数、最大公約数、最小公倍数に関する問題は、各素因数の指数に着目して比較するのが定石である。最大公約数 $G$ は指数の最小値（$\min$）、最小公倍数 $L$ は指数の最大値（$\max$）をとることで表せるため、まずは $a, b$ を素因数分解した形で設定し、指数の関係式に帰着させて証明を進める。

解法1

$n$ は相異なる素数の積であるため、$n = p_1 p_2 \dots p_k$ （各 $p_i$ は相異なる素数）とおける。 $a, b$ は $n$ の約数であるから、各素因数の指数を $\alpha_i, \beta_i \in \{0, 1\}$ として、

$$ a = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k} $$

$$ b = p_1^{\beta_1} p_2^{\beta_2} \dots p_k^{\beta_k} $$

と表すことができる。このとき、最大公約数 $G$ と最小公倍数 $L$ はそれぞれ、

$$ G = p_1^{\min(\alpha_1, \beta_1)} p_2^{\min(\alpha_2, \beta_2)} \dots p_k^{\min(\alpha_k, \beta_k)} $$

$$ L = p_1^{\max(\alpha_1, \beta_1)} p_2^{\max(\alpha_2, \beta_2)} \dots p_k^{\max(\alpha_k, \beta_k)} $$

と表される。したがって、$f(a, b) = \frac{L}{G}$ は、

$$ f(a, b) = p_1^{\gamma_1} p_2^{\gamma_2} \dots p_k^{\gamma_k} $$

（ただし $\gamma_i = \max(\alpha_i, \beta_i) - \min(\alpha_i, \beta_i)$）となる。

(1) $\alpha_i, \beta_i$ はそれぞれ $0$ または $1$ のいずれかであるため、$(\alpha_i, \beta_i)$ の組は $(0, 0), (1, 0), (0, 1), (1, 1)$ の4通りである。それぞれについて $\gamma_i = \max(\alpha_i, \beta_i) - \min(\alpha_i, \beta_i)$ の値を計算すると、

$(0, 0)$ のとき：$0 - 0 = 0$
$(1, 0)$ のとき：$1 - 0 = 1$
$(0, 1)$ のとき：$1 - 0 = 1$
$(1, 1)$ のとき：$1 - 1 = 0$

いずれの場合も $\gamma_i \in \{0, 1\}$ となる。すべての素因数 $p_i$ について指数 $\gamma_i$ が $0$ または $1$ であるため、$f(a, b)$ は $n$ の約数である。

(2) $f(a, b) = b$ であるとき、各素因数 $p_i$ の指数を比較すると、すべての $i$ について $\gamma_i = \beta_i$、すなわち

$$ \max(\alpha_i, \beta_i) - \min(\alpha_i, \beta_i) = \beta_i $$

が成り立つ。

(i)

$\beta_i = 0$ のとき等式は $\max(\alpha_i, 0) - \min(\alpha_i, 0) = 0$ となる。 $\alpha_i \ge 0$ であるから、$\max(\alpha_i, 0) = \alpha_i$、$\min(\alpha_i, 0) = 0$ であり、 $\alpha_i - 0 = 0$ より $\alpha_i = 0$ を得る。

(ii)

$\beta_i = 1$ のとき等式は $\max(\alpha_i, 1) - \min(\alpha_i, 1) = 1$ となる。 $\alpha_i \le 1$ であるから、$\max(\alpha_i, 1) = 1$、$\min(\alpha_i, 1) = \alpha_i$ であり、 $1 - \alpha_i = 1$ より $\alpha_i = 0$ を得る。

いずれの場合も $\alpha_i = 0$ となるため、すべての $i$ について $\alpha_i = 0$ である。したがって、$a = p_1^0 p_2^0 \dots p_k^0 = 1$ である。

(3) $m$ が $n$ の約数であるとき、$S(m)$ は $m$ の素因数分解における各素因数の指数の総和に等しい。よって、

$$ S(a) = \sum_{i=1}^k \alpha_i, \quad S(b) = \sum_{i=1}^k \beta_i, \quad S(f(a, b)) = \sum_{i=1}^k \gamma_i $$

である。ここで (1) の検討より、$\gamma_i$ は $\alpha_i$ と $\beta_i$ の値が異なるときに $1$、等しいときに $0$ となるため、差の絶対値を用いて $\gamma_i = |\alpha_i - \beta_i|$ と表すことができる。整数において和と差の偶奇は常に一致するため、

$$ \gamma_i = |\alpha_i - \beta_i| \equiv \alpha_i - \beta_i \equiv \alpha_i + \beta_i \pmod 2 $$

が成り立つ。ゆえに、

$$ \gamma_i + \alpha_i + \beta_i \equiv (\alpha_i + \beta_i) + \alpha_i + \beta_i = 2(\alpha_i + \beta_i) \equiv 0 \pmod 2 $$

となり、各 $i$ について $\gamma_i + \alpha_i + \beta_i$ は偶数である。したがって、

$$ S(f(a, b)) + S(a) + S(b) = \sum_{i=1}^k \gamma_i + \sum_{i=1}^k \alpha_i + \sum_{i=1}^k \beta_i = \sum_{i=1}^k (\gamma_i + \alpha_i + \beta_i) $$

は偶数の和となるため、偶数である。

解法2

$n$ は相異なる素数の積であるため、$n$ の約数は、素因数の全体集合 $U = \{p_1, p_2, \dots, p_k\}$ の部分集合と1対1に対応する。任意の $n$ の約数 $x$ に対して、その素因数の集合を $X \subseteq U$ と表すことにする。このとき、最大公約数 $G$ に対応する集合は $A \cap B$、最小公倍数 $L$ に対応する集合は $A \cup B$ となる。また、$n$ の約数 $y$ が $x$ で割り切れるとき、$\frac{y}{x}$ に対応する素因数の集合は $Y \setminus X$（差集合）となる。したがって、$f(a, b) = \frac{L}{G}$ に対応する素因数の集合を $C$ とすると、

$$ C = (A \cup B) \setminus (A \cap B) $$

となる。

(1) $C = (A \cup B) \setminus (A \cap B)$ は、全体集合 $U$ の部分集合である $A \cup B$ から要素を除いた集合であるため、これも明らかに $U$ の部分集合である。よって、$f(a, b)$ は $n$ の約数である。

(2) $f(a, b) = b$ であるとき、対応する集合について $C = B$、すなわち

$$ (A \cup B) \setminus (A \cap B) = B $$

が成り立つ。この式の左辺は、集合 $A$ と $B$ の「どちらか一方にのみ属する要素」の集合（対称差）である。これが $B$ 全体と一致するということは、「$B$ の要素はすべて左辺に含まれる」かつ「左辺に含まれる要素はすべて $B$ の要素である」ことを意味する。 $B$ の要素がすべて $(A \cup B) \setminus (A \cap B)$ に含まれるためには、$A$ と共通する要素があってはならないため、$A \cap B = \emptyset$ である。また、このとき左辺は $A \cup B$ となるが、これが $B$ と一致するためには、 $A$ 側の要素が存在してはならないため、$A \setminus B = \emptyset$ である。 $A \cap B = \emptyset$ かつ $A \setminus B = \emptyset$ より、$A = \emptyset$ でなければならない。素因数を持たない $n$ の約数は $1$ のみであるから、$a = 1$ である。

(3) $m$ が $n$ の約数であるとき、$S(m)$ は対応する素因数の集合の要素数に等しいため、

$$ S(a) = |A|, \quad S(b) = |B|, \quad S(f(a, b)) = |C| $$

である。集合 $C = (A \cup B) \setminus (A \cap B)$ の要素数 $|C|$ は、

$$ |C| = |A \cup B| - |A \cap B| $$

と表せる。ここで、和集合の要素数の公式 $|A \cup B| = |A| + |B| - |A \cap B|$ を代入すると、

$$ |C| = (|A| + |B| - |A \cap B|) - |A \cap B| = |A| + |B| - 2|A \cap B| $$

となる。したがって、

$$ S(f(a, b)) + S(a) + S(b) = |C| + |A| + |B| $$

$$ = (|A| + |B| - 2|A \cap B|) + |A| + |B| $$

$$ = 2(|A| + |B| - |A \cap B|) $$

これは $2 \times (\text{整数})$ の形をしているため、偶数である。

解説

整数問題において、約数や公倍数の条件を処理する際は、素因数分解して各素数の「指数」に関する問題にすり替えるのが非常に有効である。特に本問のように「相異なる素数の積（平方因子を持たない）」という条件がある場合、各素因数の指数は $0$ または $1$ の2値しかとらない。そのため、解法2のように部分集合を用いたベン図の世界（和集合、積集合、差集合、対称差）に翻訳して解くことも可能であり、見通しが格段に良くなる。