黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【高校数学IA】素因数分解の一意性と背理法(高校3年生以上対象)

プログラミングの為の高校数学を復習するコーナー。今回は整数と背理法に関する基礎知識をまとめていく。何回もこの連載を始めて、やってる自分が詰まらないと思ったので、最近注目されている整数論の話題をしようと思う。

数学関連でホットな話題

フェルマーの最終定理
自然数x,y,zと、n \geq 3を満たす自然数nに対する不定方程式x^n+y^n = z^nを満たす解(x,y,z)は存在しない。「全ての楕円曲線はモジュラーである」と言う命題を発案した谷山•志村予想を経て、Andrew John Wilesがこれを証明した。
abc予想
互いに素な自然数a,b,cに対する不定方程式a+b=cにおいて、積abcの互いに異なる素因数の積をdとする。このとき任意の実数ε>0に対して、c > d^{(1+ε)}を満たす不定方程式の解(a,b,c)は有限個であるか?

コンピュータ(暗号)関連で知っておきたい話題

楕円曲線の加算
楕円曲線E:y^2+{a_1}xy+{a_3}y = x^3+{a_2}x^2+{a_4}x+{a_6}とする。このとき楕円曲線上の任意の2点PA(x1,y1),PB(x2,y2)を通る直線lとEとの交点をQとし、Qのy座標を反転させた点をRとする。このとき点Pに対し複数回加算を行い、PA=PBのときはこれを2倍算と呼ぶ。
ここでPに対し加算をd回行う様子を、R=dPと表す。このときPからRに至るまで何回加算を行ったかを調べる問題を楕円曲線の離散対数問題と呼ぶ。この性質は楕円曲線暗号などに応用される。

と知っている限りを列挙してみた。各種専門分野を勉強する為には大学の「整数論」や「群環体」までを勉強する必要がある。また方程式の数よりも未知数の数が多い方程式を不定方程式と呼ぶが、不定方程式の解が有限個であるか?存在するか?と言う問題も大学入試では度々登場している。今回そう言ったもののうち、背理法を使う物について触れたい。

背理法に入る前に1:素因数分解の一意性に関する定理

以下は事例2の基本的な知識として必要な事をまとめようと思う。まずは定理について説明する。

2以上の全ての自然数nは一意に素因数分解される。
ここで素因数分解とはp_k素数a_l自然数として、n = p_1^{a_1} * p_2^{a_2} * ... * p_k^{a_l}素数の積に分解できる事を言う。

これを示すために以下の問題1の[1][2]のような手順を踏んで行く。

問題1

定理1を以下の[1][2]の手順で示そう。
[1]:2以上の自然数aは素因数分解できる事を数学的帰納法より示せ。
[2]:[1]より、2以上の自然数aは一意に素因数分解できる事を示せ。

問題1で使う定理、ヒント

[2]をやる上で以下を参考にして欲しい。
[2]については、p_kq_l素数m_kn_l自然数としたとき、a = p_1^{n_1} * p_2^{n_2} * ... * p_k^{n_k} = q_1^{m_1} * q_2^{m_2} * ... * q_k^{m_l}と2通りに表すことから始まる。必要あらば「整数aとbが互いに素で、他の整数cとbとの積bcがaで割り切れるなら、実はcがaで割り切れる(*1)」と言う定理を使うと良い。

問題1の解答

[1]:2以上の自然数において、2つ以上の素数の積で表せる自然数合成数と呼ぶことにする。(詳細はwikipediaを参照下さい)

ここで2以上の整数aに関する数学的帰納法で示す。
(i):a=2のとき2=2と素数1個の積なので成立
(ii):aよりも小さい2以上の整数については定理が成立していると仮定する。以下aが素数であるか合成数であるかで場合分けする。
aが素数なら、a自身が素数1個の積である。
aが合成数の時、a=bc(1 < b < a,1 < c < a)と分解される。数学的帰納法の仮定より、bはaよりも小さく、cはaよりも小さいのでbもcも素数の積に分解される。以上よりaも素数の積に分解される。以上より題意は示された。

