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

Well-Known Problems and Theorems in Mathematics

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

間接証明法

対偶法

定理≪命題とその対偶の同値性≫

 命題 $p,$ $q$ に対して,「$p$ $\Longrightarrow$ $q$」とその対偶「$\bar q$ $\Longrightarrow$ $\bar p$」は同値である. ここで, $\bar p,$ $\bar q$ はそれぞれ $p,$ $q$ の否定を表す.

証明

 $p,$ $q$ の真偽に応じて $p \Longrightarrow q,$ および $\bar q,$ $\bar p$ と $\bar q \Longrightarrow \bar p$ の真偽がどうなるかを調べると, 次の表のようになる. ただし, $\mathrm T$ は真, $\mathrm F$ は偽を表す. \[\begin{array}{c|c|c|c|c|c} p & q & p \Longrightarrow q & \bar q & \bar p & \bar q \Longrightarrow \bar p \\ \hline \mathrm T & \mathrm T & \mathrm T & \mathrm F & \mathrm F & \mathrm T \\ \mathrm T & \mathrm F & \mathrm F & \mathrm T & \mathrm F & \mathrm F \\ \mathrm F & \mathrm T & \mathrm T & \mathrm F & \mathrm T & \mathrm T \\ \mathrm F & \mathrm F & \mathrm T & \mathrm T & \mathrm T & \mathrm T \end{array}\] いずれの場合にも $p \Longrightarrow q$ と $\bar q \Longrightarrow \bar p$ の真偽は一致するから, $p \Longrightarrow q$ と $\bar q \Longrightarrow \bar p$ は同値である.

注意

 上記のような表を「真理値表」(truth table)と呼ぶ. $p \Longrightarrow q$ の真偽は, 上記のようになる(公理). $p$ が偽の場合には, $q$ の真偽にかかわらず, $p \Longrightarrow q$ は真であることに注意が必要である.

問題≪$2^n-1$ がメルセンヌ素数である条件≫

 $n$ を正の整数とする. $2^n-1$ が素数ならば, $n$ は素数であることを示せ.

解答例

 対偶を示す. つまり, $n$ を $1$ または合成数として, $2^n-1$ は $1$ または合成数であることを示す.
(i)
$n = 1$ のとき. $2^n-1 = 2^1-1 = 1$ である.
(ii)
$n$ が合成数のとき. $n$ は $n = lm$ ($l,$ $m$: 整数, $l > 1,$ $m > 1$)と書けて \begin{align*} &2^n-1 = 2^{lm}-1 = (2^l)^m-1 \\ &\qquad\ \ = (2^l-1)\{ 2^{l(m-1)}+\dots +1\}, \\ &2^l-1 > 2^1-1 = 1,\\ &2^{l(m-1)}+\dots +1 \geqq 2^{2\cdot 1}+1 > 1 \end{align*} となるから, $2^n-1$ は合成数である.
(i), (ii) から対偶は真であるので, 示すべき命題も真である.

背景

  • 素数が無限に存在することはユークリッドの『原論』で証明されているが, 素数の出現パターンはかなり不規則であるため, コンピュータを駆使しても具体的に巨大な素数を見つけるのは容易ではない. $2018$ 年 $12$ 月現在, 素数として確認された最大の数は $2^{82589933}-1$ (桁数は $24862048$)であり, 歴代 $8$ 位までの巨大素数は $2^n-1$ ($n$: 正の整数)の形に表される. このような表示を持つ素数は「メルセンヌ素数」(Mersenne prime)と呼ばれる.
  • $n$ が素数でも $2^n-1$ が素数であるとは限らず(例えば $2^{11}-1 = 23\cdot 89$), 「メルセンヌ素数」が無限にあるかどうかは未解決である($2018$ 年 $12$ 月現在).

問題≪$2^n+1$ がフェルマー素数である条件≫

 $n$ を正の整数とする. $2^n+1$ が素数であるならば, $n$ は $n = 2^m$ ($m$: 非負整数)と表されることを示せ.

解答例

 $n$ が $1$ より大きい奇数 $d$ で割り切れるとして $q = \dfrac{n}{d}$ とおくと, \begin{align*} 2^n+1 &= 2^{qd}+1 = (2^q)^d+1 \\ &= (2^q+1)\{ 2^{q(d-1)}-2^{q(d-2)}+\cdots +1\} \end{align*} となり, $2^n+1$ は合成数となる.
よって, 対偶「$n$ が $n = 2^m$ ($m$: 非負整数)と表されない $\Longrightarrow$ $2^n+1$ は素数でない」は真であるから, 示すべき命題も真である.

背景

  • $2^n+1$ ($n$: 正の整数)の形に表される素数を「フェルマー素数」(Fermat prime)と呼ぶ. 本問で示した通り, $n$ は $2$ の累乗であるから,「フェルマー素数」は $2^{2^m}+1$ ($m$: 非負整数)の形に表される素数に他ならない. 現在, $2^{2^m}+1$ の形の整数のうち, 素数であると確認されているのは, $0 \leqq m \leqq 4$ の場合の $5$ 個 $3,$ $5,$ $17,$ $257,$ $65537$ のみである($2018$ 年 $1$ 月現在).
  • 正 $N$ 角形が定規とコンパスのみで作図できるのは, $N = 2^l$ ($l$: $2$ 以上の整数)であるか, $N = 2^lp_1\cdots p_r$ ($l$: 非負整数, $r$: 正の整数, $p_1,$ $\cdots,$ $p_r$: 相異なる「フェルマー素数」)である場合に限ることが, ガウスによって示されている(1801 年).

