整数の証明の解法パターン全12型｜型の見抜き方と入試実例（東京都立大・九州大・神戸大・金沢大・島根大・千葉大）

整数の証明は、計算力だけでは押し切れない、ほとんど唯一の分野です。「6の倍数であることを示せ」「整数にならないことを示せ」——どれも求めるべき数値がどこにも無いので、手を動かしても終わりが見えません。それでも整数の証明が必ず解けるようになるのは、使える性質が三つしかないからです。整数はとびとびにしか存在しない。ここから「余りで分類すれば有限個で済む」「素因数の個数は動かせない」「正の整数は無限に小さくなれない」の三つが出てきて、入試の整数証明はほぼ全部このどれかで決着します。このページは整数の証明を12の型に分けた辞典です。型は当てはめるための箱ではなく、「いま自分はどの性質で勝負しにいくのか」を見失わないための道具として並べています。

1. 背骨——整数の証明は「動かせない量」を探す作業である

整数の証明は、テーマがばらばらに見えるのに、答案の骨格だけはいつも似ています。理由はたった一つ、整数がとびとびにしか存在しないからです。実数なら と のあいだにいくらでも数がありますが、整数にはひとつもない。この当たり前すぎる事実から証明に使える性質が三つ出てきて、入試の整数証明はその外側にほとんど出ません。

①がなぜ強いのかは、「すべての自然数 で は6の倍数」を考えると分かります。 は無限にあるのに、確かめるべきことは有限個しかない。 を6で割った余りで6通りに分ければ、計算するだけで終わります。あるいは と因数分解すれば、連続3整数のどれかが必ず3の倍数、どれかが必ず偶数——これも「余りが一巡する」という①の言い換えです。無限を有限に押し込める。整数の証明で最初に探すべきは、この押し込め方です。

②は、もっと決定的です。 と書けたなら の中に はちょうど2個、 はちょうど1個で、この個数は誰が計算しても変わりません。変わらない量、すなわち不変量です。 が無理数であることの証明も根っこは同じで、 の両辺で の個数を数えると左辺は偶数個・右辺は奇数個。偶数は奇数になれない、それだけの話です。

③は、答案では「最小のものをとる」という言い回しで現れます。帰納法は下から積み上げ、降下法は上から落として底にぶつける。底があるからこそ、どちらも成立します。

この三つは、見た目こそ違いますが、やっていることは同じです。「どうやっても動かせない量」を一つ作り、その量が両側で食い違うことを見せる。整数の証明とは問題ごとに「どの不変量で勝負するか」を選ぶ競技だと考えると、型の並びが一気に見通せるようになります。

もう一つ、整数の証明には「〜でない」という否定形が異様に多いという特徴があります。素数でない、整数にならない、有理数でない、解が存在しない。否定形は直接示しにくいので、結論を否定して矛盾を出す（背理法）か対偶に言い換えるのが定石です。そして矛盾の作り方は結局さきほどの三つ——偶奇や余りの食い違い（①）、素因数の個数の食い違い（②）、正の整数がそれ以上小さくなれないのに小さくなる（③）——に戻ってきます。「何を仮定して、どの食い違いを狙うか」を最初に決めてから書き始める——これだけで、答案の見通しはまったく変わります。

最後に、型そのものについて一言だけ。整数の問題を見た瞬間に「余りで分ける」「積の形にする」と手が動く人は、頭の回転が速いわけではありません。過去に何百回も使われてきた「型」から予想して、思考する量を減らすことで、手際よく解法を思い付いている場合もあるのです。型は考えなくて済ませるための道具ではなく、考える範囲を狭めるための道具です。狭めたあとに何を考えるかは、その問題ごとに自分で決めることになります。以下の12型も、そのつもりで読んでください。

2. 手順——証明を書き始めるまでの判断の流れ

3. 解法パターン全12型

型01　倍数の証明（連続整数の積）

型02　互いに素の証明

型03　最大公約数・最小公倍数

型04　素因数分解の一意性

型05　素数であることの証明

型06　無理数であることの証明

型07　有理数解をもたないことの証明

型08　数学的帰納法（整数版）

型09　無限降下法

型10　存在しないことの証明

型11　すべての n で成り立つことの証明

型12　反例を挙げる

4. 実際の入試で確かめる

