ルジャンドルの公式のソースを表示

{{No footnotes|date=2018-04}}
[[数学]]の[[初等整数論]]における'''ルジャンドルの公式'''（ルジャンドルのこうしき、{{lang-en-short|''Legendre's formula''}}）とは、自然数 {{mvar|n}} の[[階乗]] {{math|''n''!}} を素数 {{mvar|p}} で（整数の範囲で）割り切る最大回数を与える式である。{{math|''n''!}} を[[素因数分解]]したときの {{mvar|p}} の[[冪乗]]の指数とも言い換えられる。[[アドリアン＝マリ・ルジャンドル]]に因んで名付けられた。'''ルジャンドルの定理'''、{{ill2|アルフォンス・ド・ポリニャック|en|Alphonse de Polignac}}に因んで'''ド・ポリニャックの公式'''とも呼ばれる。

== 概要 ==
任意の[[非負整数]] {{mvar|N}} と任意の[[素数]] {{mvar|p}} に対して、 {{mvar|N}} を割り切る最大 {{mvar|p}}-冪の指数（すなわち、{{mvar|n}} の [[p進付値|{{mvar|p}}-進付値]]）を {{math2|''ν{{sub|p}}''(''N'')}} で表す。このとき自然数 {{mvar|n}} に対して
:<math>\nu_p(n!) = \textstyle\sum\limits_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i} \right\rfloor</math>
が成り立つ。ここで <math>\lfloor x \rfloor</math> は[[床関数と天井関数|床関数]]である。右辺の総和は見かけ上無限和となっているが実際には、{{math2|''p{{sup|i}}'' > ''n''}} ならば <math>\left\lfloor \tfrac{n}{p^i} \right\rfloor = 0</math> となるため、{{mvar|i}} は <math>\lfloor \log_p n \rfloor</math> まで取ればよい。

=== 例 ===
{{math2|1=''n'' = 6}} のとき、<math>6! = 720 = 2^4 \cdot 3^2 \cdot 5^1</math> である。それぞれの指数は <math>\nu_2(6!) = 4, \nu_3(6!) = 2, \nu_5(6!) = 1</math> である。これらは以下のようにルジャンドルの公式によって計算できる。
:<math>\begin{align}
\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{align}</math>

=== 証明 ===
{{math2|1=''n''! = 1 × … × ''n''}} であるから、{{mvar|n}} 以下の各自然数の素因数 {{mvar|p}} の指数の総和が求める値である。まず、{{mvar|n}} 以下の {{mvar|p}} の正の倍数は <math>\left\lfloor \tfrac{n}{p} \right\rfloor</math> 個だけある。加えて、{{math|''p''{{sup|2}}}} の倍数があるごとに {{math|''n''!}} に素因数 {{mvar|p}} をさらに1個見い出すことができる。{{math|''p''{{sup|3}}}} 以降も同様である。故に <math>\nu_p(n!)</math> はこれらの総和に等しい。

== 他の形式 ==
{{mvar|p}} を底とする {{mvar|p}}-進展開の観点からルジャンドルの公式を定式化し直すこともできる。<math>s_p(n)</math> を {{mvar|n}} の {{mvar|p}}進表記における[[数字和|各位の和]]とすると以下の式が成り立つ。
:<math>\nu_p(n!) = \frac{n - s_p(n)}{p-1}.</math>
例えば、{{math2|1=''n'' = 6}} を二進法で表記すると {{math2|1=6{{sub|(10)}} = 110{{sub|(2)}}}} であり、<math>s_2 (6) = 1+1+0 = 2</math>である。したがって
:<math>\nu_2(6!) = \frac{6-2}{2-1} = 4</math>
同様に、{{math2|1=''n'' = 6}} を三進法表示は {{math2|1=6{{sub|(10)}} = 20{{sub|(3)}}}} であり、<math>s_3(6) = 2+0 = 2</math>である。したがって
:<math>\nu_3(6!) = \frac{6-2}{3-1} = 2</math>
である。

=== 証明 ===
{{mvar|n}} は {{mvar|p}}進法で <math>n = n_\ell p^\ell + \cdots + n_1 p + n_0</math> と書ける。したがって、<math>\left\lfloor \tfrac{n}{p^i} \right\rfloor = n_\ell p^{\ell-i} + \cdots + n_{i+1} p + n_i</math> であり、
:<math>\begin{align}
\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{align}</math>

== 応用 ==
ルジャンドルの公式を用いて{{仮リンク|クンマーの定理|en|Kummer%27s_theorem}}を証明することができる。特別な場合の一つとして、{{mvar|n}} を正の整数とすると、<math>\tbinom{2n}{n}</math> が {{math|4}} で割り切れるための[[必要十分条件]]は、{{mvar|n}} が [[2の冪|{{math|2}} の冪]]でないことである。 

また、ルジャンドルの公式からは {{ill2|p-進指数函数|label={{mvar|p}}-進指数関数|en|p-adic exponential function}}の[[収束半径]]は <math>p^{-\tfrac{1}{p-1}}</math> であることが導ける。

== 参考文献 ==
*{{Citation |first=Leonard Eugene |last=Dickson |authorlink=レオナード・E・ディクソン |title=History of the Theory of Numbers |volume=Volume 1: Divisibility and Primality |origyear=1830 |year=2005 |publisher=Dover Publications |page=263 |isbn=978-0-486-44232-7}}
*{{Citation |first=A. M. |last=Legendre |title=Théorie des |publisher=Firmin Didot Frères |year=1830 |location=Paris}}
**{{Cite book|和書 |author=AｰM. ルジャンドル |authorlink=アドリアン＝マリ・ルジャンドル |title=数の理論 |translator=[[高瀬正仁]] |publisher=海鳴社 |date=2007-12 |isbn=978-4-87525-245-0 |ref={{Harvid|ルジャンドル|2007}}}}
*{{Citation |first=Victor H. |last=Moll |title=Numbers and Functions |publisher=[[アメリカ数学会|American Mathematical Society]] |year=2012 |isbn=978-0-8218-8795-0 |mr=2963308 |page=77}}

== 外部リンク ==
*{{高校数学の美しい物語|590|ルジャンドルの定理（階乗が持つ素因数のべき数）}}
* {{MathWorld|urlname=Factorial|title=Factorial}}
<!--* {{MathWorld|urlname=Legendre's Formula|title=Legendre's Formula}}-->
* {{PlanetMath|urlname=depolignacsformula|title=de Polignac’s formula}}
* {{ProofWiki|urlname=De_Polignac's_Formula|title=De Polignac's Formula}}

{{DEFAULTSORT:るしやんとるのこうしき}}
[[Category:初等整数論]]
[[Category:アドリアン＝マリ・ルジャンドル]]
[[Category:数学に関する記事]]