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

この記事の所要時間: 214

問題.

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

問題. 

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

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

解答例.

Nを自然数として, \displaystyle \frac{(2N)!}{N!}が2で何回割り切れるかを調べると,

\begin{eqnarray*} \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{eqnarray*}


(2N-1)(2N-3)\cdots1は奇数なので, \displaystyle \frac{(2N)!}{N!}は2でN回割り切れる.
今, 与えられた式は

(1) \begin{equation*} \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{equation*}


と変形でき, 右辺の各項\displaystyle \frac{(2^{k+1}n)!}{(2^kn)!}は2で2^kn回割り切れる整数なので, (1)の右辺は2で

\begin{equation*} 2^Mn+2^{M-1}n+\cdots+2n+n = (2^{M+1}-1)n \end{equation*}


回割り切れる.
従って, \displaystyle \frac{(2^{M+1}n)!}{n!}は2で(2^{M+1}-1)n回割り切れる.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加