르장드르 공식

르장드르 공식

$n!$은 소인수 $p$를 정확히 $$\displaystyle\sum_{k\ge 1} \lfloor\dfrac{n}{p^k}\rfloor$$번 포함한다. (여기서 $\lfloor n \rfloor$은 $n$를 넘지 않는 최대 정수를 의미한다.)

 

증명

$$n!=1\cdot 2\cdot 3\cdot \cdots n$$의 곱을 나타내는 인수들 중에 정확히 $\lfloor \frac{n}{p}\rfloor$개의 인수가 $p$로 나누어지며, 이들이 곧 $p$의 배수이다. 다음, $n!$의 인수들 중 $p^2$으로 나누어지는 인수의 개수는$\lfloor \frac{n}{p^2}\rfloor$이다. 이는 $n!$이 소인수 $p$를 $\lfloor \frac{n}{p^2}\rfloor$개 더 포함함을 의미한다. 같은 과정을 반복하면 증명이 완료된다.   $\blacksquare$

 

Exponential 17 김지하