大学入試数学 背理法と有限個の仮定—候補の一覧に入らない整数を作って否定する｜武蔵野個別指導塾

一覧の積に1を足した数を素数と決めつけると、30031が59と509の積になる場面で止まります。どの候補でも割り切れない素因数を拾う組み立てが背理法です。

よくあるのは、演習の解き直しで「一覧にある素数を全部掛けて1を足せば、新しい素数ができる」と書き、その数を素数と決めて答案を閉じる場面です。計算は合っているのに最後の一行で減点されるのは、有限個の候補で世界を閉じたときに、その外側の整数をどう作るかという論証の組立てが抜けているからです。

一覧で閉じた仮定を崩す三つの出方

まず、この型がどんな問いで出るかを見ます。一つ目は個数の有限性を否定する型です。「素数は n 個だけしかない」と仮定し、すべての素数を一覧にしたうえで、そのどれでも割り切れない数を作ります。二つ目は範囲の有限性を否定する型です。「n 以下の素数だけが素数である」と仮定し、n より大きい素因数をもつ数を作ります。三つ目は候補の尽くし方の誤りを示す型です。「条件を満たす整数は a₁, a₂, …, aₙ の n 個だけ」と仮定し、条件を満たす別の整数を作ります。

三つに共通するのは、答案の最初に一覧を書き切ることです。どの候補までを仮定に含めたのかが曖昧なままでは、後で作った数が一覧の外にあると言えません。そのうえで、最初に見る整数条件は二つあります。作った数が 1 より大きいこと、そして一覧のどの数でも割り切れないことです。この二つがそろって初めて、一覧の外の素因数を1個取り出せます。

入試の答案では、この三つの型が同じ問いの中で入れ替わって現れます。たとえば素数についての問いでも、答案の冒頭で「すべての素数を一覧にする」と書くか「n 以下の素数を一覧にする」と書くかで、最後に否定できる仮定が変わります。前者は個数の有限性を、後者は範囲の有限性を閉じています。どちらを閉じたのかを意識して書き分けると、作る数の形も、矛盾を書く位置も、答案の中で一貫します。

有限個と仮定したときに答案へ書く四行

背理法は、示したい結論の否定を仮定して矛盾を導く方法です。ここで否定するのは「もっとある」ではなく「これで全部」という形の主張です。条件を満たす整数が a₁, a₂, …, aₙ の n 個だけだと仮定します。この仮定は、候補を数え上げて閉じた状態を作ります。閉じた一覧から外へ出る整数を1個構成できれば、仮定は崩れます。

答案は四行に分けて書くと崩れません。第一行は仮定です。「条件を満たす整数は a₁, a₂, …, aₙ の n 個だけである」と書きます。第二行は構成です。N = a₁a₂…aₙ + 1 とおきます。第三行は確認です。各 i について N を aᵢ で割った余りが 1 になるので、aᵢ は N を割り切りません。第四行は矛盾です。N は 1 より大きいので素因数 q をもち、q は一覧のどれとも異なります。ところが仮定では一覧がすべてなので、q も一覧に入っていなければなりません。同じ q が一覧にあり、かつ一覧にないことになり、矛盾です。

この型を学ぶ意味は、無限を直接数えられないときに、有限の一覧という手に負える対象へ言い換えられる点にあります。結論の「無限に存在する」をそのまま示そうとすると、すべての候補を並べる作業になります。ところが否定して「有限個だけ」と仮定すると、候補は a₁ から aₙ までの有限個になり、積や余りの計算が使えます。無限についての主張を有限の計算へ持ち込むのが、この背理法の役割です。

この四行で肝になるのは、N 自身が素数かどうかを一度も使わない点です。使うのは「N を割る素数が1個ある」ことと「その素数は一覧の外にある」ことだけです。1 より大きい整数が素数を約数にもつことは、素因数分解の存在として高校の整数で認められています。N が合成数でも、その素因数は必ず1個あり、その素因数について同じ議論ができます。

なぜ積に 1 を足す形を選ぶのかも、余りで説明できます。N = a₁a₂…aₙ + 1 を aᵢ で割ると、aᵢ を含む項はすべて割り切れて、余りだけが 1 として残ります。つまり N はどの aᵢ でも割り切れません。同じ理由で、積から 1 を引く形 N = a₁a₂…aₙ − 1 も使えます。このときの余りは aᵢ − 1 で、これも 0 ではありません。どちらの形でも、一覧の数が N の約数にならないように作るという目的は同じです。

