苦手はここで克服しよう。整数問題は絞り込みで攻略せよ!

整数問題は難しい……。

しかし 残念ながら、整数問題は大学入試でも頻出分野です。
加えて、教科書レベルの問題を通りいっぺんさらうだけでは、実は入試レベルに対して太刀打ちできないのです。

今回は、入試レベルの整数問題に対して白紙解答を絶対に避け、突破口を開くために役立つ「絞り込み」の思考法を紹介します。

整数問題はどうして難しいの?

ではどうして整数問題は難しいと感じてしまうのでしょうか?
その理由の1つとして、答えにたどり着くまでの道筋が一見遠く見えるからです。

問題をただ眺めるだけでは用いるべき解法が分からないので、自身のストックした解法からひとつひとつ試していかなければなりません。
いろいろ試して、答えの値に目処を立ててやると、途方もないように見えた解答までの道が一挙に開けてきます。

実際、整数問題は小難しいことが書いてある割に、答えの値はシンプルであることが多いですよね。

整数問題は「絞り込み」を使おう!

「絞り込み」とはずばり、答えの値のとりうる範囲を絞ることです。

一見大したことではなさそうですが、これがほとんどの整数問題に有用な技で、かつ意外と見過ごされがち。
特に、難関大の試験でもっとも頻出の「◯◯という式を満たす整数◇の値を求めよ」といった類の問題を解く際には、ほとんど必須の考え方といえます。

そこで今回は、特に重要な「絞り込み」の技をいくつか伝授します!
  

整数問題の「絞り込み」の4定石

①代入して推測する

整数の問題をキレイに解こうと思ってはいけません。

求める\(n\)や\(x\)に\(1,2,3…\)と代入し、結果の様子を調べてみましょう。
すると大抵、すぐに傾向が見えてきます。

例えば\(n=3\)しかありえない、といった感じですね。
そうしたら答えが\(n=3\)であると見定めたうえで、それを論証していくという形をとる。

結論を推測してから論証する、というのが整数問題を解くさいの基本の流れです。覚えておきましょう。

②対称式を用いる

\( x+y+z=xyz\)を満たす整数の組\((x,y,z)\)を求めよ。

こういった問題で対称式の考え方を呼び出せるようにしましょう。
対称式とは式に含まれる変数をそれぞれ入れ替えても値が同じになるような式のことです。

\(x+y+z=xyz\)の各辺について、\(x\)を\(y\)、\(y\)を\(z\)、\(z\)を\(x\)に入れ替えても値が同じになるはず。
そんな場合、\(x,y,z\)の大小関係を自分で設けることができます。\(x<y<z\)といった風に。

そうすると\(xyz=x+y+z<z+z+z=3z\)となり、\(xyz=3z\)、つまり\(xy=3\)となって\(x,y\)の条件を絞ることができます。
 

③余りで場合分けする

「困難は分割せよ」というのはデカルトの言葉ですが、解法を絞り込んでいくのに有用なのが分割、つまり場合分けです。

「答えとなる\(n\)は\(3\)の倍数でしかありえないかも」などと推測を立てたうえで、\(n\)を\(3\)で割った余り\((0,1,2)\)で場合分けし、それぞれについて条件を満たすか検証していくといった風に行います。
無数にある整数が、「\(3\)で割った余り」というカテゴリーで分類することで、たった\(3\)グループ(余り\(0\)、余り\(1\)、余り\(2\))に分割することができるのです!

また、特別に覚えておいてほしいことを2つ。偶数・奇数の分類が特に便利であること、偶数の素数は2しかないこと、の2つです。
素数・倍数系の問題で頻出なので知っておきましょう。

④積の形を利用する(因数分解する)

一般に、和の形よりも積の形の方が整数問題として扱いやすいと心に留めておいてください。

なぜそうなるか、実際に試してみましょう。
\(x+y=5\)を満たす整数の組\((x,y)\)は\((-1,6)(10,-5)…\)などと無数にあります。
他方、\(xy=5\)を満たす整数の組\((x,y)\)は\((1,5)(5,1)(-1,-5)(-5,-1)\)の4組しかありません。

ある数をふたつの整数の和算で表すにはいくらでも仕方がありますが、乗算で表すとなると、ある数の素因数を使うしかなく、一気に候補が絞られてくるのですね。
与えられた式が因数分解できそうであればとりあえずしてみる。すると無数にありそうな答えが一気に絞られることがしばしばあります。

