【数学】n!がpで割れる回数を求める方法とは？ルジャンドルの定理を徹底解説！【初心者向け】
n!がpで割れる回数を求める方法とは？ルジャンドルの定理を徹底解説！
この記事では、「n!がpで割れる回数を求める方法」として知られるルジャンドルの定理を初心者向けにも、上級者向けにも理解できるように解説します。数式や例を交えながら、順を追って説明しますので、数学に自信がない方でも安心して読んでいただけます。
目次
1. ルジャンドルの定理とは？
まずは、ルジャンドルの定理が何を表しているのかを簡単に説明します。ルジャンドルの定理は、任意の自然数n!（nの階乗）を素数pで割ったとき、pがn!に何回割り切れるかを求める方法です。定理の概要は以下の通りです：
「n!を素数pで割った商が何回整数になるかを求めるための公式。」
具体的には、次のように定義されます。n!の中に含まれるpの因子の個数は、以下の式で求めることができます：
$$ \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots $$
2. ルジャンドルの定理の証明
次に、ルジャンドルの定理の証明を行います。n!には、1からnまでのすべての自然数が掛け合わされており、その中でpが含まれる数が何回あるかを考えます。
まず、n!に含まれるpの因子は、pで割り切れる自然数の個数です。例えば、nが20で、pが5の場合、5, 10, 15, 20の4つの数がpで割り切れます。しかし、これだけでは不十分です。
次に、p^2、p^3、…というように、さらに高いべきのpで割り切れる数も考慮する必要があります。たとえば、p=5の場合、25のように、p^2で割り切れる数も含まれます。
これを一般化すると、n!の中に含まれるpの因子の数は、以下の式で求められることがわかります：
$$ \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots $$
3. 具体例で学ぼう！n!がpで割れる回数を求める
実際に具体例を使って、n!がpで割れる回数を求めてみましょう。
例1: n = 100, p = 5の場合
この場合、100!に含まれる5の因子の個数を求めるために、以下の式を使用します：
$$ \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{5^2} \right\rfloor = \left\lfloor 20 \right\rfloor + \left\lfloor 4 \right\rfloor = 20 + 4 = 24 $$
例2: n = 50, p = 3の場合
次に、n = 50, p = 3の場合を考えます。以下の式を使って求めます：
$$ \left\lfloor \frac{50}{3} \right\rfloor + \left\lfloor \frac{50}{3^2} \right\rfloor = \left\lfloor 16.67 \right\rfloor + \left\lfloor 5.56 \right\rfloor = 16 + 5 = 21 $$
よって、50!は21回3で割り切れるということがわかります。4. 上級者向け：定理の応用と発展
ルジャンドルの定理には、いくつかの応用があります。たとえば、大きな階乗の素因数分解や、素数判定、または数論的な問題において重要な役割を果たします。
また、pが複数の素数の場合、個別にこの定理を適用して、各素数ごとにn!がその素数で割れる回数を求め、最終的な分解に役立てることができます。
5. まとめ
今回は、ルジャンドルの定理を使って、n!がpで割れる回数を求める方法を詳しく解説しました。初心者の方でも理解できるように、定理の基本的な考え方から始まり、具体例を用いて計算の方法を紹介しました。上級者の方には、定理の応用方法や発展的な考え方も触れました。
この定理は数論や計算数学で非常に有用ですので、ぜひしっかりと理解して、さまざまな問題に応用してみてください。