図1は、仮定から矛盾までを四つの段階に分け、各段階で答案に書くことを対応させた表です。

図1のように、左の列が答案の段階、右の列がそこに書く内容です。段階を飛ばすと、作った数が一覧の外にあるという最後の根拠が抜けます。

ここで、この型が効く条件を四つに整理します。一覧が空でないこと、作った数が 1 より大きいこと、素因数が本当に素数であること、その素因数が一覧のどれとも異なることです。逆に、一覧を「条件を満たすものの一部」としてしか書いていない答案は、たとえ構成が正しくても矛盾になりません。仮定は「これで全部」でなければならないからです。

積に1を足した数は素数とは限らない

次の基本例題では、一覧を閉じてから外へ出る数を作り、矛盾までを四行で書きます。

基本例題（標準）

素数が有限個しかないと仮定して、矛盾を導いてください。

基本例題の解答

素数が p₁, p₂, …, pₙ の n 個だけだと仮定します。ここで

N = p₁p₂…pₙ + 1

とおきます。各 i について、N を pᵢ で割った余りを調べます。

N = pᵢ・(p₁…pᵢ₋₁pᵢ₊₁…pₙ) + 1

なので、N を pᵢ で割った余りは 1 です。余りが 0 ではないため、pᵢ は N を割り切りません。これはすべての i について成り立ちます。

次に N の大きさを見ます。p₁ は素数なので 2 以上です。したがって

N = p₁p₂…pₙ + 1 ≥ 2 + 1 = 3

となり、N は 1 より大きい整数です。1 より大きい整数は素因数を少なくとも1個もちます。その一つを q とします。

q は素数です。仮定によれば、素数は p₁, p₂, …, pₙ のどれかでなければなりません。しかし q は N を割り切るので、q が pᵢ のどれかであるとすると、pᵢ が N を割り切ることになります。これは先に確かめた「pᵢ は N を割り切らない」に反します。よって q は一覧のどれでもなく、仮定に反します。したがって、素数が有限個しかないという仮定は誤りです。

直接「素数は無限にある」と書き始めると、次々に素数を作る手順を延々と続ける説明になり、答案として閉じません。一覧を閉じてから外へ出る数を1個作れば足りるのは、仮定が「これで全部」という形をしているからです。否定した仮定が全称の形をしているほど、1個の反例で崩せます。

具体例で確かめます。p₁ から p₅ までを 2, 3, 5, 7, 11 とすると

N = 2・3・5・7・11 + 1 = 2311

です。2311 は 1 と 2311 以外に約数をもたない素数ですが、この事実は上の証明では使っていません。使ったのは、2311 が 1 より大きく、2, 3, 5, 7, 11 のどれでも割り切れないことだけです。

図2は、この例題の流れを一覧、構成、素因数の三点で示したものです。

図2のように、一覧の素数を掛けて 1 を足し、その数の素因数を取ります。2311 が素数かどうかは図にも答案にも登場しません。

仮定の一覧を狭めて作る三つの例

標準例題では、一覧を「すべての素数」から「n 以下の素数」へ狭めます。仮定の範囲が変わっても、外に出る整数を作る手順は同じです。

標準例題（標準）

n を 2 以上の整数とします。n より大きい素数が存在することを示してください。

標準例題の解答

n より大きい素数が存在しないと仮定します。このとき、素数はすべて n 以下です。n 以下の素数を小さい順に q₁, q₂, …, qₖ とします。n は 2 以上なので、2 はこの一覧に入っており、k は 1 以上です。ここで

N = q₁q₂…qₖ + 1

とおきます。各 i について N を qᵢ で割った余りは 1 なので、qᵢ は N を割り切れません。また N は 2 以上なので 1 より大きく、素因数 q を1個もちます。q は素数であり、qᵢ のどれでもありません。仮定によれば n 以下の素数がすべての素数なので、q も n 以下のはずです。しかし q は一覧のどれでもなく、一覧は n 以下の素数をすべて含んでいます。よって q は n 以下ではありません。これは仮定に反します。