ここからは実際の入試問題で型を確かめます。問題文は各大学が公表した入試問題を、解説のために引用したものです。解答・解説は数強塾が独自に作成したもので、大学公表の解答ではありません。掲載した数値は当塾で独立に解いたうえで Python で検算し、別の担当者が別ルートで解き直して照合しています。6題は易しい順に並べました。

東京都立大学 2019年度　――　型04・型05。約数を「積の形」で数え上げる

(1)　まず です。31 は なので 2, 3, 5 で割り切れるかだけ調べれば足り、いずれでも割り切れないので素数。よって 496 の素因数分解は で、これ以外の書き方はありません（素因数分解の一意性）。したがって 496 の正の約数は

の形に限られ、書き下すと の10個。その総和 は、次の積を展開するとこの10個が過不足なく現れることから

よって 496 以外の約数の総和は となり、496 に等しい。ゆえに 496 は完全数です。（証明終）

(2)　 とおきます。 より であり、 は奇数。仮定より は素数なので、 は 2 とは異なる素数です（この一行が後で効きます）。 とおくと、これがそのまま の素因数分解であり、 なので は2以上の自然数です。

このとき の正の約数は

の 個に限られます。実際 は奇素数なので はどれも で割り切れず、 はどれも割り切れるので、この 個は相異なります。よって総和 は

ここで等比数列の和より 、また ですから

したがって 以外の約数の総和は となり、 は完全数です。（証明終）

二つの小問の関係。じつは (1) は (2) の の場合そのものです（ は素数、）。同様に は を与えます。そして「 が素数」という仮定は外せません。 のとき は合成数で、 の 以外の約数の総和は 240——120 とは一致しません。

九州大学 2017年度　――　型06・型10。同じ面積を2通りに書くと、有理と無理がぶつかる

(1)　 より 、。正三角形になる条件は かつ 、すなわち

②を展開すると 。①を代入して 、すなわち 。 を①に入れると なので

(2)　背理法で示します。 が有理数だと仮定すると、互いに素な自然数 を用いて と書けます。両辺を2乗して分母を払うと

よって は3の倍数。ここで「 が3の倍数でなければ も3の倍数でない」ことを示します。実際 が3の倍数でなければ と書け、 となって3で割った余りは1です。したがって は3の倍数で、（ は自然数）とおけます。代入すると 、すなわち 。同じ議論から も3の倍数。ゆえに はともに3の倍数となり、互いに素であることに矛盾します。よって は無理数です。（証明終）

(3)　 は正三角形なので、1辺の長さを とすると であり、面積は

一方、 の面積公式から

2つを等しいとおいて

ここで結論を否定し、 がともに有理数であると仮定します。 は有理数なので、③の左辺 は有理数です。他方 とおくと は有理数で、 は実数だから 、すなわち 。③は と書けるので

右辺は（有理数）÷（0でない有理数）なので有理数。これは (2) で示した「 は無理数」に矛盾します。よって がともに有理数であることはあり得ず、 と のうち少なくとも1つは無理数です。（証明終）

神戸大学 2014年度　――　型05・型01・型11。素数が積で書けたら、片方は

(1)　そのまま展開します。

（証明終）　なお より 、、 なので3辺は正で、 を斜辺とする直角三角形です。

(2)　(1) より直角三角形なので、面積は直角をはさむ2辺から

一方、内接円の半径と3辺には の関係があり

よって

(3)　ここからが整数の話です。 と はともに自然数で、その積 が素数。素数は「1と自分自身の積」としてしか自然数2つの積に分解できませんから

または

の2通りに限られます。

(i) のとき で

(ii) のとき で

いずれも より をみたすので、両方とも実際に起こり得ます。よって または 。（例： なら (i) は3辺 8, 6, 10 で 、(ii) は3辺 5, 12, 13 で 。）

(4)　(3) の2つの場合それぞれで示します。

(i) のとき。これは連続する3整数の積です。連続2整数を含むので2の倍数、連続3整数の中には必ず3の倍数が1つあるので3の倍数。2と3は互いに素だから は6の倍数。

(ii) のとき。2で割り切れることは、 が連続2整数なのでどちらかが偶数、より従います。3で割り切れることは を3で割った余りで分けます。

いずれの場合も3つの因数のどれかが3の倍数です。2と3は互いに素なので は6の倍数。

よって が素数のとき、いずれの場合も は6で割り切れます。（証明終）　なお (ii) は が整数であることからも分かります。

金沢大学 2017年度　――　型04・型08。「分子に があるから」では減点される

