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

Well-Known Problems and Theorems in Mathematics

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

素数

素数

定義《素数》

(1)
$1$ より大きい正の整数 $p$ が $1$ と $p$ 以外に正の約数をもたないとき, $p$ を素数(prime number)と呼ぶ.
(2)
$1$ でも素数でもない正の整数 $a$ を合成数(composite number)と呼ぶ. これは, $a = bc$ $(1 < b < a,$ $1 < c < a)$ と分解できるような整数 $a$ に他ならない.

定理《素因数分解の可能性》

 $0$ でも $\pm 1$ でもないすべての整数 $a$ は, 素数の積に分解できる.

証明

 $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\] に分解できる.

定義《素因数》

 整数の約数を因数(factor)とも呼ぶ. 素数である因数を素因数(prime factor)と呼び, 整数を素因数の積の形に表すことを素因数分解(prime factorization)という.

定理《素数の無限性》

 素数は無限に存在する.

証明 1(ユークリッド, 紀元前 $3$ 世紀頃)

 $p_1,$ $\cdots,$ $p_r$ を素数とする. このとき, \[ p = p_1\cdots p_r+1\ (> 1)\] は素数または合成数である.
(i)
$p$ が素数であるとき. $p$ が $p_1,$ $\cdots,$ $p_r$ と異なる素数の例を与える.
(ii)
$p$ が合成数であるとき. $p$ は, $p_1,$ $\cdots,$ $p_r$ と互いに素であるから, $p_1,$ $\cdots,$ $p_r$ と異なる素因数をもつ.
(i), (ii) から, 任意の素数の有限集合から新たな素数が得られるので, 素数は無限に存在する.

証明 2: 階乗を利用

 $p$ を任意の素数とする. このとき, \[ q = p!+1\ (> 1)\] は素数または合成数である.
(i)
$q$ が素数であるとき. $q$ は $p$ より大きい素数の例を与える.
(ii)
$q$ が合成数であるとき. $q$ は, $1,$ $\cdots,$ $p$ と互いに素であるから, $p$ より大きい素因数をもつ.
(i), (ii) から, 与えられた素数より大きい素数が存在するので, 素数は無限に存在する.

証明 3:「シルヴェスター数列」を利用

 こちらを参照.

証明 4:「フェルマー数」の数列を利用(ゴールドバッハ, $1730$ 年)

 こちらを参照.

証明 5(サイダック, $2006$ 年)

 $a$ を $1$ より大きい整数として, \[ a_1 = a, \quad a_{n+1} = a_n(a_n+1)\] により数列 $\{ a_n\}$ を定める. このとき, $a_1$ は少なくとも $1$ つの素因数をもつ. また, $a_n+1$ は, $a_n$ と互いに素であるから, $a_n$ と異なる素因数をもち, $a_n$ より多くの素因数をもつ. ゆえに, $\{ a_n\}$ において各項の素因数の個数は単調に増加するから, 素数は無限に存在する.

問題《エラトステネスのふるいの原理》

 $a$ を $1$ より大きい整数とする. $a$ は素数であるか, $[\sqrt a]$ 以下の素因数をもつことを示せ. ただし, $[\sqrt a]$ は $\sqrt a$ 以下の最大の整数を表す.

解答例

 合成数 $a$ が $[\sqrt a]$ 以下の素因数をもつことを示せばよい. 合成数 $a$ は, $1 < b \leqq c < a$ なる整数 $b,$ $c$ を用いて, $a = bc$ と表される. ここで, $p$ を $b$ の素因数とすると, \[ p^2 \leqq b^2 \leqq b\cdot c = a\] と $p > 0$ から $p \leqq \sqrt a$ となり, $p$ が整数であることから $p \leqq [\sqrt a]$ が得られる.

背景

 $2$ 以上 $a$ 以下の整数の一覧から素数をすべて選び出すには, 次の操作を繰り返せばよい.
(i)
$2$ を素数として選び出し, $2$ 以外の偶数を合成数として取り除く.
(ii)
すでに選び出された素数, 取り除かれた合成数以外の最小の整数 $p$ を素数として選び, $p$ 以外の $p$ の倍数を合成数として取り除く.
このように素数を見つけるアルゴリズムを「エラトステネスのふるい」(sieve of Eratosthenes)と呼ぶ. なお, 各操作で取り除かれる合成数は $[\sqrt a]$ 以下の素数の倍数である.