n = 1 のときは、2 が 1 より大きい素数なので、一覧を持ち出すまでもありません。n が 2 以上のときに一覧が空でないことを確かめてから、積を作ります。一覧が空だと積の扱いが変わり、場合分けが増えるので、答案の冒頭で n の範囲を固定しておくのが安全です。

具体例として n = 10 を考えます。10 以下の素数は 2, 3, 5, 7 です。

N = 2・3・5・7 + 1 = 211

211 は素数で、10 より大きい数です。ここでも 211 が素数であることは証明の本筋ではなく、一覧の外の素因数が取れたことが本筋です。

この型と一つ目の型の違いは、仮定の書き方だけです。すべての素数を一覧にすると個数の有限性を否定でき、n 以下の素数を一覧にすると範囲の有限性を否定できます。答案の冒頭でどちらの一覧を閉じたのかをはっきり書くと、最後の矛盾の位置も決まります。

やや難例題（やや難）

4 で割って 3 余る素数が無限に存在することを示してください。

やや難例題の解答

4 で割って 3 余る素数が有限個しかないと仮定します。それらを p₁, p₂, …, pₙ とします。3 は 4 で割って 3 余る素数なので、この一覧は空ではありません。ここで

N = 4p₁p₂…pₙ - 1

とおきます。4 で割った余りを考えると

N ≡ 4p₁p₂…pₙ - 1 ≡ -1 ≡ 3 (mod 4)

です。また N は 4・3 − 1 = 11 以上なので 1 より大きく、素因数を1個もちます。

N は 4 で割って 3 余る奇数なので、N の素因数はすべて奇数です。奇素数は 4 で割った余りが 1 か 3 のどちらかです。もし素因数がすべて 4 で割って 1 余る素数なら、その積も 4 で割って 1 余り、N が 4 で割って 3 余ることに反します。よって N の素因数のうち少なくとも一つは、4 で割って 3 余る素数です。その一つを q とします。

q は N を割り切るので、q が一覧の pᵢ のどれかだとすると pᵢ が N を割り切ることになります。しかし N = 4p₁…pₙ − 1 を pᵢ で割った余りは -1、つまり pᵢ − 1 であり、0 ではありません。よって q は一覧のどれでもなく、仮定に反します。

具体例として、一覧を 3, 7, 11, 19 とします。

N = 4・3・7・11・19 - 1 = 17556 - 1 = 17555

17555 = 5・3511 で、3511 は 4 で割って 3 余る素数です。5 は 4 で割って 1 余るので、素因数の余りを分けて見る段階がここで効いています。

この問題で 4P + 1 ではなく 4P − 1 を使うのは、4P + 1 が 4 で割って 1 余る形になり、欲しい 3 余る素因数を保証できないからです。4P − 1 は 4 で割って 3 余るので、素因数の余りの場合分けで 3 余るものを1個取り出せます。作りたい数の形に合わせて、足すか引くかを選ぶ段階が、この型の二つ目の分かれ目です。

この例題で使った「素因数の余りを場合分けする」段階は、積に 1 を足すだけの型にはなかった追加の仕事です。作った数が一覧のどれでも割り切れないだけでは、一覧の外に欲しい形の素数があるとは限りません。欲しい形を素因数の余りで保証してから、一覧の外であることを使います。

なお、4 で割って 1 余る素数について同じ作り方をすると、N の素因数がすべて 4 で割って 1 余る可能性を排除できません。この形は本問の作り方では外に出られないので、別の道具が必要です。ここでは扱いません。

発展例題（難）

相異なる素因数を k 個もつ整数が存在するとします。このとき、相異なる素因数を k+1 個もつ整数も存在することを示してください。

発展例題の解答

相異なる素因数を k 個もつ整数を m とし、その素因数を q₁, q₂, …, qₖ とします。ここで

N = q₁q₂…qₖ + 1

とおきます。N を qᵢ で割った余りは 1 なので、qᵢ は N を割り切れません。N は 1 より大きいので素因数 r を1個もちます。r は素数で、どの qᵢ とも異なります。

このとき mN を考えます。m は q₁, q₂, …, qₖ のすべてを素因数にもち、N は r を素因数にもちます。r は qᵢ のどれとも異なるので、mN は q₁, q₂, …, qₖ, r の k+1 個の相異なる素因数をもちます。よって k+1 個の場合も存在します。