問題≪アイゼンシュタイン多項式≫

 $n$ を $2$ 以上の整数, $p$ を素数, $a_0,$ $\cdots,$ $a_{n-1}$ を $p$ の倍数とする. 多項式 \[ f(x) = x^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0\] について, 次が成り立つことを示せ.
(1)
$f(x) = 0$ が整数解 $\alpha$ をもつ $\Longrightarrow$ $\alpha$ は $p$ で割り切れる.
(2)
$a_0$ が $p^2$ で割り切れない $\Longrightarrow$ $f(x) = 0$ は整数解をもたない.
(参考: 1996 京都大)

解答例

 各番号 $k\ (0 \leqq k \leqq n-1)$ に対して, $a_k$ はある整数 $a'_k$ を用いて $a_k = pa'_k$ と書ける.
(1)
$f(\alpha ) = 0$ のとき, \begin{align*} \alpha ^n &= -(a_{n-1}\alpha ^{n-1}+\cdots +a_1\alpha +a_0) \\ &= -p(a'_{n-1}\alpha ^{n-1}+\cdots +a'_1\alpha +a'_0) \end{align*} は $p$ で割り切れるから, $\alpha$ は $p$ で割り切れる.
(2)
対偶を示すため, $f(x) = 0$ が整数解 $\alpha$ をもつとする. このとき, (1) から, $\alpha$ はある整数 $q$ を用いて $\alpha = pq$ と書けるので, \begin{align*} a_0 &= -(\alpha ^n+a_{n-1}\alpha ^{n-1}+\cdots +a_1\alpha ) \\ &= -(p^nq^n+pa'_{n-1}\cdot p^{n-1}q^{n-1}+\cdots +pa'_1\cdot pq) \\ &= -p^2\left( p^{n-2}q^n+a'_{n-1}p^{n-2}q^{n-1}+\cdots +a'_1q\right) \end{align*} は $p^2$ で割り切れる. ゆえに, 対偶は真だから, 元の命題も真である.

背景

 整数全体の集合を $\mathbb Z,$ 有理数全体の集合を $\mathbb Q$ とおき, $R$ をそのいずれかとする. $R$ の要素を係数とする多項式を $R$ 上の多項式と呼ぶ.
  • 定数でない $R$ 上の多項式 $f(x)$ が $R$ 上の定数と $f(x)$ の定数倍以外のすべての多項式で割り切れないとき, $f(x)$ は $R$ 上「既約」(irreducible)であるという. 例えば, $x^2-1 = (x+1)(x-1)$ は $\mathbb Q$ 上「既約」でない. また, $x^2-2$ が $x^2-2 = (ax+b)(cx+d)$ ($a,$ $b,$ $c,$ $d$: 定数)と因数分解できるとすると, $\sqrt 2 = -\dfrac{b}{a}$ または $\sqrt 2 = -\dfrac{d}{c}$ となり, $\sqrt 2$ が無理数であることにより $a,$ $b,$ $c,$ $d$ は有理数とはならないので, $x^2-2$ は $\mathbb Q$ 上「既約」である.
  • 万能ではないが, 多項式が「既約」であるかどうかの判定に便利な, 次のような定理がある: ある素数 $p$ に対して, 最高次の項の係数が $p$ で割り切れず, それ以外の係数が $p$ で割り切れて, 定数項が $p^2$ で割り切れないような整数係数多項式は $\mathbb Q$ 上既約である(アイゼンシュタインの既約判定法). 特に, このような $2$ 次以上の多項式 $f(x)$ について, $f(x) = 0$ は整数解を持たない. 本問では, こちらを示した.
  • $\mathbb Z$ 上「既約」な多項式は $\mathbb Q$ 上でも「既約」であることが知られており(ガウスの補題), これを認めると,「アイゼンシュタインの既約判定法」は, 次のように証明できる: 条件を満たす整数係数 $n$ 次多項式 $f(x) = a_nx^n+\cdots +a_1x+a_0$ が $\mathbb Z$ 上「既約」であることを示せばよい. 整数係数多項式 $g(x) = b_lx^l+\cdots +b_1x+b_0,$ $h(x) = c_mx^m+\cdots +c_1x+c_0$ について \[ f(x) = g(x)h(x)\] が成り立つとして, $g(x)$ または $h(x)$ が定数になることを示す. 条件により, $a_0 = b_0c_0$ は $p$ で割り切れて $p^2$ で割り切れないから, $b_0$ が $p$ で割り切れて $c_0$ が $p$ で割り切れないとして一般性を失わない. $g(x)$ において, 係数がすべて $p$ で割り切れることはないから, 係数が $p$ で割り切れない次数最小の項を $b_kx^k$ とする. このとき, \[ a_k = b_0c_k+\cdots +b_{k-1}c_1+b_kc_0\] において $b_kc_0$ 以外の項は $p$ で割り切れて $b_kc_0$ は $p$ で割り切れないから, $a_k$ は $p$ で割り切れない. 条件により, $a_k = a_n$ であるから, $k = n$ となり, $l = n,$ $m = 0$ となる. よって, $h(x)$ は定数となる.
  • なお, 素因数分解と同様に, 定数でないすべての有理数係数多項式は $\mathbb Q$ 上の「既約多項式」と定数の積の形に $1$ 通りに表されることが知られている.