ルジャンドルの定理(階乗が持つ素因数のべき数)

ルジャンドルの定理

n!n! に含まれる素因数 pp の数は以下の式で計算できる:

i=1npi=np+np2+np3+{\displaystyle \sum_{i=1}^{\infty}\left\lfloor \dfrac{n}{p^i} \right\rfloor}=\left\lfloor \dfrac{n}{p} \right\rfloor+\left\lfloor \dfrac{n}{p^2} \right\rfloor+\left\lfloor \dfrac{n}{p^3} \right\rfloor+\cdots

ただし,x\lfloor x \rfloorxx を超えない最大の整数を表す。

ルジャンドルの定理は階乗が素因数で何回割れるかを計算できる公式です。

なお,ルジャンドルは整数論の定理をいくつか発見しており,ルジャンドルの定理はいくつかあるようです。この記事では,上記の定理をルジャンドルの定理と呼ぶことにします。

ルジャンドルの定理の使用例

階乗に素因数がいくつ含まれるかという問題は,大学入試で頻出です。ルジャンドルの定理を覚えていれば,以下のように一発で解くことができます。

例題1

30!30! は何回 33 で割り切れるか求めなさい。

証明

30!30! を気合いで計算するのは厳しい。

そこで,ルジャンドルの定理を用いると,

303+309+3027=10+3+1=14\left\lfloor \dfrac{30}{3} \right\rfloor+\left\lfloor \dfrac{30}{9} \right\rfloor+\left\lfloor \dfrac{30}{27} \right\rfloor\\ =10+3+1\\ =14

つまり,14回

→高校数学の問題集 ~最短で得点力を上げるために~のT20の解説も参照してください。

また,階乗を割る数が素数でない場合にも,以下のように応用できます。

例題2

100!100! の末尾の 00 の数を求めなさい。

解答

末尾の 00 の数は,10で何回割り切れるか,すなわち 22 で割れる回数と 55 で割れる回数の少ない方である。
(直感的に考えて 55 で割れる回数のほうが少ないので,55 で割れる回数だけ考えればよいが,練習のため 22 で割れる回数も計算する)

ルジャンドルの定理より,100!100!22 で割れる回数は
1002+1004+1008+10016+10032+10064=50+25+12+6+3+1=97\left\lfloor \dfrac{100}{2} \right\rfloor+\left\lfloor \dfrac{100}{4} \right\rfloor+\left\lfloor \dfrac{100}{8} \right\rfloor+\left\lfloor \dfrac{100}{16} \right\rfloor+\left\lfloor \dfrac{100}{32} \right\rfloor+\left\lfloor \dfrac{100}{64} \right\rfloor\\ =50+25+12+6+3+1\\ =97

100!100!55 で割れる回数は
1005+10025=20+4=24\left\lfloor \dfrac{100}{5} \right\rfloor+\left\lfloor \dfrac{100}{25} \right\rfloor\\ =20+4\\ =24

よって,答えは24個。

ルジャンドルの定理の証明

最後に,ルジャンドルの定理の証明を解説します。

証明

1から nn までの数の中で素因数 pp を1つ以上持っているもの(pp の倍数)は np\left\lfloor \dfrac{n}{p} \right\rfloor 個。

さらに,その中で素因数 pp を2つ以上持っているもの(p2p^2 の倍数)は np2\left\lfloor \dfrac{n}{p^2} \right\rfloor 個。

以下この議論を繰り返して求める公式を得る。

上記の証明が抽象的でわかりにくい人は,以下の図に n=9,p=2n=9, p=2 の場合の様子を示したので参考にしてください。

ルジャンドルの定理の証明

大学入試でも数学オリンピックでも活躍する重要な公式です。