具体例で確かめます。m = 30 は 2, 3, 5 の三つの相異なる素因数をもちます。

N = 2・3・5 + 1 = 31

31 は素数で、2, 3, 5 のどれとも異なります。よって 30・31 = 930 は 2, 3, 5, 31 の四つの相異なる素因数をもちます。さらに

N = 2・3・5・31 + 1 = 931 = 7・7・19

で、931 は素数ではありませんが、7 と 19 という一覧の外の素因数をもちます。よって 930・931 は 2, 3, 5, 7, 19, 31 の六つの相異なる素因数をもちます。

この例題は、一覧の外の素因数を拾う操作をもう一度行うと、素因数の種類を1個ずつ増やせることを示しています。一度の構成で得られるのは1個だけですが、得られた整数を次の一覧に加えて同じ操作をすれば、種類の数は必ず増えます。閉じた一覧から外へ出る手順そのものが、次の一覧を作る材料になります。

この例題の 931 は、作った数が素数でなくても議論が進むことを具体的に示しています。素数であることを主張した瞬間に誤りになりますが、素因数を1個取るだけなら合成数でも困りません。一覧の外の素因数を拾う、という目的を最後まで保つことが大切です。

素数だと言い切った答案の直し方

誤答の実例です。ある答案は、素数が有限個しかないと仮定したうえで、次のように書きました。

N = 2・3・5・7・11・13 + 1 = 30031
30031 は 2, 3, 5, 7, 11, 13 のどれでも割り切れない。
よって 30031 は素数であり、一覧にない素数が見つかった。

この答案は結論だけを見ると当たっているように見えますが、途中の「よって 30031 は素数」が誤りです。実際に計算すると

30031 = 59・509

であり、30031 は合成数です。59 も 509 も 2, 3, 5, 7, 11, 13 のどれでもありません。つまり、一覧にない素数は確かにありますが、それは 30031 自身ではなく、30031 の素因数です。

原因は「一覧のどれでも割り切れない」から「素数である」への飛躍です。一覧にない素数で割れないことは、ほかの素数でも割れないことを意味しません。30031 は 59 で割り切れますが、59 は一覧に載っていないだけです。一覧の外の素数が存在することを示したいのに、その存在を「一覧のどれでも割れない」という一覧に依存した条件から引き出そうとした点が、論理のねじれです。

直し方は、主張を一段弱めます。「30031 の素因数 q を取ると、q は一覧のどれとも異なる」と書きます。これなら 30031 が素数でも合成数でも同じように成り立ちます。素数であることを言う必要はありません。

もう一つの誤りは、N が合成数だと矛盾が起きないと考えることです。矛盾を担うのは N の素数性ではなく、N の素因数が一覧の外にあるという事実です。N が合成数でも、その素因数は必ず1個あり、その素因数について一覧の外だと言えます。

「N は一覧のどの数よりも大きいので、一覧にない数である」という行だけを書く答案もあります。N が一覧にないこと自体は正しいのですが、N が素数とは限らないので、一覧にない素数を得たことにはなりません。大きさの比較は構成の確認であって、素因数の代わりにはなりません。一覧にないことと、素数であることを、別の行に分けて確かめます。

さらに、N が 1 より大きいことの確認を落とす誤りもあります。N = 1 や N = 0 では素因数を取れません。積に 1 を足す形では N が 3 以上になることを一行で確かめます。積から 1 を引く形では、一覧の数がすべて 1 のときに N = 0 になるので、この確認が特に重要です。

図3は、誤答が分かれる地点を示したものです。

図3のように、「一覧で割れない」から「素数」へ進む枝が誤答で、「素因数が一覧の外」へ進む枝が正しい道です。二つの枝は同じ出発点から分かれます。

練習問題

次の五問を解いてください。解答は五問の後にまとめて置きます。

練習1（標準）

a₁, a₂, …, aₙ を 1 より大きい整数とします。N = a₁a₂…aₙ − 1 が、a₁, a₂, …, aₙ のどれでも割り切れないことを示してください。

練習2（標準）

2・3・5・7・11・13・17 + 1 = 510511 を素因数分解し、2, 3, 5, 7, 11, 13, 17 のどれでもない素因数をすべて挙げてください。

