間接証明法
対偶法
定理《命題とその対偶の同値性》
命題 $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$ は素数であることを示せ.
(参考: $2022$ 宮崎大, $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$ は合成数である.
参考
- 素数が無限に存在することはユークリッドの『原論』で証明されているが, 素数の出現パターンはかなり不規則であるため, コンピュータを駆使しても具体的に巨大な素数を見つけるのは容易ではない. 素数として確認された最大の数は $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$ 月現在).
問題《$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$ 年).
問題《アイゼンシュタイン多項式》
$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$ 通りに表されることが知られている.
背理法
問題《円周上の $2$ 点間の距離》
$n$ 角形 $\mathrm P_1\mathrm P_2\cdots\mathrm P_n$ が半径 $r$ の円周に内接しているとする.
このとき,
\[\mathrm P_i\mathrm P_j < \frac{2\pi r}{n} \quad \cdots [\ast ]\]
を満たす $2$ つの頂点 $\mathrm P_i,$ $\mathrm P_j$ $(i \neq j)$ が少なくとも $1$ 組存在することを示せ.
(参考: 東北工業大)
解答例
仮に $[\ast ]$ を満たす $2$ つの頂点 $\mathrm P_i,$ $\mathrm P_j$ $(i \neq j)$ が存在しないとする.
このとき,
\[\mathrm P_1\mathrm P_2 \geqq \frac{2\pi r}{n}, \quad \cdots, \quad \mathrm P_{n-1}\mathrm P_n \geqq \frac{2\pi r}{n}, \quad \mathrm P_n\mathrm P_1 \geqq \frac{2\pi r}{n}\]
が成り立つから, 辺々を加えると
\[\mathrm P_1\mathrm P_2+\cdots +\mathrm P_{n-1}\mathrm P_n+\mathrm P_n\mathrm P_1 \geqq 2\pi r\]
が得られる.
半径 $r$ の円周の長さ $2\pi r$ は $n$ 角形 $\mathrm P_1\mathrm P_2\cdots\mathrm P_n$ の周の長さより大きいから, これは矛盾である.
ゆえに, $[\ast ]$ を満たす $2$ つの頂点 $\mathrm P_i,$ $\mathrm P_j$ $(i \neq j)$ が少なくとも $1$ 組存在する.
ゆえに, $[\ast ]$ を満たす $2$ つの頂点 $\mathrm P_i,$ $\mathrm P_j$ $(i \neq j)$ が少なくとも $1$ 組存在する.