[2]:aを素因数に分解して2つの分解
a = p_1^{n_1} * p_2^{n_2} * ... * p_k^{n_k} = q_1^{m_1} * q_2^{m_2} * ... * q_k^{m_l} (p_m,q_n素数)を得たと仮定する。さて2つの整数の積が素数pで割り切れるなら、因数のなかの少なくとも1つがその素数で割り切れる。(*1)
3つ以上の数以上の積の場合もabc=(ab)cのように括弧くくり順次考えれば、いずれかがpの倍数になる。
したがってp_1,p_2,p_3,….,p_mのいずれかはq_1で割り切れる。いまp_1q_1で割り切るとすれば,p_1素数なのでp_1=q_1である。
p_2p_3 …p_m= q_2q_3 …q_nこの両辺の数をbとすればbよってaにおいて定理が成立する。以上より、2以上の任意の整数に対して定理が成立する。

上記解答は「素因数分解:青空学園数学科」を基に、自分の理解の追いつく限り補足を加えた。定理1の原文を見たい方は、是非上記を読んで欲しい。

話は脱線するが、256と65536と言えばどちらが素因数分解するのが困難であろうか?恐らく殆どの人が65536と答えるであろう。このように整数が大きくなればなるほど素因数分解が困難であり、この性質を上手く利用したのがRSA暗号だと言う事は記憶に新しい。

背理法とは?

さて本題の背理法について触れたい。背理法とは命題pを示すのに、「pでない」と仮定して矛盾を示す方法を言う。

背理法の使いどころ

背理法は整数の問題で多く用いられる。特に一見して当たり前で、「pが真」であることを示すのが困難な場合に用いられる。今回は以下の事例を通し、背理法について見て行こうと思う。

事例:2^{\frac{n}{m}}(n,mは互いに素)が無理数である事を証明する

今回は背理法の問題ではすっかりおなじみのものであるが、証明の方法が複数あるものを紹介したい。

問題2(2002 東京理科大・理・数 Izumiの数学より)

(1):背理法とは何かを20字以上、100字以内で説明せよ。
(2):2^{\frac{1}{3}} が無理数であることを、背理法を用いて証明せよ。

解答

(1):命題「pならばq」を示すのに、「pならばqでない」と仮定して矛盾を示す方法
ある命題 P を証明したいときに、P が偽であると仮定して、そこから矛盾を導くことにより、P が偽であるという仮定が誤り、つまり P は真であると結論付けること(wikipediaより引用 2016.2.25 訂正)

(2):無限降下法に依る証明

2^{\frac{1}{3}} = \frac{b}{a} <=> 2 = \frac{b^3}{a^3} => 2a^3 = b^3 このとき左辺は偶数より、b=2b'とおける。
すると2a^3 = 8b'^3 => a^3 = 4b'^3 さらにa=2a'とすれば再び2a'^3 = b'^3となり、無限回2で割れる事があるがこれはa=b=0以外不可能である。この事からaとbが互いに素である事に反し、2^{\frac{1}{3}} は無理数である。

(2):素因数分解の一意性に依る証明

2^\frac{1}{3} = \frac{b}{a} <=> 2 = \frac{b^3}{a^3} => 2a^3 = b^3

このとき2*a*a*a = b*b*b より左辺の2の因数の個数は奇数に対し、右辺の2の因数の個数は偶数となる。ここで左辺と右辺の2の因数の個数が一致しないことにより、(例題1より)素因数分解の一意性がに反するので矛盾が生じる。以上より2^{\frac{1}{3}} は無理数である。

尚本問は不定方程式の問題として言い換えることも可能で、「互いに素な自然数a,bにおける不定方程式2a^3 = b^3の解は存在しない事を示せ」と言い換える事ができる。

合わせて読みたい

無限降下法と言えば受験生時代全く使いこなせなかったものの1つだ。筆者が無限降下法を知るきっかけとなった入試問題が「難関大学への数学」へ収録されている。趣味で見たい人は「Izumiの数学」や「無限降下法」、整数について深く勉強したい人は「青空学園数学科」を参考にして欲しい。