(1)　実際に計算します。

順に なので、6個すべて7の倍数です。（証明終）　有限個なら全部書き出す——これも立派な証明で、遠慮する必要はありません。

(2)　定義から 、すなわち

という整数の等式が成り立ちます。右辺は の倍数です。一方 のとき も も より小さい自然数だけの積なので、素数 はそのどの因数も割らず、素数の性質（型04）より積も割りません。すなわち

したがって左辺が の倍数であるためには が の倍数でなければなりません。（証明終）

(3)　 のとき で7の倍数です。 のとき成り立つ、すなわち整数 を用いて と書けると仮定します。二項定理より

ですから

第2項の係数 は (1) よりすべて7の倍数なので、右辺全体が7の倍数——すなわち 。

よって でも成り立ち、すべての自然数 で は7の倍数です。（証明終）

島根大学 2011年度　――　型05・型12。数え上げて式にし、対偶で潰す

(2)　 は に含まれる素因数2の個数です。 のうち偶数は 個あり、 と書けます。奇数は素因数2をもたないので、奇数だけの積を とおくと

両辺の素因数2の個数を比べて、 のとき 。また より 。この漸化式を繰り返すと

(1)　(2) に を代入して 。直接確かめるなら、 に含まれる2の個数は

(3)　(2) より示すべきことは「 が素数ならば は素数」。対偶「 が素数でなければ は素数でない」を示します。 が素数でないのは次の2つの場合です。

(i) のとき。 で、1は素数ではありません。

(ii) が合成数のとき。（ は2以上の整数）と書けます。恒等式 に を代入して

第1因子は より 。第2因子は より項が2個以上あって 。よって は1より大きい2つの整数の積なので素数ではありません。

(i)(ii) より対偶が示されたので、 が素数ならば も素数です。（証明終）

逆は成り立ちません。 は素数ですが は素数ではありません。反例が一つあれば逆は崩れる——これが型12です。

千葉大学 2014年度　――　型10・型04。ただ1つだけ性質の違う項が、勝負を決める

(1)　 とおくと です。

ステップ1（ただ1つ）。 で となるのは だけです。実際 なら （ は奇数）と書け、 だと となって不適だから 。また なら で不適。よって である はすべて です。

ステップ2（通分）。 のときは 、 で 。以下 （このとき ）とします。 なる各 を （ は奇数、）と書き、 とおくと、奇数の最小公倍数だから は奇数で、各 は の約数です。よってある整数 を用いて

と書けます。したがって

は奇数、 は偶数なので は奇数。そこで とおけば、ともに奇数で 。（証明終）　例：、。

(2)　 なら 。 が整数 に等しいと仮定すると (1) より となり、右辺は より偶数、左辺 は奇数。奇数が偶数に等しくなることはあり得ません。よって は整数になりません。（証明終）

(3)　 とおきます。

ステップ1。 だから がともに区間に入り、その一方は偶数。よって 。

ステップ2（ここを自分で証明し直すのが本問の核心）。 となる は区間内にちょうど1つです。もし の2つがあったとし、（ は奇数、）と書くと、奇数どうしで だから 、よって となり も区間に属します。ところが は偶数なので となり、 が最大であることに矛盾。よってちょうど1つで、それを （ は奇数）とします。

ステップ3（通分）。 なる区間内の は なので、(1) と同じく （奇数）をとると、ある整数 で 。さらに とおくと は奇数で、 はどちらも奇数どうしの商だから奇数（とくに整数）です。よって

分子は「奇数 偶数」なので奇数。これを とおけば （ は奇数、）。

ステップ4。 が整数 に等しいとすると となり、左辺は奇数・右辺は偶数で矛盾。よってどんな に対しても は整数になりません。（証明終）　例：、。

5. よくある質問

6. 次に読むページ

• 整数の解法パターン全18型　――　このページの親。約数の個数から 進法まで単元全体を概観できます。
• 合同式と余りの解法パターン全14型　――　型01・型11の主戦場。余りの計算を記号で軽くする方法。
• 不定方程式の解法パターン全14型　――　型02・型09の詳細。積の形にする、範囲をしぼる。
• 集合と論理の解法パターン全12型　――　背理法・対偶・反例という、このページの土台。
• 数列・漸化式の解法パターン全16型　――　型08の詳細。数学的帰納法の書き方。
• 解法パターン事典（総索引）