このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
*階乗 [#b647198c]

#divid(s,thorem)
[定理]連続する自然数r個の積は必ずr!で割り切れる。
#divid(e,thorem)

#divid(s,proof)
[証明]連続する自然数r個の積は、大きい方から書けば次のようにと書ける。

n(n-1)(n-2)…(n-r+1) ←(*)

ただし、n≧rである。

これをr!で割った結果は、次の通りである。

&mimetex("\frac{n(n-1)(n-2) \cdots (n-r+1)}{r!}"); ←(**)~
&mimetex("=\frac{n!}{r! (n-r)!}");~
&mimetex("= _n C_r");

このSUB{n};CSUB{r};はn個のものからr個取り出す組み合わせなので、整数である。

つまり、(*)のr個の積は当然r!で割り切れる。 □

[別証](組み合わせという意味付けを使わない証明)

任意の素数pが(**)の分子n!に含まれる個数(n)SUB{p};と、分母のr!(n-r)!に含まれる個数(r)SUB{p};+(n-r)SUB{p};である。

これらを比べて、どんなpに対して常に次が成り立つことをいえばよい。

&mimetex("(n)_p \ge (r)_p + (n-r)_p"); ←(***)

そこで、[定理]「n!に含まれる素数pの総個数(n)SUB{p};とすると、次が成り立つ。&mimetex("(n)_p = [ \frac{n}{p} ] + [ \frac{n}{p^2} ] + [ \frac{n}{p^3} ] + \cdots = \Sigma_{k=1}^\Infty [\frac{n}{p^k} ]");」より、次が成り立つ。

-&mimetex("(n)_p = [ \frac{n}{p} ] + [ \frac{n}{p^2} ] + [ \frac{n}{p^3} ] + \cdots");
-&mimetex("(r)_p = [ \frac{r}{p} ] + [ \frac{r}{p^2} ] + [ \frac{r}{p^3} ] + \cdots");
-&mimetex("(r')_p = [ \frac{r'}{p} ] + [ \frac{r'}{p^2} ] + [ \frac{r'}{p^3} ] + \cdots");

ただし、r'=n-r、即ちn=r+r'

ここで、[定理]「&mimetex("[ \frac{a+b}{k} ] \ge \frac{a}{k} + \frac{b}{k}");」より、(***)が成り立つ。 □
#divid(e,proof)

*参考文献 [#o5b023dc]

-『数学ワンポイント双書10 整数』