数学

【数学】無限降下法と大学入試問題を用いた使用例

無限降下法

今回は大学入試問題の整数問題のテーマとして用いられる無限降下法についてお勉強していきましょう。

ペンちゃん
ペンちゃん
今回は無限降下法についてお勉強しましょう!

無限降下法とは

無限降下法とは、整列集合という性質を利用した、証明の一手法となります。

例えば自然数の場合、2つの自然数の間には大きいか小さいか等しいかという順序をつけることができます。また、自然数の集合には1という自然数の中で一番小さい数が存在します。

この2つの性質を用いて証明する方法を無限降下法といいます。まとめると次のようになります。

無限降下法
      式Xが成り立たないことを示したい。
      ①自然数a,b,・・・に対して式Xが成り立つと仮定する。
      ②自然数a’,b’,・・・が a’< a, b'< b ,・・・を満たし、かつ式Xが成り立つことを示す。
      ③繰り返すと自然数 a’, b’, c’ は無限に小さくすることができるが、a’, b’, c’ は自然数であることに矛盾するので最初の式Xは成り立たない。

例題で無限降下法を見てみよう

まずは例題を用いても無限降下法を見てみましょう。

例題

$$\sqrt{2}が無理数であることを証明せよ$$

無理数については下記記事をご覧ください。

無理数とは?無理数であることの証明方法無理数とは 無理数の定義 無理数とは有理数でない実数のことです。つまり以下のように定義できます。 任意の整数a,bに対して ...

背理法を用いた例題の解答

まずは背理法を用いた一般的な証明を見てみましょう。

$$\sqrt{2}が有理数であると仮定する。$$
このとき、互いに素な自然数m,nが存在して
$$\sqrt{2}=\frac{n}{m}$$
と書ける。両辺2乗して整理すると、
$$2m^{2}=n^{2}$$
ここで、左辺は偶数であるから
$$n^{2}は偶数、すなわちnは偶数となる。$$
$$したがって自然数n_1が存在してn=2n_1と書ける$$
これを代入すると
$$2m^{2}=4n_1^{2}よりm^{2}=2n_1^{2}$$
$$よって、m^{2}は偶数、すなわちmは偶数となる。$$
このとき、m,nはともに偶数となり、m,nが互いに素であることに矛盾する
$$よって、\sqrt{2}は無理数である。$$

無限降下法を用いた例題の解答

これを無限降下法を用いて証明してみよう。

$$\sqrt{2}が有理数であると仮定する。$$
このとき、ある自然数m,nが存在して(互いに素を仮定しないのがポイント
$$\sqrt{2}=\frac{n}{m}$$
と書ける。両辺2乗して整理すると、
$$2m^{2}=n^{2}$$
ここで、左辺は偶数であるから
$$n^{2}は偶数、すなわちnは偶数となる。$$
$$したがって自然数n_1が存在してn=2n_1と書ける$$
これを代入すると
$$2m^{2}=4n_1^{2}よりm^{2}=2n_1^{2}$$
$$よって、m^{2}は偶数、すなわちmは偶数となる。$$
$$したがって自然数m_1が存在してm=2m_1と書ける$$
$$つまり、\sqrt{2}=\frac{n}{m}=\frac{2n_1}{2m_1}=\frac{n_1}{m_1}$$
と書ける。この操作を繰り返すと、
$$n_1,m_1は無限に小さくすることできる。$$
$$しかし、n_1,m_1は自然数であることに矛盾する。$$
$$よって、\sqrt{2}は無理数である。$$

大学入試問題を解いてみよう

大学入試問題を無限降下法を用いて解いてみましょう。

九州大学前期理系(2014)

(1)任意の自然数aに対し、a2を3で割った余りは0か1あることを証明せよ。
(2)自然数a, b, c がa2+b2=3c2を満たすと仮定すると、a, b, c はすべて3で割り切れなければならないことを証明せよ。
(3)a2+b2=3c2を満たす自然数a, b, cは存在しないことを証明せよ。

ヒント

ヒント

(1)aを3で割った余りで場合分けしてみよう。
(2)右辺は3の倍数より、左辺も3の倍数であるので(1)を用いて場合分けしてみよう。
(3) (2)よりa, b, c はすべて3の倍数であることを用いて無限降下法を使おう。

無限降下法を用いた解答

それでは解答を見てみましょう。

(1)任意の自然数aに対し、
a≡0 (mod 3), a≡1 (mod 3), a≡2 (mod 3)
のいづれかが成り立つ。このとき、
a≡0⇒a2≡0 (mod 3)
a≡1⇒a2≡1 (mod 3)
a≡2⇒a2≡1 (mod 3)
したがって、a2を3で割った余りは0か1である。

(2)自然数a, b, cがa2+b2=3c2を満たすと仮定すると、右辺は3の倍数より、左辺も3の倍数である。
したがって、(1)より、a2≡0 (mod 3),b2≡0 (mod 3)となる。
よって、a≡0 (mod 3), b≡0 (mod 3)となる。
このとき、c2≡0 (mod 3)より、c≡0 (mod 3)である。
以上より、a≡0 (mod 3), b≡0 (mod 3), c≡0 (mod 3)
よって、a, b, cはすべて3で割り切れなければならない。

(3)a2+b2=3c2を満たす自然数a, b, cが存在すると仮定すると、(2)より、a=3a’, b=3b’, c=3c’ (a’, b’, c’は自然数)
とおける。
このとき、9a’2+9b’2=27c’2より、a’2+b’2=3c’2
このような操作を繰り返すと、自然数 a’, b’, c’ は無限に小さくすることができる。
しかし、a’, b’, c’ は自然数であることに矛盾する。
よって、a2+b2=3c2を満たす自然数a, b, cは存在しない。

まとめ

今回は大学入試問題の整数問題のテーマとして用いられる無限降下法についてお勉強しました。ぜひ覚えておきましょう。

無限降下法
      式Xが成り立たないことを示したい。
      ①自然数a,b,・・・に対して式Xが成り立つと仮定する。
      ②自然数a’,b’,・・・が a’< a, b'< b ,・・・を満たし、かつ式Xが成り立つことを示す。
      ③繰り返すと自然数 a’, b’, c’ は無限に小さくすることができるが、a’, b’, c’ は自然数であることに矛盾するので最初の式Xは成り立たない。
ペンちゃん
ペンちゃん
今回は無限降下法についてお勉強したよ!