最難関大の入試問題にチャレンジ!

ここまでお伝えしたことを踏まえれば、難関大の入試問題であっても太刀打ちができます!
それでは見ていくことにしましょう

<第1問>

問題

素数\(p,q\)を用いて\(p^q+q^p\)と表される素数をすべて求めよ。
(京都大学・2016年度理系第2問)

解説

【step1】まずは試して突破口を開く!

式を眺めるだけでは少しも前に進みません。そんなときは定石①に則り、代入して試してみましょう!
\( p=2,q=2\)のとき、\(p^q+q^p=2^2+2^2=8\)となって素数になりませんね。

ここで気づいてほしいのは、\(p^q\)と\(q^p\)がともに偶数だと、\(p^q+q^p\)は\(2\)より大きい偶数になること。

偶数の素数は\(2\)しかないので、偶数である\(p^q+q^p\)は素数にならないのです。
\(p^q\)と\(q^p\)がともに奇数である場合も同様に、\(p^q+q^p\)が素数にならない。
とすると\(p^q,q^p\)の一方が奇数、他方が偶数なのですが、定石②から、\(p^q+q^p\)は対称式なので、\(p^q\)が偶数であるととりあえず絞ってしまってOK。

\(p^q\)が偶数だとして、もし\(p\)が奇数だと、何個\(p\)をかけても\(p^q\)は偶数になりません。
だから素数\(p\)は偶数とわかるのですが、偶数の素数は\(2\)しかないので、\(p=2\)しかありえません。

以上により、\(p\)をただひとつの値に絞ることに成功しました。

【step2】試す、推測、論証の流れをつかむ!

いまや\(p=2\)とわかったので、『\(2\)でない素数\(q\)を用いて\(2^q+q^2\)と表される素数をすべて求めよ』という問題になりました。
突破口を開くために、定石①:代入して推測を用いて、色々と代入してみましょう。

\(q=3\)のときは\(2^3+3^2=17\)。素数ですね。
\(17\)が答えのひとつとわかりました。

他に答えはあるのでしょうか?
\(q=5\)のときは\(2^5+5^2=57\)。素数ではありません。
\(q=7\)のときは\(2^7+7^2=177\)。こちらも素数ではありません。
\(q=11\)のとき\(2^11+11^2=2169\)。これも素数ではありません。

このあたりで「もしかして、\(q=3\)のときしか素数にならないのか? 答えは\(17\)しかない?」と推測がつくと素晴らしいです。
今まで求めた\(57,177,2169\)がいずれも\(3\)の倍数であることにも気づけるとなお良いですね。

もしこの推測を立証できれば、文句なしの解答です。
証明すべき事柄は『\(q\)が\(5\)以上の素数であるとき、\(2^q+q^2\)は素数でなく\(3\)の倍数である』となりました。

【step3】場合分けで全ての整数を把握する!

「◯の倍数であることを示せ」ときたら定石③:\(q\)を\(3\)で割った余りに関する場合分けを行います。

自然数\(n\)を用いると、全ての整数は\(3n,3n+1,3n-1\)でしか表されません。
\(q\)は\(5\)以上の素数ということは\(3\)で割り切れませんから、\(q\)は\(3n\)ではないことがわかります。

ゆえに\(q\)は\(3n+1\)か\(3n-1\)のどれかで表されます。
途方もなかった\(q\)が、余りによる絞り込みでたった2つの場合に絞られました! 

あとは\(q=3n+1,q=3n-1\)をそれぞれ\(2^q+q^2\)に代入し、\(3\)で割り切れることを確かめれば証明終了です。
ここまでくると、合同式を用いた教科書レベルの問題です。

以上により、素数\(p,q\)を用いて\(p^q+q^p\)と表される素数は\(17\)しかないと導かれます。
後はぜひ自分で手を動かして解いてみてください!

 今回用いた手法は全て先ほど解説した定石からなっています。
どこから手をつけたら良いかわからない整数問題も、今回の定石を用いたら十分に戦えるということです。

<第2問>

問題

\(3\)以上\(9999\)以下の奇数\(a\)で、\(a^2-a\)が\(10000\)で割り切れるものをすべて求めよ。
(東京大学・2005年度文系第2問&理系第4問共通)

解説