問題《シルヴェスター数列と素数の無限性》

 $s_1 = 2,$ $s_{n+1} = s_1\cdots s_n+1$ で定まる数列 $\{ s_n\}$ を利用して, 素数は無限に存在することを示せ.

解答例

(i)
$s_1 = 2$ は素数である.
(ii)
$s_{n+1} = s_1\cdots s_n+1$ は $s_1,$ $\cdots,$ $s_n$ のいずれとも互いに素である. また, $s_{n+1} \geqq s_1+1 > 1$ であるから, $s_{n+1}$ は $s_1,$ $\cdots,$ $s_n$ の素因数と異なる素因数をもつ.
(i), (ii) から, 数列 $\{ s_n\}$ の各項は互いに異なる素因数をもつので, 素数は無限に存在する.

背景

  • $s_1 = 2,$ $s_{n+1} = s_1\cdots s_n+1$ で定まる数列 $\{ s_n\}$ は「シルヴェスター数列」(Sylvester sequence)と呼ばれる(注意: $s_{n+1} = s_n{}^2-s_n+1$ を定義の漸化式に採用することもあり, $s_0 = 2$ とする流儀もある).
  • 素数が無限にあることは, ユークリッドによって証明された(紀元前 $3$ 世紀頃).
  • 「シルヴェスター数列」の他の応用については, こちらを参照.

問題《フェルマー数の数列と素数の無限性》

 $F_1 = 3,$ $F_{n+1} = F_1\cdots F_n+2$ で定まる数列 $\{ F_n\}$ を利用して, 素数は無限に存在することを示せ.

解答例

(i)
$F_1 = 3$ は素数である.
(ii)
$F_{n+1} = F_1\cdots F_n+2$ と $F_1,$ $\cdots,$ $F_n$ との最大公約数はいずれも $2$ の約数である. 定義により $\{ F_n\}$ の各項は奇数であるから, $F_{n+1}$ は $F_1,$ $\cdots,$ $F_n$ のいずれとも互いに素である. また, $F_{n+1} \geqq F_1+2 > 1$ であるから, $F_{n+1}$ は $F_1,$ $\cdots,$ $F_n$ の素因数と異なる素因数をもつ.
(i), (ii) から, 数列 $\{ F_n\}$ の各項は互いに異なる素因数をもつので, 素数は無限に存在する.

背景

  • $F_n = 2^{2^{n-1}}+1$ $(n \geqq 1)$ の形の整数は「フェルマー数」(Fermat number)と呼ばれる(注意: $F_n = 2^{2^n}+1$ $(n \geqq 0)$ とする流儀もある,「フィボナッチ数列」も $\{ F_n\}$ で表す).
  • 「フェルマー数」からなる数列 $\{ F_n\}$ は $F_1 = 3,$ $F_{n+1} = F_1\cdots F_n+2$ を満たす(こちらを参照).
  • ゴールドバッハは, 上記のように「フェルマー数」を使って, 素数が無限にあることの別証明を与えた($1730$ 年).
  • 「フェルマー数」の他の応用については, こちらを参照.

問題《$2$ 個の平方数の和で表される素数》

 $p$ を奇数の素数とする. $p$ がある整数 $a,$ $b$ を用いて $p = a^2+b^2$ と表されるならば, $p$ を $4$ で割った余りは $1$ であることを示せ.

解答例

 奇数の素数 $p$ がある整数 $a,$ $b$ を用いて \[ p = a^2+b^2\] と表されるとする. 偶数 $2q$ ($q$: 整数)の平方 \[ (2q)^2 = 4q^2\] を $4$ で割った余りは $0,$ 奇数 $2q+1$ ($q$: 整数)の平方 \[ (2q+1)^2 = 4(q^2+q)+1\] を $4$ で割った余りは $1$ であるから, $p$ を $4$ で割った余りは $0,$ $1,$ $2$ のいずれかである. $p$ を $4$ で割った余りが $0,$ $2$ の場合は $p$ が奇数であることに反するから, $p$ を $4$ で割った余りは $1$ である.

