読む編集履歴表示

ルジャンドルの公式

ウィキペディアから、無料の百科事典

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。脚注を導入して、記事の信頼性向上にご協力ください。（2018年4月）

数学の初等整数論におけるルジャンドルの公式（ルジャンドルのこうしき、英: Legendre's formula）とは、自然数 $n$ の階乗 $n!$ を素数 $p$ で（整数の範囲で）割り切る最大回数を与える式である。 $n!$ を素因数分解したときの $p$ の冪乗の指数とも言い換えられる。アドリアン＝マリ・ルジャンドルに因んで名付けられた。ルジャンドルの定理、アルフォンス・ド・ポリニャック（英語版）に因んでド・ポリニャックの公式とも呼ばれる。

概要

任意の非負整数 $N$ と任意の素数 $p$ に対して、 $N$ を割り切る最大 $p$ -冪の指数（すなわち、 $n$ の $p$ -進付値）を $ν p (N)$ で表す。このとき自然数 $n$ に対して

\nu _{p}(n!)=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {n}{p^{i}}}\right\rfloor

が成り立つ。ここで $\lfloor x\rfloor$ は床関数である。右辺の総和は見かけ上無限和となっているが実際には、 $p i > n$ ならば $\left\lfloor {\tfrac {n}{p^{i}}}\right\rfloor =0$ となるため、 $i$ は $\lfloor \log _{p}n\rfloor$ まで取ればよい。

例

$n = 6$ のとき、 $6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}$ である。それぞれの指数は $\nu _{2}(6!)=4,\nu _{3}(6!)=2,\nu _{5}(6!)=1$ である。これらは以下のようにルジャンドルの公式によって計算できる。

{\begin{aligned}\nu _{2}(6!)&=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {6}{2^{i}}}\right\rfloor =\left\lfloor {\dfrac {6}{2}}\right\rfloor +\left\lfloor {\dfrac {6}{4}}\right\rfloor =3+1\\[3pt]\nu _{3}(6!)&=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {6}{3^{i}}}\right\rfloor =\left\lfloor {\dfrac {6}{3}}\right\rfloor =2\\[3pt]\nu _{5}(6!)&=\textstyle \sum \limits _{i=1}^{\infty }\left\lfloor {\dfrac {6}{5^{i}}}\right\rfloor =\left\lfloor {\dfrac {6}{5}}\right\rfloor =1\end{aligned}}

証明

$n! = 1 \times \dots \times n$ であるから、 $n$ 以下の各自然数の素因数 $p$ の指数の総和が求める値である。まず、 $n$ 以下の $p$ の正の倍数は $\left\lfloor {\tfrac {n}{p}}\right\rfloor$ 個だけある。加えて、 $p 2$ の倍数があるごとに $n!$ に素因数 $p$ をさらに1個見い出すことができる。 $p 3$ 以降も同様である。故に $\nu _{p}(n!)$ はこれらの総和に等しい。

他の形式

$p$ を底とする $p$ -進展開の観点からルジャンドルの公式を定式化し直すこともできる。 $s_{p}(n)$ を $n$ の $p$ 進表記における各位の和とすると以下の式が成り立つ。

\nu _{p}(n!)={\frac {n-s_{p}(n)}{p-1}}.

例えば、 $n = 6$ を二進法で表記すると $6 (10) = 110 (2)$ であり、 $s_{2}(6)=1+1+0=2$ である。したがって

\nu _{2}(6!)={\frac {6-2}{2-1}}=4

同様に、 $n = 6$ を三進法表示は $6 (10) = 20 (3)$ であり、 $s_{3}(6)=2+0=2$ である。したがって

\nu _{3}(6!)={\frac {6-2}{3-1}}=2

である。

証明

$n$ は $p$ 進法で $n=n_{\ell }p^{\ell }+\cdots +n_{1}p+n_{0}$ と書ける。したがって、 $\left\lfloor {\tfrac {n}{p^{i}}}\right\rfloor =n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}$ であり、

{\begin{aligned}\nu _{p}(n!)&=\textstyle \sum \limits _{i=1}^{\ell }\left\lfloor {\dfrac {n}{p^{i}}}\right\rfloor \\&=\textstyle \sum \limits _{i=1}^{\ell }(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i})\\&=\textstyle \sum \limits _{i=1}^{\ell }\sum \limits _{j=i}^{\ell }n_{j}p^{j-i}\\&=\textstyle \sum \limits _{j=1}^{\ell }\sum \limits _{i=1}^{j}n_{j}p^{j-i}\\&=\textstyle \sum \limits _{j=1}^{\ell }n_{j}\cdot {\dfrac {p^{j}-1}{p-1}}\\&=\textstyle \sum \limits _{j=0}^{\ell }n_{j}\cdot {\dfrac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\textstyle \sum \limits _{j=0}^{\ell }\left(n_{j}p^{j}-n_{j}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right)\end{aligned}}

応用

ルジャンドルの公式を用いてクンマーの定理（英語版）を証明することができる。特別な場合の一つとして、 $n$ を正の整数とすると、 ${\tbinom {2n}{n}}$ が $4$ で割り切れるための必要十分条件は、 $n$ が $2$ の冪でないことである。

また、ルジャンドルの公式からは $p$ -進指数関数（英語版）の収束半径は $p^{-{\tfrac {1}{p-1}}}$ であることが導ける。

参考文献

Dickson, Leonard Eugene (2005) [1830], History of the Theory of Numbers, Volume 1: Divisibility and Primality, Dover Publications, p. 263, ISBN 978-0-486-44232-7
Legendre, A. M. (1830), Théorie des, Paris: Firmin Didot Frères
- AｰM. ルジャンドル著、高瀬正仁訳『数の理論』海鳴社、2007年12月。ISBN 978-4-87525-245-0。
Moll, Victor H. (2012), Numbers and Functions, American Mathematical Society, p. 77, ISBN 978-0-8218-8795-0, MR2963308

外部リンク

『ルジャンドルの定理（階乗が持つ素因数のべき数）』 - 高校数学の美しい物語
Weisstein, Eric W. "Factorial". mathworld.wolfram.com (英語).
de Polignac’s formula - PlanetMath.（英語）
De Polignac's Formula at ProofWiki