対偶と背理法について　　問題のどこをみて、対偶を使うか、背理法を使うか判断しますか？

対偶について

Point 複雑な事象→簡単な事象を示すときに有効。

例　2^n -1が素数ならばnが素数であることを示せ。(京都府立医科大)

2^n -1を因数分解しても指数部分が素数であることはどう考えても難しいので、簡単な事象に変えてあげます。

対偶をとってnが合成数ならば2^n -1が合成数を証明すれば良いわけです。これならばn＝PQ(PQはそれぞれ自然数)として代入すれば良いわけです。(有名問題なので完全数と調べれば証明は出てきます。)

背理法について

Point 存在しないことを証明するときに有効。

例　nと2n＋1が互いに素であることを示せ。(一橋大)

これはつまり「nと2n＋1には2以上の公約数dが存在しない」ことを示せば良いわけです。

ここでそのようなdが存在すると仮定します。

自然数M,Lを用いて

n＝Md 2n＋1＝Ldと置いて代入すると

2(Md)＋1＝Ld

1＝(L−2M)d

dは２以上の自然数であり、L−2Mは自然数なのでこの等式は絶対に満たされません。1は2以上の自然数ではないのに

1＝(二以上の自然数)×(自然数)で表されてしまうからです。こんなことは絶対にないですよね。なのでこのようなdは存在せず矛盾なんです。よってd＝1に限るため、公約数は1であって互いに素だと証明できるわけです。

理解できたでしょうか。難しくてもノートにこの証明を実際に手を動かして書いてみると対偶と背理法の真髄が理解できるでしょう。