背景

 本問で示したことの逆も成り立つ. つまり, 奇数の素数 $p$ は, $4$ で割った余りが $1$ であるときに限り, $2$ 個の平方数の和として表されることが,「フェルマーの $2$ 平方和定理」(Fermat's theorem on sums of two squares)として知られている.

問題《$4n+1$ 型の素数の無限性》

 仮に, $4$ で割った余りが $1$ である素数が $p_1,$ $\cdots,$ $p_r$ のみであるとする.
(1)
$a = 2p_1\cdots p_r,$ $b = a^2+1$ とおき, $p$ を $b\,(> 1)$ の $1$ つの素因数とする. $p$ は非負整数 $n$ を用いて $p = 4n+3$ の形に表されることを示せ.
(2)
(1) の $a,$ $p$ に関して, $a^{p-1}$ を $p$ で割った余りについて「フェルマーの小定理」$a^{p-1} \equiv 1 \pmod p$ (整数 $a,$ 素数 $p$ は互いに素; こちらを参照)に反する結果を導け. これにより, $4$ で割った余りが $1$ である素数は無限に存在することを示せ.

解答例

(1)
\[ b = 4p_1{}^2\cdots p_r{}^2+1\] は $2,$ $p_1,$ $\cdots,$ $p_r$ のいずれとも互いに素であるから, $b$ の素因数 $p$ は $2,$ $p_1,$ $\cdots,$ $p_r$ と異なる. 仮定により $4$ で割った余りが $1$ である素数は $p_1,$ $\cdots,$ $p_r$ のみであるから, $p$ は非負整数 $n$ を用いて $p = 4n+3$ の形に表される.
(2)
$a^2+1 \equiv 0 \pmod p$ であるから, \[ a^2 \equiv -1 \pmod p\] が成り立つ. 両辺を $2n+1$ 乗すると, \[ a^{p-1} = a^{4n+2} = (a^2)^{2n+1} \equiv (-1)^{2n+1} = -1 \pmod p\] が得られる. これは「フェルマーの小定理」の主張 \[ a^{p-1} \equiv 1 \pmod p\] に反するから, $4$ で割った余りが $1$ である素数は無限に存在する.

背景

  • 奇数の素数 $p$ は, $4$ で割った余りが $1$ であるときに限り, $2$ 個の平方数の和として表される(前問参照).
  • 斜辺の長さが素数 $p$ であるような「ピタゴラスの三角形」が存在するのは, $p$ を $4$ で割った余りが $1$ であるときに限る.
  • 一般に, 初項と公差が互いに素である等差数列は無限に多くの素数の項をもつことが,「ディリクレの算術級数定理」(Dirichlet's theorem on arithmetic progressions)として知られている.

素因数分解の一意性

 次の定理は, 整数論の要となる定理であり, 整数論の基本定理(fundamental theorem of arithmetic)としても知られている.

定理《素因数分解の一意性》

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

証明

 $1$ より大きい整数 $a$ に対して示せば十分である. $a$ が素数 $a_1,$ $\cdots,$ $a_l$ の積 \[ 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_1$ で割り切れるから, 下記の補題によりある $b_k$ $(1 \leqq k \leqq m)$ は $a_1$ で割り切れる. よって, 必要に応じて番号をつけ替えると, $a_1 = b_1$ となる. このとき, \[ a_2\cdots a_l = b_2\cdots b_m\] となるから, 必要に応じて番号をつけ替えながら同様の操作を続けると, \[ a_1 = b_1, \quad \cdots, \quad a_l = b_l, \quad l = m\] となる. ゆえに, 表示 $[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 = 1}^\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 = 1}^\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}$ について, $2x-1 < [2x] \leqq 2x,$ $-2x \leqq -2[x] < -2(x-1)$ の辺々を加えると,
$-1 < [2x]-2[x] < 2$ つまり $[2x]-2[x] = 0,\ 1$
が得られる. ここで, $[2x]-2[x] = 1$ のとき, $0 \leqq 2[x] = [2x]-1 \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 = 1}^\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$ である.

約数の和

 こちらを参照.