階乗を含む整数の素因数分解では、巨大な数を直接計算せずに素数ごとの指数を調べることで性質を判断できます。今回は「1000以下のすべての素数が、1000!/(500!・333!・142!・23!)の素因数である」という命題について、階乗の素因数を調べる方法を使って検証します。
命題の内容と考え方
対象となる数は、次の整数です。
N＝1000!/(500!・333!・142!・23!)
この数の素因数とは、Nを割り切る素数のことです。命題では「1000以下のすべての素数がNの素因数である」と主張しています。
つまり、2、3、5、7、11、13……997までのすべての素数pについて、Nの素因数分解にpが1回以上含まれるかを確認すればよいことになります。
階乗に含まれる素数の個数を調べる方法
階乗の中にある素数pの個数は、ルジャンドルの公式によって求められます。
n!に含まれる素数pの指数は、
⌊n/p⌋＋⌊n/p²⌋＋⌊n/p³⌋＋……
で計算できます。
例えば、1000!に含まれる5の個数は、
⌊1000/5⌋＋⌊1000/25⌋＋⌊1000/125⌋＋⌊1000/625⌋＝200＋40＋8＋1＝249
となります。
分母にある階乗についても同様に計算し、指数の差を求めることでNにその素数が残っているか判断できます。
一般の素数pについて指数を考える
素数pに対するNの指数をe(p)とすると、
e(p)=v_p(1000!)-v_p(500!)-v_p(333!)-v_p(142!)-v_p(23!)
となります。
ここでv_p(n!)はn!に含まれるpの個数を表します。
もしe(p)が1以上なら、その素数pはNの素因数です。逆にe(p)=0なら、その素数は完全に分母側で打ち消されてしまいます。
大きな素数についての確認
まず、501以上1000以下の素数を考えます。このような素数pについて、1000!の中に現れる回数は、1000/pが1以上2未満なので1回だけです。
一方、分母側の500!、333!、142!、23!にはpが含まれません。したがって、501以上1000以下のすべての素数は確実にNの素因数になります。
問題は500以下の素数です。これらは分母の階乗にも含まれるため、単純には判断できません。
小さい素数では打ち消しが起こる可能性がある
例えば2について指数を計算すると、
v_2(1000!)=500＋250＋125＋62＋31＋15＋7＋3＋1＝994
分母側は、
v_2(500!)=498、v_2(333!)=331、v_2(142!)=140、v_2(23!)=19
となります。
したがって、
e(2)=994−498−331−140−19＝6
となり、2は素因数として残ります。
同じような計算をすべての素数について行う必要があります。
命題の真偽を判断するための洞察
この問題の構造は、実は多項係数に近い形をしています。分母の500、333、142、23という数字を見ると、
500＋333＋142＋23＝998
となり、1000との差は2です。
つまり、Nは通常の二項係数や多項係数に似た巨大な整数であり、素数の分布を広く含む性質があります。
特に1000以下の大きな素数は分母の階乗では消えないため、含まれることが直感的にも分かります。一方で、小さい素数については指数計算による確認が必要です。
参考となる一般化された考え方
参考に挙げられている、
n!/([n/2]!・[n/3]!・[n/7]!・[n/42]!)
のような形も、階乗比によって作られる整数です。このような式では、分母に含まれる階乗が大きくても、分子の階乗との差によって多くの素数が残ります。
ただし、「すべての素数が必ず残る」という主張は自明ではありません。特定の素数では分母による完全な打ち消しが起こる可能性があるため、ルジャンドルの公式などで確認する必要があります。
まとめ｜階乗比の素因数は指数比較で判断できる
1000!/(500!・333!・142!・23!)の素因数を調べるには、巨大な数を実際に展開するのではなく、各素数pについて階乗中の指数を比較します。
ルジャンドルの公式を使えば、任意の素数が分母で打ち消されずに残るかどうかを正確に判断できます。
この問題の重要なポイントは、階乗比の素因数問題では「どれだけその素数が階乗に含まれているか」を数えることです。巨大な整数でも、素因数の指数という視点に変えることで、構造を理解しながら検証できます。
コメント