COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

素数

素数

問題≪$p$ 進付値≫

 $p$ を素数とする. $0$ でない整数 $a$ に対して, $a$ の素因数分解における $p$ の指数を $\mathrm{ord}_p(a)$ で表す.
(1)
$0$ でないすべての整数 $a,$ $b$ に対して, \[\mathrm{ord}_p(ab) = \mathrm{ord}_p(a)+\mathrm{ord}_p(b)\] が成り立つことを示せ. また, $a$ が $b$ で割り切れるとき, \[\mathrm{ord}_p\left(\frac{a}{b}\right) = \mathrm{ord}_p(a)-\mathrm{ord}_p(b)\] が成り立つことを示せ.
(2)
$n$ を正の整数として, $m = \mathrm{ord}_p({}_{2n}\mathrm C_n)$ とおく. このとき, $p^m \leqq 2n$ であることを示せ. ただし, 各実数 $x$ に対して $x$ 以下の最大の整数を $[x]$ で表すとき, \[\mathrm{ord}_p(n!) = \sum_{k = 0}^\infty\left[\frac{n}{p^k}\right] \quad \cdots [*]\] が成り立つことは, 証明なしに使ってもよい. ここで, $n < p^k$ なる正の整数 $k$ に対しては $\left[\dfrac{n}{p^k}\right] = 0$ であることに注意する.

解答例

(1)
素因数分解の一意性により
$a = p^{\mathrm{ord}_p(a)}a',$ $b = p^{\mathrm{ord}_p(b)}b'$ ($a',$ $b'$: $p$ と互いに素)
と表せて
$ab = p^{\mathrm{ord}_p(a)+\mathrm{ord}_p(b)}a'b'$ ($a'b'$: $p$ と互いに素)
となるから, \[\mathrm{ord}_p(ab) = \mathrm{ord}_p(a)+\mathrm{ord}_p(b)\] が成り立つ. また, $a$ が $b$ で割り切れるとき, \[\mathrm{ord}_p(a) = \mathrm{ord}_p\left(\frac{a}{b}\cdot b\right) = \mathrm{ord}_p\left(\frac{a}{b}\right) +\mathrm{ord}_p(b)\] から, $\mathrm{ord}_p\left(\dfrac{a}{b}\right) = \mathrm{ord}_p(a)-\mathrm{ord}_p(b)$ が成り立つ.
(2)
(1) の結果と $[*]$ により, \begin{align*} m &= \mathrm{ord}_p\left(\frac{(2n)!}{n!n!}\right) = \mathrm{ord}_p((2n)!)-2\,\mathrm{ord}_p(n!) \\ &= \sum_{k = 0}^\infty\left(\left[\frac{2n}{p^k}\right] -2\left[\frac{n}{p^k}\right]\right) \\ \end{align*} が成り立つ. 非負整数 $k$ に対して $x = \dfrac{n}{p^k}$ とおくと, $[2x] \leqq 2x,$ $x-1 < [x]$ から $[2x]-2[x] < 2$ となるので, $[2x]-2[x]$ の値は $0$ または $1$ のいずれかとなり, $[2x]-2[x] = 0$ のとき $2x < 1$ つまり $p^k > 2n$ となるから, $m$ は $p^k \leqq 2n$ なる整数 $k$ の最大値以下である. ゆえに, $p^m \leqq 2n$ が成り立つ.

背景

  • 正の整数 $a$ の素因数分解における素数 $p$ の指数を $a$ の「$p$ 進付値」($p$-adic valuation)と呼び, $\mathrm{ord}_p(a)$ で表す.
  • $[*]$ は, 初等整数論における「ルジャンドルの公式」(Legendre's formula)と呼ばれ, 次のように示される.
     $\mathrm{ord}_p(n!) = \displaystyle\sum_{l = 1}^n\mathrm{ord}_p(l)$ であるから, $1$ 以上 $n$ 以下の整数を横に並べて書き, 各整数 $l$ の真下に $l$ の素因数分解における $p$ の指数 $\mathrm{ord}_p(l)$ だけ 〇 を書くことにすると, $\mathrm{ord}_p(n!)$ は 〇 の総数に等しい.
     $k$ 段目の 〇 の総数は $1$ 以上 $n$ 以下の $p^k$ の倍数の個数 $\left[\dfrac{n}{p^k}\right]$ であるから, それを $k$ について足しあわせると $\mathrm{ord}_p(n!) = \displaystyle\sum_{k = 0}^\infty\left[\frac{n}{p^k}\right]$ となる.
     例えば, $\mathrm{ord}_2(10!) = 8$ は, 次表の右欄の合計として求まる.
    $1$$2$$3$$4$$5$$6$$7$$8$$9$$10$〇 の個数
    $2$ の倍数$\left[\dfrac{10}{2}\right] = 5$
    $4$ の倍数$\left[\dfrac{10}{4}\right] = 2$
    $8$ の倍数$\left[\dfrac{10}{8}\right] = 1$
  • 本問の結果は, 次の「ベルトラン仮説」(Bertrand's postulate)の証明に使われる: 各正の整数 $n$ に対して, $n < p \leqq 2n$ なる素数 $p$ が少なくとも $1$ つ存在する.

約数の和

 こちらを参照.