トップ› 東京工業大学› 2007年› 理系第1問

東京工業大学 2007年理系第1問解説

方針・初手

与えられた整数が素数 $p$ で何回割り切れるか（素因数 $p$ の個数）に注目して数え上げる問題である。

(1) は、「$p^m$ の倍数の個数」から「$p^{m+1}$ の倍数の個数」を引くことで求められる。 (2) は、(1) の結果を利用する。$x$ がちょうど $p^i$ で割り切れ、$y$ がちょうど $p^j$ で割り切れるとしたとき、積 $xy$ が $p^{n+1}$ で割り切れる条件は $i+j \geqq n+1$ である。$x$ の持つ素因数 $p$ の個数で場合分けをして、対応する $y$ の個数を数え上げる。

解法1

(1)

$1$ から $p^{n+1}$ までの整数のうち、$p^m$ で割り切れる（すなわち $p^m$ の倍数である）ものの個数は、

$$ \frac{p^{n+1}}{p^m} = p^{n+1-m} $$

である。

また、$1$ から $p^{n+1}$ までの整数のうち、$p^{m+1}$ で割り切れる（すなわち $p^{m+1}$ の倍数である）ものの個数は、

$$ \frac{p^{n+1}}{p^{m+1}} = p^{n-m} $$

である。

求めるものは、$p^m$ で割り切れる整数のうち、$p^{m+1}$ で割り切れない整数の個数であるから、

$$ p^{n+1-m} - p^{n-m} = p^{n-m}(p - 1) $$

となる。

(2)

$1$ から $p^{n+1}$ までの整数 $z$ が、$p^k$ で割り切れ $p^{k+1}$ で割り切れないとき、「$z$ はちょうど $p^k$ で割り切れる」と表現し、これを満たす $k$ の値を $v(z)$ と表すことにする。ただし、$z = p^{n+1}$ のときは $p^{n+2}$ 以上の素因数を含まないため、$v(p^{n+1}) = n+1$ とする。

$1$ から $p^{n+1}$ までの整数 $x, y$ の積 $xy$ が $p^{n+1}$ で割り切れるための条件は、

$$ v(x) + v(y) \geqq n+1 $$

である。

$v(x) = i$ ($0 \leqq i \leqq n+1$) を満たすように $x$ を固定したとき、条件を満たす $y$ について考える。 $y$ が満たすべき条件は $v(y) \geqq n+1-i$ となるが、これは「$y$ が $p^{n+1-i}$ の倍数である」ことと同値である。 $1$ から $p^{n+1}$ までの整数のうち、$p^{n+1-i}$ の倍数の個数は、

$$ \frac{p^{n+1}}{p^{n+1-i}} = p^i $$

である。

ここで、(1) の結果より、$v(x) = i$ となる $x$ の個数は、 $0 \leqq i \leqq n$ のとき、$p^{n-i}(p-1)$ 個である。また、$i = n+1$ のとき、$x = p^{n+1}$ の $1$ 個のみである。

したがって、条件を満たす組 $(x, y)$ の個数は、各 $i$ に対する「$x$ の個数 $\times$ $y$ の個数」の総和として求められる。

$$ \sum_{i=0}^{n} \left\{ p^{n-i}(p-1) \times p^i \right\} + \left( 1 \times p^{n+1} \right) $$

この式を計算すると、

$$ \sum_{i=0}^{n} p^n(p-1) + p^{n+1} $$

シグマの中身は $i$ に依存しないため、

$$ (n+1)p^n(p-1) + p^{n+1} $$

これを整理して、

$$ (n+1)p^{n+1} - (n+1)p^n + p^{n+1} $$

$$ (n+2)p^{n+1} - (n+1)p^n $$

となる。

解法2

(2) の別解

積 $xy$ が $p^{n+1}$ で割り切れない（余事象）場合を考える。 $x, y$ は $1$ 以上 $p^{n+1}$ 以下の整数であるから、全体の組 $(x, y)$ の個数は $(p^{n+1})^2 = p^{2n+2}$ 個である。

$xy$ が $p^{n+1}$ で割り切れない条件は、解法1と同様に $v(x) = i, v(y) = j$ とおくと、

$$ i + j \leqq n $$

である。このとき、$0 \leqq i \leqq n$ であり、各 $i$ に対して $j$ は $0 \leqq j \leqq n-i$ を満たす。

$i$ を固定したとき、条件を満たす $y$ は、「$p^0$ で割り切れ $p^1$ で割り切れないもの」から「$p^{n-i}$ で割り切れ $p^{n-i+1}$ で割り切れないもの」までの和集合に属する。これはすなわち、「$y$ が $p^{n-i+1}$ で割り切れない」ことと同値である。 $1$ から $p^{n+1}$ までの整数のうち、$p^{n-i+1}$ で割り切れるものの個数は $p^{n+1-(n-i+1)} = p^i$ 個であるため、$p^{n-i+1}$ で割り切れない $y$ の個数は、

$$ p^{n+1} - p^i $$

である。

(1)より $v(x) = i$ となる $x$ の個数は $p^{n-i}(p-1)$ であるため、余事象の組の個数は次のように計算できる。

$$ \sum_{i=0}^{n} p^{n-i}(p-1)(p^{n+1} - p^i) $$

$$ = \sum_{i=0}^{n} \left\{ p^{2n+1-i}(p-1) - p^n(p-1) \right\} $$

$$ = p^{2n+1}(p-1) \sum_{i=0}^{n} \left(\frac{1}{p}\right)^i - \sum_{i=0}^{n} p^n(p-1) $$

前者は等比数列の和であり、後者は定数の和であるから、

$$ = p^{2n+1}(p-1) \frac{1 - \left(\frac{1}{p}\right)^{n+1}}{1 - \frac{1}{p}} - (n+1)p^n(p-1) $$

$$ = p^{2n+1}(p-1) \frac{p^{n+1} - 1}{p^{n+1}} \frac{p}{p-1} - (n+1)p^n(p-1) $$

$$ = p^{n+1}(p^{n+1} - 1) - (n+1)p^n(p-1) $$

$$ = p^{2n+2} - p^{n+1} - (n+1)p^{n+1} + (n+1)p^n $$

求める個数は、全体から余事象の個数を引いたものであるから、

$$ p^{2n+2} - \left\{ p^{2n+2} - p^{n+1} - (n+1)p^{n+1} + (n+1)p^n \right\} $$

$$ = (n+2)p^{n+1} - (n+1)p^n $$

となる。

解説

整数が特定の素数で何回割り切れるか（最高何乗の倍数か）を基準に分類することは、ルジャンドルの定理などに代表される整数問題の定石である。 (1) のように「ちょうど $m$ 回割り切れる」整数の個数は、「$m$ 回以上割り切れる（$p^m$の倍数）」ものから「$m+1$ 回以上割り切れる（$p^{m+1}$の倍数）」ものを引くことで求められる。

(2) では $x$ と $y$ の対称性を利用したり、直接数え上げたりする方法が考えられる。解法1のように、$x$ が「ちょうど何回割り切れるか」で分類した上で、$y$ の条件を「何回以上割り切れるか（＝何かの倍数）」とまとめてしまうと、(1)を再度使う必要がなくなり、計算が非常に簡明になる。解法2の余事象を用いるアプローチでも等比数列の和を正確に処理すれば同等の結論を得ることができるが、全体像を見通しやすいのは直接数える解法1であろう。