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

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$ は素数であることを示せ.
(参考: $2007$ 千葉大)

解答例

 対偶を示す. つまり, $n$ を $1$ または合成数として, $2^n-1$ は $1$ または合成数であることを示す.
(i)
$n = 1$ のとき. $2^n-1 = 2^1-1 = 1$ である.
(ii)
$n$ が合成数のとき. $n$ は $n = lm$ ($l,$ $m$: 整数, $l,$ $m > 1$)と表せて \[\begin{aligned} &2^n-1 = 2^{lm}-1 = (2^l)^m-1 \\ &\qquad\ \ = (2^l-1)\{ 2^{l(m-1)}+\dots +1\} \end{aligned}\] となる. ここで, 右辺の各因数は整数であり, $1 < l < n$ から \[ 1 = 2^1-1 < 2^l-1 < 2^n-1\] であるので, $2^n-1$ は合成数である.
(i), (ii) から対偶は真であるので, 示すべき命題も真である.

参考

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

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

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

解答例

 対偶「$n$ が $n = 2^m$ ($m$: 非負整数)と表されないならば, $2^n+1$ は素数でない」を示す. $n$ が $1$ より大きい奇数 $d$ で割り切れるとして $q = \dfrac{n}{d}$ とおくと, \[\begin{aligned} 2^n+1 &= 2^{qd}+1 = (2^q)^d+1 \\ &= (2^q+1)\{ 2^{q(d-1)}-2^{q(d-2)}+\cdots +1\} \end{aligned}\] となる. ここで, 右辺の各因数は整数であり, $q < n$ から \[ 1 < 2^q+1 < 2^n+1\] であるので, $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$ のみである($2021$ 年 $12$ 月現在).
  • 正 $N$ 角形が定規とコンパスのみで作図できるのは, $N = 2^l$ ($l$: $2$ 以上の整数), または $N = 2^lp_1\cdots p_r$ ($l$: 非負整数, $r$: 正の整数, $p_1,$ $\cdots,$ $p_r$: 相異なる「フェルマー素数」)の場合に限ることが, ガウスによって示されている($1801$ 年).
(最終更新日: $2022/04/09$)

問題《アイゼンシュタイン多項式》

 $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 = pa'_k$ ($a'_k$: 整数)とおく.
(1)
整数 $\alpha$ が $f(\alpha ) = 0$ つまり \[\alpha ^n+a_{n-1}\alpha ^{n-1}+\cdots +a_1\alpha +a_0 = 0\] を満たすとき, \[\begin{aligned} \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{aligned}\] (かっこ内は整数)であり, $\alpha ^n$ は $p$ で割り切れるから, $\alpha$ は $p$ で割り切れる.
(2)
対偶を示すため, $f(x) = 0$ が整数解 $\alpha$ をもつとする. このとき, (1) により, $\alpha$ はある整数 $q$ を用いて $\alpha = pq$ と表せる. $f(\alpha ) = 0$ から \[\begin{aligned} 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{aligned}\] であり, $a_0$ は $p^2$ で割り切れる. よって, 対偶は真であるから, 元の命題も真である.

参考

 整数全体の集合を $\mathbb Z,$ 有理数全体の集合を $\mathbb Q$ とおき, $R$ をそのいずれかとする. $R$ の要素を係数とする多項式を $R$ 上の多項式と呼ぶ.
  • 定数でない $R$ 上の多項式 $f(x)$ が定数と $f(x)$ の定数倍以外のすべての $R$ 上の多項式で割り切れないとき, $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)$ は定数となる.
  • 整数の素因数分解と同様に, 定数でないすべての有理数係数多項式は, 最高次の係数が $1$ である $\mathbb Q$ 上「既約」な多項式と定数の積の形に, 順序の違いを除いてただ $1$ 通りに表されることが知られている.
(最終更新日: $2022/04/09$)