これは強力。背理法

【問題】（宿題でした）

3で割ると1あまり、6で割ると5あまるような整数はあるでしょうか？
あるならば、これを一般式の形で示してください。ないのであれば、ないことを証明してください。

【解答】

3で割ると1あまる数を調べてみましょう。同時に6で割ると5あまる数も調べます。

両方を同時に満たしてくれる整数が、なかなか現れてくれませんね。
そんな数はない、と言いたくなりますが、まだ41までを知らべただけですから、この先にもしかすると現れる可能性がありますよね。
さて、どうしましょうか？

ここはひとつ、数学の代表的な（証明）手法である背理法を使ってみましょう。
とりあえず、いまは「3で割ると1あまり、6で割ると5あまるような整数」はないのではないか、と思いそれを証明したいと思っています。そこで・・・

3で割ると1あまり、6で割ると5あまる整数が存在する、と仮定します。

その数をNと表すとすると・・・

Nは仮定した条件を満たす数です。で、Nが条件を満たすのであれば、N+6もまた条件を満たす数になるはずです（ちなみにこの6というのは、3と6の最小公倍数です）。
表をよく見てください。「3で割ると1あまり、6で割ると5あまるような整数」は、連続する6つの整数の中に1個だけ存在する状況に気づきませんか。
この連続する6つの整数は、1、2、3、4、5、6かもしれませんし、
1003、1004、1005、1006、1007、1008かもしれません。

この表は、整数の並びのどこから「切り取っても」いいので、とにかく連続する6つの整数があれば、そのうちの1つは「3で割ると1あまり、6で割ると5あまるような整数」であるはずだよ、もしそんな数があるならね！　と言っています。

では、本当にそうなっているのかを調べてみましょう。一番簡単に思える整数の並びを切り取って調べてみます。

○をつけた箇所が各々の条件を満たす数です。例えば、1は3で割ると1あまる数ですが、6で割ると5あまる数ではない、ということを示しています。
さて、表を見てみると・・おかしいですね、「3で割ると1あまり、6で割ると5あまるような整数」があるのならば、この表のどこかで○が縦に2つ並ぶ数があるはずです。

あるはずのものがない、ということは・・

3で割ると1あまり、6で割ると5あまる整数が存在する、

とした仮定が誤っていたのです。すなわち・・・

3で割ると1あまり、6で割ると5あまるような整数はない

ということになります。

最初に正しいと仮定したことから始めて、正しく論理を展開したにもかかわらず矛盾がおきてしまう。ならば仮定が間違っていたんだね、という証明方法を「背理法」と呼びます。かなり強力な証明方法なので、しっかり身につけたいところです。

ところで、この証明ですが文字を使った式を用いて、もっと簡単に証明することもできます。

a、bを整数として（もちろんNも整数です）
N＝3a+1　であり、N＝6b+5　であるわけですから・・

3a+1＝6b+5
3a＝6b+4
a＝2b+4/3

右辺の2bは整数です。ですがこれに4/3が足されており、結局右辺は整数になりません。左辺はaでこれは整数として考えを始めました。
ということは、a（bもですが）を整数と仮定して始めた検証に矛盾を生じたことになります。これもまた背理法。
a、bが整数であれば、3a+1＝6b+5　が成り立たないことを示しており、3で割ると1あまり、6で割ると5あまるような整数はない、ことを証明しています。

ここで、3と6なんて、たまたま割り切れる係数の組み合わせになっているだけじゃないか！と思った方は、かなり鋭い数学センスの持ち主だと思います。

実は・・たとえば3と5や4と7など、係数が互いに素となる組み合わせの場合には、求めるNは必ず存在し、互いに素でない場合（この例では、3と6でした）には、Nは存在するかもしれないし存在しないかもしれない、という状況が発生します。
ですので、3と6なんて、たまたま割り切れる係数・・ではなく、「存在しないN」を出題しようとすると、そうなってしまうのでありました。

【おまけ】

AとBが互いに素であるとき、Aで割るとaあまり、Bで割るとbあまるような整数Nが必ず存在する
（A、B、a、b、N　はすべて整数。）