定石を用いることに慣れている人とそうでない人とでは印象が異なる問題で、後者の人は特に迷うことなく定石を当てはめていけると思います。
その境地を目標にやっていきましょう。

【step1】問題文を数式に翻訳する!

これからの解答には数式ベースで考えることが必須です。

「\(3\)以上\(9999\)以下の奇数\(a\)で、\(a^2-a\)が\(10000\)で割り切れるもの」という問題文を、即座に数式化できるようになりましょう。
数式化すると「\(a(a-1)=(2^4)(5^4)k\)(\(k\)は整数)を満たす\(a\)(\(3≦a≦9999,a\)は奇数)」となります。

\(a^2-a\)を\(a(a-1)\)、\(10000\)を\((2^4)(5^4)\)としたのは定石④:積の形の利用によっています。
この先どのような論理展開が待ち受けているかは不明ですが、とりあえず積の形にすると利益があるという経験からなる定石に、今は頼っておきましょう。

ここからは\(a\)や\(k\)の値を絞りこんでいくことを考えます。
\(a\)や\(k\)に何か代入して試してみても、どうもうまくいきません。

ここで注目するのは、\(a(a-1)\)が連続する2整数の積だということ。
「連続する2整数」というのはかなり強力な「絞りこみ」を導ける条件なので、ちょっとした定石として次に紹介する方法を覚えておきましょう。

【step2】「連続する2整数」から\(a\)を限定する!

連続する2整数は互いに素という性質は頻出!!

\(2\)の倍数は2個おき、\(3\)の倍数は3個おきに登場するので、連続する2整数がともに\(2\)や\(3\)の倍数であることはありません。
さて、\(a(a-1)=(2^4)(5^4)k\)の右辺は\(2^4\)と\(5^4\)を因数に含むので、\(a(a-1)\)も\(2^4\)と\(5^4\)を因数に含みます。

\(a\)は奇数なので、因数\(2^4\)を含むことはありえないですね。
\(2^4\)は\(a-1\)に含まれます。では、\(a\)が\(5^3\)を、\(a-1\)が\(2^4\)と残りの\(5\)を含むことはあるでしょうか。
これはありえませんね。これでは\(a\)と\(a-1\)がともに\(5\)で割り切れ、連続する2整数は互いに素という条件に合わないからです。

ゆえに、\(a-1\)だけが\(2^4\)を含み、\(a\)と\(a-1\)の一方だけが\(5^4\)を含むことがわかります。
では\(a-1\)が\(2^4\)と\(5^4\)をともに含んでもよいかというと、これもダメです。

\(2^4\)と\(5^4\)をともに因数に含む整数は、\(10000\)の倍数です。
しかし、\(3≦a≦9999\)において\(10000\)の倍数である\(a-1\)は存在しません。

【step3】積の形で絞り込む!

以上により、\(a\)について次のように条件を絞りこめました。
「\(a\)だけが\(5^4\)を因数に含み、\(a-1\)だけが\(2^4\)を因数に含む」言い換えると、\(a\)が\(625\)の倍数で、\(a-1\)が\(16\)の倍数なのです。
これも数式化して、\(a=625m\),\(a-1=16n\)(\(m,n\)は整数)とします。
重要なことは、新しい文字を設けて数式化することに慣れましょう、ということです。

さて、\(a=625m\),\(a-1=16n\)の2式からは\(a\)を消去して\(625m-16n=1\)という式が導かれます。
これはただの不定方程式であり、教科書レベルです。

\(a=625m\)を\(3≦a≦9999\)に代入すると、\(3≦625m≦9999\)、\(m\)は整数なので\(1≦m≦15\)という\(m\)の条件が出ます。
以上の不定方程式を、ぜひ自分で手を動かして解いてみてください。

すると解は\((m,n)=(1,39)\)しかないことがわかると思います。
よって、求める\(a(=625m)\)の値は、\(m=1\)の場合、すなわち\(a=625\)しかないと結論することができました。

今回のポイントは積の形の利用に尽きます。積の形にすると、今回のように倍数や素因数の考え方を導きやすくなるのです。

整数問題の攻略法まとめ

いかがでしたか?

完全にパターン化できないところに整数問題の難しさがあります。
ですが、本記事で紹介したように、突破口の開き方にはある程度の定石があります。

まずは絞り込みからマスターして、整数問題をぜひ得意分野に変えていきましょう!