| 詳しい説明は、そのページの前段に書かれていますので、そちらに譲るとして、
自然数 Ｎ の階乗（ Ｎ！）の中に、素数 Ｐ は次の個数含まれる。
（ただし、Ｎ の Ｐ 進法展開を、ｓｔｕ・・・ とする。）
を数学的帰納法で示してみます。
Ｐ＝２ の場合
Ｎを２進法展開したときの、各位の数の合計をｆ(Ｎ)とすると、
Ｎ！に含まれる素因数２の個数は
Ｎ−f(Ｎ)
と表される、というのが示すべき命題です。
Ｎ＝１ のとき、ｆ（Ｎ）＝１ であり、含まれる２の個数は
１−ｆ(１)＝０ (個)
で、標記の命題は成り立ちます。
ある自然数ｋについて、ｋ！に含まれる２の個数が
ｋ−ｆ(ｋ) （個）
であり、これに ｋ＋１ を掛けて (ｋ＋１)！を作る時、
「(ｋ＋１)！に含まれる２の個数が
ｋ＋１−ｆ（ｋ＋１）
であること」 ・・・（Ａ）
を示します。
ｋに１を足してｋ＋１にするときの、２進法での変化を考えると、
１．繰り上がりがない時
１１００１０＋１＝１１００１１
のような場合で、ｋ＋１ が奇数の場合です。
このとき、ｆ（ｋ＋１）＝ｆ（ｋ）＋１ であるので、
ｋ＋１−ｆ（ｋ＋１）＝ｋ−ｆ（ｋ） ・・・２の数はｋのときと変わらない（ｋ＋１が奇数のため)
よって、（Ａ）は正しいです。
２．２^n の位まで繰り上がる時
１０１１１＋１＝１１０００ 2^3の位まで繰り上がった場合
ｋ＋１ は 2^n の倍数で、2^(n+1) の倍数ではないので、含まれる２の数はｎ個増えます。
一方、f(k+1)＝f(k)−ｎ＋１ （1の位から 2^(n-1) の位までが０になり、2^n の位が１となる）
より、
ｋ＋１−ｆ（ｋ＋１）＝ｋ−ｆ（ｋ）＋ｎ
よって、（Ａ）は正しいです。
以上より、すべての自然数Ｎについて、首記の命題は成り立つことが証明されます。
一般の素数Ｐのときもほぼ同じで、
ＮをＰ進法展開したときの、各位の数の合計をｆ(Ｎ)とすると、
Ｎ！に含まれる素因数Ｐの個数は
{Ｎ−f(Ｎ)}／(P-1)
と表される、というのが示すべき命題です。
Ｎ＝１ のとき、ｆ（Ｎ）＝１ であり、含まれる２の個数は
{１−ｆ(１)}／(P-1)＝０ (個)
で、標記の命題は成り立ちます。
ある自然数ｋについて、ｋ！に含まれるＰの個数が
{ｋ−ｆ(ｋ)}／(P-1) （個）
であり、これに ｋ＋１ を掛けて (ｋ＋１)！を作る時、
「(ｋ＋１)！に含まれるＰの個数が
{ｋ＋１−ｆ（ｋ＋１）}／(P-1)
であること」 ・・・（Ａ）
を示します。
ｋに１を足してｋ＋１にするときの、Ｐ進法での変化を考えると、
１．繰り上がりがない時
４３４２１０＋１＝４３４２１１ （５進法の例）
のような場合で、ｋ＋１ がＰで割り切れない数の場合です。
このとき、ｆ（ｋ＋１）＝ｆ（ｋ）＋１ であるので、
{ｋ＋１−ｆ（ｋ＋１）}／(P-1)＝{ｋ＋ｆ（ｋ）}／(P-1) ・・・Ｐの数はｋのときと変わらない
よって、（Ａ）は正しいです。
２．Ｐ^n の位まで繰り上がる時
３０４４４＋１＝３１０００ ５進法で、５^3の位まで繰り上がった場合
ｋ＋１ は Ｐ^n の倍数で、Ｐ^(n+1) の倍数ではないので、含まれるＰの数はｎ個増えます。
一方、f(k+1)＝f(k)−(P-1)ｎ＋１ （1の位から Ｐ^(n-1) の位までが０になり、Ｐ^n の位が１となる）
より、
{ｋ＋１−ｆ（ｋ＋１）}／(P-1)＝{ｋ＋ｆ（ｋ）}／(P-1)＋ｎ
よって、（Ａ）は正しいです。
以上より、すべての自然数Ｎについて、首記の命題は成り立つことが証明されます。
Ｐ＝２ の場合は、イメージを掴むために載せたもので、一般のＰだけでも十分です。
|
No.43332 - 2017/05/25(Thu) 18:20:57 |