練習3（やや難）

n を 2 以上の整数とします。n! + 1 が n 以下のどの素数でも割り切れないことを示し、これを用いて n より大きい素数が存在することを導いてください。

練習4（標準）

2 でも 3 でも割り切れない合成数を一つ挙げ、その素因数が 2 でも 3 でもないことを確かめてください。

練習5（やや難）

a, b を 2 以上の整数とします。N = ab + 1 の任意の素因数が、a とも b とも異なることを示してください。

練習の解答

練習1です。各 i について、a₁a₂…aₙ は aᵢ を因数にもつので aᵢ で割り切れます。したがって

N = aᵢ・(a₁…aᵢ₋₁aᵢ₊₁…aₙ) - 1

となり、N を aᵢ で割った余りは aᵢ − 1 です。aᵢ は 1 より大きい整数なので aᵢ − 1 は 0 ではなく、aᵢ は N を割り切りません。これがすべての i で成り立ちます。

練習2です。順に割っていくと

510511 = 19・26869
26869 = 97・277

なので、510511 = 19・97・277 です。19, 97, 277 はいずれも素数で、2, 3, 5, 7, 11, 13, 17 のどれとも異なります。確かめに、19・97・277 を計算すると 510511 に戻ります。割り算の側から見ると、510511 ÷ 19 = 26869、26869 ÷ 97 = 277 で、どちらの余りも 0 です。

練習3です。n 以下の素数を p とします。p は n! = 1・2・…・n の因数に入っているので、n! は p で割り切れます。よって n! + 1 を p で割った余りは 1 で、p は n! + 1 を割り切れません。次に、n! + 1 は 2 以上なので 1 より大きく、素因数 q を1個もちます。q は素数で、n 以下のどの素数とも異なります。n 以下の素数はすべて n 以下なので、q は n 以下ではありません。よって q は n より大きい素数です。n = 5 なら 5! + 1 = 121 = 11・11 で、11 は 5 より大きい素数です。2, 3, 5 のどれでも 121 は割り切れません。

練習4です。35 は 5・7 と分解でき、合成数です。35 を 2 で割った余りは 1、3 で割った余りは 2 なので、2 でも 3 でも割り切れません。素因数の 5 と 7 も、2 でも 3 でもありません。一覧の外の素数が、一覧の外の合成数を作っている例です。

練習5です。q を N = ab + 1 の素因数とします。q が a を割り切ると仮定すると、q は ab も割り切ります。一方で q は N を割り切るので、q は N − ab = 1 を割り切ることになります。1 を割り切る素数はないので、これは矛盾です。よって q は a と異なります。b についても同じ議論で q は b と異なります。なお ab + 1 は 2・2 + 1 = 5 以上なので 1 より大きく、素因数を必ずもちます。a = 4, b = 9 なら N = 37 で、素因数 37 は 4 とも 9 とも異なります。

覚えておくこと

• 有限個と仮定したら、一覧を答案の冒頭に書き切る。
• 一覧から外れる数は、積に 1 を足すか、積から 1 を引く形で作る。
• 作った数が 1 より大きいことを確かめ、素因数を1個取る。
• その素因数が一覧のどれとも異なることを示して、仮定と突き合わせる。
• 作った数自身が素数かどうかは、一度も使わない。

つまずきの見分け方

答案に「素数である」と書いた行があれば、その根拠が「一覧のどれでも割り切れない」だけになっていないかを見ます。この根拠だけでは合成数の場合を排除できません。次に、N が 1 より大きいことの確認があるかを見ます。最後に、一覧がすべてだという仮定が答案の冒頭に書かれているかを見ます。末尾に「矛盾」とだけ書いて、どの仮定とどの事実がぶつかったのかを書かない答案も、同じ型のつまずきです。

個別の確かめでは、生徒自身に 30031 を計算させ、59 と 509 に分けさせます。そのうえで「一覧にない素数はどれか」と問うと、答えは 30031 ではなく 59 と 509 になります。この一問で、主張の対象が N から N の素因数へ移ります。同じ確かめを 17555 でも行うと、素因数の余りを場合分けする段階も一緒に点検できます。

一覧の外の数を1個作る、その一手が答案を閉じます。