■ヨーロッパの「剰余問題」 (その138)
【1】ep(n!)の上限
  ep(n!)<n/p+n/p^2++n/p^3+・・・
=n/p(1+1/p+1/p^2+・・・)
=n/(p−1)
 p=2,n=100の場合は,97<100となり,真の値97にかなり近い.
  e2(100!)=[100/2]+[100/2^2]+[100/2^3]+[100/2^4]+[100/2^5]+[100/2^6]=97
 p=5,n=1000の場合は,249<250となり,真の値249にかなり近い.
  e5(1000!)=[1000/5]+[1000/5^2]+[1000/5^3]+[1000/5^4]=200+40+8+1=249
===================================
[Q]1000!/10^250は整数であるか?
[A]  [1000/5]+[1000/5^2]+[1000/5^3]+[1000/5^4]=200+40+8+1=249
 10の倍数は249個.したがって,1000!/10^249は整数であるか,1000!/10^250は整数とはならない.
===================================
 それでは
[Q]1000!=?  (mod10^250)
[A]  e2(100!)=[100/2]+[100/2^2]+[100/2^3]+[100/2^4]+[100/2^5]+[100/2^6]=97
  e2(1000!)>500
  e5(1000!)>249
 したがって,ある偶数aがあって,
  1000!=a・10^249
また,1000=(13000)5より
  a・2^249=1000!/5^249=−1 (mod5)
  2^249=2 (mod5)
  a=2 (mod10)→a=2または7 (mod10)
  aは偶数であるから,a=2.
[A]1000!=2・10^249  (mod10^250)
===================================
 
