背理法・対偶法を使った証明問題について見ていきます。
背理法を使った証明は何度も紹介しましたが、まとめの意味を含めて扱います。
(例題1)
\(n^3+1=p^3\) を満たす素数\(p\)と自然数\(n\)の組は存在しないことを示せ。
\(n^3+1\)が因数分解できるので、\(p^3\)の\(p\)3つ分を積のそれぞれの項に分けて考える方法でもよいですが、\(p^3-n^3=1\)の形にして因数分解したほうが楽なので、解法ではこの方法をとります。
(解答)
等式を満たす\(n,p\)が存在すると仮定する。
\(p^3-n^3=1\)より
\((p-n)(p^2+pn+n^2)=1\)
\(p,n\)は自然数なので、\(p^2+pn+n^2>0\)より
\(p-n=1\)・・・①
\(p^2+pn+n^2=1\)・・・②
①\(p=n+1\) を②に代入して
\((n+1)^2+(n+1)n+n^2=1\)
整理すると
\(3n^2+3n=0\)
\(3n(n+3)=0\)・・・③
\(n\)は自然数なので、\(n(n+3)>0\)より③と矛盾。
よって\(n^3+1=p^3\) を満たす素数\(p\)と自然数\(n\)の組は存在しない。
(例題2)
\(n\)は自然数とする。
\(2^n-1\) が素数ならば、\(n\)も素数であることを証明せよ。
結論の\(n\)のほうが扱いやすそうなので、対偶をとってみます。
素数でない自然数は、\(1\)か合成数なので、
対偶は「\(n\)が\(1\)もしくは合成数ならば、\(2^n-1\)は\(1\)もしくは合成数」です。途中で次の因数分解公式を利用します。
\(x^n-1=(x-1)(x^{n-1}+x^{n-2}+\)\(・・・+x+1)\)
(解答)
対偶は、「\(n\)が\(1\)もしくは合成数ならば、\(2^n-1\)は\(1\)もしくは合成数」・・・(A) である。
(1)\(n=1\)のとき
\(2^n-1=2-1=1\) となり(A)が成立。
(2)\(n\)が合成数、つまり \(n=rs\) (\(r,s\)は\(1\)より大きい自然数)のとき
\(2^n-1\)
\(=2^{rs}-1\)
\(=(2^r)^{s}-1\)
\(=N^{s}-1\) (\(2^r=N\)とする)
\(=(N-1)(N^{s-1}+N^{s-2}\)\(+・・・+N+1)\)
ここで、
\(N-1=2^r-1\) は、\(r>1\)だから\(1\)より大きい自然数であり
\(N^{s-1}+N^{s-2}\)\(+・・・+N+1\) も\(1\)より大きい自然数。
よって、\(2^n-1\)は合成数である。
以上より、もとの命題の対偶が真であることが示されたので、もとの命題も真である。
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。