インテジャーズ

インテジャーズ

数、特に整数に関する記事。

ルジャンドルの公式についての補足

pは素数。

Legendreの公式 \ \ \ \ \ \ \displaystyle \mathrm{ord}_p(n!) = \sum_{m=1}^{\infty}\left[ \frac{n}{p^m} \right] = \sum_{m=1}^{[ \log_pn]}\left[ \frac{n}{p^m} \right] .

mathtrain.jp

integers.hatenablog.com

正整数np進展開を

n=n_0+n_1p+\cdots +n_lp^l,\quad 0 \leq n_i \leq p-1

と書くことにすると*1、Legendreの公式は

\displaystyle \mathrm{ord}_p(n!) = \frac{n-(n_0+n_1+\cdots +n_l)}{p-1}

と書き換えることができます。

理由: 次のように計算できる:

\begin{align}\mathrm{ord}_p(n!) &= \sum_{m=1}^l\left[\frac{n}{p^m}\right] = \sum_{m=1}^l\sum_{i=m}^ln_ip^{i-m} = \sum_{i=1}^ln_i\sum_{m=1}^ip^{i-m}\\
&=\sum_{i=1}^ln_i\frac{p^i-1}{p-1} = \frac{1}{p-1}\sum_{i=0}^ln_i(p^i-1)=\frac{1}{p-1}\Biggl(n-\sum_{i=0}^ln_i\Biggr).\end{align}

この形まで変形してしまえば、次の京大の入試問題はいよいよ瞬殺です。

京大文系2009
pを素数、nを自然数とするとき、(p^n)!pで何回割れるか?

解答. p^np進展開は1\times p^nなので、

\displaystyle \mathrm{ord}_p(p^n!) = \frac{p^n-1}{p-1}

である。

*1:lは当然npから決まる(l=[ \log_pn])。