| For All Solvers
OMC237

OMC237(D)

 f(a,b)=abaf(a,b) = a^b - a とおき,以下の補題を示す.


補題1. pp を素数であって, n1n-1p1p-1 で割り切れるようなものとすると,g(n)g(n)pp でちょうど 11 回割り切れる.

証明. kkpp で割り切れるとき, knkk^n-kpp の倍数.kkpp で割り切れないとき,フェルマーの小定理から,knk(modp)k^n \equiv k \pmod{p} となるので,この場合も knkk^n-kpp の倍数.pnp\leq n より,f(p,n)=pnpf(p,n)=p^n-pg(n)g(n) で割り切れる.pnpp^n-ppp で丁度一回割り切れるため,補題が示される.


補題2. pp を素数であって, n1n-1p1p-1 で割り切れないものとすると,g(n)g(n)pp で割り切れない.

証明. 以下の場合分けによって示される.

  • pn!p \leq n! のとき
    modp\mod{p} での原始根を一つとり, rr とする.rn!r \leq n! となるように取ることができ,条件より n1n-1p1p-1 で割った余りを tt とすると,tt00 でないため,rt≢1(modp)r^t \not\equiv 1 \pmod{p} であり,フェルマーの小定理と合わせて,rnrt+1(modp)r^{n} \equiv r^{t+1} \pmod{p} となるため,f(r,n)f(r,n)pp で割り切れない.したがって,g(n)g(n)pp で割り切れない.
  • p>n!p \gt n! のとき
     f(2,n)=2n2n!<pf(2,n)=2^n-2 \leq n! \lt p となるため,f(2,n)f(2,n)pp で割り切れず,したがって g(n)g(n)pp で割り切れない.

 補題1と補題2により,以下を得る. g(n)=p1n1p:primep (1) g(n)=\prod_{\substack{p-1|n-1 \\ p:prime }} p \cdots (1)


補題3. 任意の素数 pp に対して,Mp=1071p1M_p = \bigg\lfloor \dfrac{10^7-1}{p-1} \bigg\rfloor である.

証明 g(2),,g(107)g(2),\ldots,g(10^7) の中で pp で割り切れるものの数は,(1)式より,1,,10711,\ldots,10^7-1 の中にある p1p-1 の倍数の個数と一致する.これは 1071p1\bigg\lfloor \dfrac{10^7-1}{p-1} \bigg \rfloor と計算できる.


 補題3により,以下を得る. p+Mp=1+p1+1071p1=1+(p1)+1071p1r1r+210716324.555 \begin{aligned} p+M_p &= 1+ p-1 + \bigg\lfloor \dfrac{10^7-1}{p-1} \bigg\rfloor\\ &= 1+(p-1)+\dfrac{10^7-1}{p-1} -r \\ & \geq 1-r + 2\sqrt{10^7-1} \\ & \geq 6324.555 \end{aligned} 途中の rr1071p1\dfrac{10^7-1}{p-1} の小数部分で,途中の不等式は相加相乗の不等式を用いた.p+Mpp+M_p が整数であることより,63256325 以上であるとわかる.ここで,1071\sqrt{10^7-1} に近い素数である 31633163 を代入すると,3163+M3163=63253163+M_{3163}=6325 となり,下からの評価を実現する値となっている.したがって解答すべき値は 6325\mathbf{6325}

解説YouTube

解説YouTubeが存在しません.