有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

素数

素数

定理《整数論の基本定理》

 $0$ でも $\pm 1$ でもないすべての整数 $a$ は, $\pm 1$ と素数 $p_1,$ $\cdots,$ $p_r$ $(p_1 < \cdots < p_r)$ の積に
$a = \pm p_1{}^{m_1}\cdots p_r{}^{m_r}$ ($m_1,$ $\cdots,$ $m_r$: 正の整数)
とただ $1$ 通りに表すことができる.

証明

 分解の存在: $0$ でも $\pm 1$ でもない整数 $a$ は, 合成数であれば, 絶対値のより小さい整数 $b,$ $c$ の積 $a = bc$ に分解される. $b,$ $c$ は, 合成数であれば, 絶対値より小さい整数の積に分解される. この操作を繰り返せば, $a$ は高々 $|a|$ 個の整数 $a_1,$ $\cdots,$ $a_l$ の積に分解され, どれも絶対値のより小さい整数の積に分解できなくなる. このとき $a_1,$ $\cdots,$ $a_l$ は素数であるから, $a$ は素数の積 \[ a = a_1\cdots a_l \quad \cdots [1]\] に分解することができる.
 分解の一意性: $a$ が素数 $b_1,$ $\cdots,$ $b_m$ の積 \[ a = b_1\cdots b_m\] としても表されたとする. $l,$ $m > 1$ のとき, \[ a_1\cdots a_l = b_1\cdots b_m\] が成り立ち, 右辺は素数 $a_l$ で割り切れるから, 補題によりある $b_k$ $(1 \leqq k \leqq m)$ は $a_l$ で割り切れる. よって, 必要に応じて番号をつけ替えると, $a_l = c_lb_m$ ($c_l$: 整数)となる. このとき, \[ a_1\cdots a_{l-1} = c_lb_1\cdots b_{m-1}\] となるから, 必要に応じて番号をつけ替えながら同様の操作を続けると,
$l = m,$ $a_k = c_kb_k$ ($c_k$: 整数)
となる. ここで, $l = m$ となるのは, 素数の積が $\pm 1$ となることはないからである. ゆえに, 表示 $[1]$ は, 順序の違いを除いてただ $1$ 通りである.

補題《素数は素元》

 $p$ を素数とする. このとき, すべての整数 $a,$ $b$ に対して, $ab$ が $p$ の倍数ならば, $a$ または $b$ は $p$ の倍数である.

証明

 $ab$ が $p$ の倍数であり, $a$ が $p$ の倍数でないとすると, $a,$ $p$ は互いに素であるから, $ax+py = 1$ は整数解 $x,$ $y$ をもつ. よって, $b = abx+bpy$ は $p$ の倍数である.

問題《$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{aligned} 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) \quad \cdots [1] \end{aligned}\] が成り立つ. $x = \dfrac{n}{p^k}\,(> 0)$ について, $2x-1 < [2x] \leqq 2x,$ $2x-2 < 2[x] \leqq 2x$ であるから, \[ [2x]-2[x] = 0,\ 1\] である. ここで, $[2x]-2[x] = 1$ のとき, $0 \leqq 2[x] \leqq 2x-1$ とならざるを得ず, $1 \leqq 2x$ つまり $p^k \leqq 2n$ が成り立つ. よって, $p^k \leqq 2n$ なる非負整数 $k$ の最大値を $M$ とおくと, $[1]$ から
$m \leqq (p^k \leqq 2n$ なる非負整数 $k$ の個数$)\times 1 = M$
となり, $p^m \leqq p^M \leqq 2n$ したがって $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–Chebyshev theorem)の証明に使われる: 各正の整数 $n$ に対して, $n < p \leqq 2n$ なる素数 $p$ が少なくとも $1$ つ存在する.

問題《カーマイケル数の性質》

 $n$ を $1$ より大きい整数とする. すべての整数 $a$ に対して $a^n-a$ が $n$ の倍数であり, $n$ が素数でないとき, $n$ を「カーマイケル数」と呼ぶ. 次のことを示せ.
(1)
「カーマイケル数」は奇数である.
(2)
「カーマイケル数」は相異なる素数の積である.
ヒント: (1) では $a = n-1$ の場合を, (2) では $n$ の素因数分解における素数 $p$ の指数を $m$ として $a = p^{m-1}$ の場合を考える. (1) では二項定理(数学 II)を使う.

解答例

(1)
すべての整数 $a$ に対して $a^n-a$ が $n$ の倍数であるとする. このとき, $(n-1)^n-(n-1)$ は $n$ の倍数であるから, $(-1)^n+1$ は $n$ の倍数である(二項定理を使った). $n$ が偶数であるとき, $n$ は $(-1)^n+1 = 2$ の約数となるから, $n = 2$ となる. $2$ は素数であるから,「カーマイケル数」は奇数である.
(2)
「カーマイケル数」$n$ の素因数分解における素数 $p$ の指数を $m$ とおく. $p^{(m-1)n}-p^{m-1}$ は $n$ で割り切れ, $n$ は $p^m$ で割り切れるから, \[\frac{p^{(m-1)n}-p^{m-1}}{p^m} = \frac{p^{(m-1)(n-1)}-1}{p}\] は整数である. これが成り立つのは $m = 1$ の場合に限るから,「カーマイケル数」は相異なる素数の積である.

背景

  • $1$ より大きい整数 $n$ について,「フェルマーの小定理」
     $n$ が素数 $\Longrightarrow$
     $0 \leqq a < n$ なる各整数 $a$ に対して $a^n \equiv a \pmod n$
    (こちらを参照)の対偶をとると,
     $0 \leqq a < n$ なるある整数 $a$ に対して $a^n \not\equiv a \pmod n$
     $\Longrightarrow$ $n$ は合成数
    となる. これを利用して, 素数の候補を見つける方法は「フェルマー・テスト」(Fermat test)として知られている. 「カーマイケル数」とは「フェルマー・テスト」を通過してしまう合成数である.
  • $n$ を正の整数とするとき, 次は同値であることが知られている(「コルセルトの判定法」, 証明はこちらを参照).
    (i)
    $n$ は「カーマイケル数」である.
    (ii)
    $n$ は相異なる奇素数の積に分解され, $n$ の各素因数 $p$ に対して $p-1$ は $n-1$ を割り切る.
  • 最小の「カーマイケル数」は $561$ である.

約数の和

 こちらを参照.