整数の問題(自作問題1-(11))

問題.

自作問題集の1-(11), 整数の問題です.

問題.

$M$ を非負整数, $n$ を自然数とする. $\displaystyle\frac{(2^{M+1}n)!}{n!}$ は2で何回割り切れるか.

2で割り切れる回数を直接数え上げることはできないので, いくつかの整数の積として表し数えていきます.

解答例.

$N$ を自然数として, $\displaystyle \frac{(2N)!}{N!}$ が2で何回割り切れるかを調べると,
$\begin{align*} \frac{(2N)!}{N!} &= \frac{(2N)\cdot(2N-1)\cdots2\cdot 1}{N\cdot(N-1)\cdots 2\cdot 1}\\ &= (2N-1)(2N-3)\cdots1\cdot\frac{2N}{N}\cdot\frac{2N-2}{N-1}\cdots\frac{4}{2}\cdot\frac{2}{1}\\ &= (2N-1)(2N-3)\cdots1\cdot2^N \end{align*}$
$(2N-1)(2N-3)\cdots1$ は奇数なので, $\displaystyle \frac{(2N)!}{N!}$ は2で $N$ 回割り切れる.
今, 与えられた式は
$\begin{align} \frac{(2 ^ {M+1}n)!}{n!} = \frac{(2 ^ {M+1}n)!}{(2 ^ Mn)!}\cdot\frac{(2 ^ Mn)!}{(2 ^ {M-1}n)!}\cdots \frac{(2n)!}{n!} \end{align}$
と変形でき, 右辺の各項 $\displaystyle \frac{(2^{k+1}n)!}{(2^kn)!}$ は2で $2^kn$ 回割り切れる整数なので, (1)の右辺は2で
$\begin{align*} 2 ^ Mn+2 ^ {M-1}n+\cdots+2n+n = (2 ^ {M+1}-1)n \end{align*}$
回割り切れる.
従って, $\displaystyle \frac{(2 ^ {M+1}n)!}{n!}$ は2で $(2 ^ {M+1}-1)n$ 回割り切れる.

数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

整数の問題(自作問題1-(11))

問題.

解答例.