COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

間接証明法

対偶法

問題≪$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$ 年 $1$ 月現在, 素数として確認された最大の数は $2^{77232917}-1$ (桁数は $23249425$)であり, 歴代 $7$ 位までの巨大素数は $2^n-1$ ($n$: 正の整数)の形に表される. このような表示を持つ素数は「メルセンヌ素数」(Mersenne prime)と呼ばれる.
  • $n$ が素数でも $2^n-1$ が素数であるとは限らず(例えば $2^{11}-1 = 23\cdot 89$), 「メルセンヌ素数」が無限にあるかどうかは未解決である($2018$ 年 $1$ 月現在).

問題≪$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}$ を整数とする. 多項式 \[ f(x) = x^n+pa_{n-1}x^{n-1}+\cdots +pa_1x+pa_0\] について, 次が成り立つことを示せ.
(1)
$f(x) = 0$ が整数解 $\alpha$ を持つ $\Longrightarrow$ $\alpha$ は $p$ で割り切れる.
(2)
$a_0$ が $p$ で割り切れない $\Longrightarrow$ $f(x) = 0$ は整数解を持たない.
[1996 京都大]

解答例

(1)
$f(\alpha ) = 0$ のとき, $\alpha ^n = -p(a_{n-1}\alpha ^{n-1}+\cdots +a_0)$ が成り立ち, $\alpha ^n$ は $p$ で割り切れるから, $\alpha$ は $p$ で割り切れる.
(2)
対偶を示すため, $f(x) = 0$ が整数解 $\alpha$ を持つとする. このとき, (1) から, $\alpha$ はある整数 $q$ を用いて $\alpha = pq$ と書ける. $f(\alpha ) = 0$ から \begin{align*} pa_0 &= -(p^nq^n+a_{n-1}p^nq^{n-1}+\cdots +a_1p^2q) \\ &= -p^2(p^{n-2}q^n+a_{n-1}p^{n-2}q^{n-1}+\cdots +a_1q) \end{align*} が成り立つので, $pa_0$ は $p^2$ で割り切れる. よって, $a_0$ は $p$ で割り切れる. ゆえに, 対偶は真だから, 元の命題も真である.

背景

 有理数全体の集合を $\mathbb Q$ とおく.
  • 定数でない有理数係数多項式 $f(x)$ が定数以外のすべての有理数係数多項式で割り切れないとき, $f(x)$ は $\mathbb Q$ 上「既約」(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 Q$ 上の「既約多項式」と定数の積の形に $1$ 通りに表されることが知られている.