2014/02/25

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

分野: 整数問題  レベル: 最難関大学

ルジャンドルの定理
$n!$ に含まれる素因数 $p$ の数は以下のように表される:
${\displaystyle \sum_{i=1}^{\infty}\Big\lfloor \dfrac{n}{p^i} \Big\rfloor}=\Big\lfloor \dfrac{n}{p} \Big\rfloor+\Big\lfloor \dfrac{n}{p^2} \Big\rfloor+\Big\lfloor \dfrac{n}{p^3} \Big\rfloor+\cdots$
ただし,ここで $\lfloor x \rfloor$ は $x$ を超えない最大の整数を表す。

ルジャンドルは整数論の定理をいくつか発見しており,ルジャンドルの定理はいくつかあるみたいですが,このサイトでは上記の定理をルジャンドルの定理と呼ぶことにします。

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

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

例題1:$30!$は何回 $3$ で割り切れるか求めなさい。

解答

$30!$を気合いで計算するのは厳しいのでルジャンドルの定理を用いると,
$\Big\lfloor \dfrac{30}{3} \Big\rfloor+\Big\lfloor \dfrac{30}{9} \Big\rfloor+\Big\lfloor \dfrac{30}{27} \Big\rfloor=10+3+1=14回$

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

例題2:$100!$の末尾の $0$ の数を求めなさい。

解答

末尾の $0$ の数は,10で何回割り切れるか,すなわち $2$ で割れる回数と $5$ で割れる回数の少ない方である。(直感的に考えて $5$ で割れる回数のほうが少ないので $5$ で割れる回数だけ考えればよいが練習のため,)
ルジャンドルの定理より,$100!$を $2$ で割れる回数は
$\Big\lfloor \dfrac{100}{2} \Big\rfloor+\Big\lfloor \dfrac{100}{4} \Big\rfloor+\Big\lfloor \dfrac{100}{8} \Big\rfloor+\Big\lfloor \dfrac{100}{16} \Big\rfloor+\Big\lfloor \dfrac{100}{32} \Big\rfloor+\Big\lfloor \dfrac{100}{64} \Big\rfloor\\=50+25+12+6+3+1=97回$
$100!$を $5$ で割れる回数は
$\Big\lfloor \dfrac{100}{5} \Big\rfloor+\Big\lfloor \dfrac{100}{25} \Big\rfloor=20+4=24回$
よって,答えは24個。

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

ルジャンドルの定理は上記のように答えを一発で求めることができるのですが,記述式の場合は答えに至るまでの流れを説明しなければいけないので,以下の証明の考え方も覚えておきましょう。

証明

1から $n$ までの数の中で素因数 $p$ を1つ以上持っているもの($p$ の倍数)は $\Big\lfloor \dfrac{n}{p} \Big\rfloor$ 個。
さらに,その中で素因数 $p$ を2つ以上持っているもの($p^2$ の倍数)は $\Big\lfloor \dfrac{n}{p^2} \Big\rfloor$ 個。
以下この議論を繰り返して求める公式を得る。

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

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

 
 
 
 
 
 
 

大学入試でも数学オリンピックでも活躍する重要な公式です。
分野: 整数問題  レベル: 最難関大学