整数の解法パターン全18型｜型の見抜き方と入試実例（一橋大・神戸大・九州大・岡山大・千葉大）

01整数の正体は素因数の並び

顔つき　「\(\sqrt{24n}\) が整数となる最小の \(n\)」「\(n^{2}-20n+91\) が素数」。

中身　平方数 \(\Longleftrightarrow\) 素因数の指数がすべて偶数。素数 \(\Longleftrightarrow\) 約数が1と自分自身だけ。

なぜ効くか　素因数分解の一意性があるので、整数に関するほとんどの条件は「指数についての条件」に翻訳できるからです。「平方数である」も「\(k\) 乗数である」も「約数がいくつある」も、全部が指数の言葉になります。素因数分解は整数の設計図です。

手順　① 素因数分解する → ② 条件を指数の条件に書きかえる → ③ 指数を決める

隣の型との境界　「素数になる」条件は型06（積の形）とセットです。\(N=AB\) で \(N\) が素数なら、\(A\) か \(B\) が \(\pm 1\) しかありえません。

02指数の min と max で考える

顔つき　「最大公約数が15となる数の個数」「\(\gcd(a,b)=g\) とおく」。

中身　各素数について、最大公約数は指数の小さいほう、最小公倍数は大きいほう。したがって \(\gcd\times\mathrm{lcm}=ab\)。

なぜ効くか　「\(\gcd(n,225)=15\)」のような条件は、\(225=3^{2}5^{2}\) と分解して「\(n\) に3がちょうど1個、5がちょうど1個」と読みかえられます。集合の条件が指数の条件に変わるので、あとは数えるだけの作業になります（九州大学の実例）。

手順　① \(\gcd(a,b)=g\) なら \(a=ga\) とおいて \(\gcd(a\) を使う → ② 素数ごとに指数を比べる

03指数に1を足してかける／等比数列の積に開く

顔つき　「約数の個数が12個」「約数の総和を求めよ」「完全数」。

中身　\(N=p^{a}q^{b}\cdots\) のとき、約数の個数は \((a+1)(b+1)\cdots\)、総和は \((1+p+\cdots+p^{a})(1+q+\cdots+q^{b})\cdots\)。

なぜ効くか　約数を1つ決めることは「各素数の指数を \(0\) から \(a\) の中で1つ選ぶ」ことと1対1に対応するからです。個数の公式はこの対応そのもの。総和の公式は、その積を展開すると各項がちょうど1つの約数になることから出ます。公式を覚えるより、展開して確かめるほうが忘れません。

04数えて、足して、引く

顔つき　「1から1000までで3の倍数でも5の倍数でもない個数」。

中身　\(1\) から \(N\) までの \(k\) の倍数は \(\left\lfloor \dfrac{N}{k} \right\rfloor\) 個。「または」は包除原理で足して引く。

なぜ効くか　\(k\) の倍数は \(k\) おきに現れるので、個数はガウス記号1つで書けます。「割り切れない」は数えにくいので、数えやすい「割り切れる」を数えて全体から引く――これは確率の余事象とまったく同じ発想です。

05p の倍数、p² の倍数、… を段ごとに数える

顔つき　「\(100!\) は末尾に0が何個並ぶか」「\(n!\) が \(2^{k}\) で割り切れる最大の \(k\)」。

中身　\(n!\) に含まれる素数 \(p\) の個数は \(\left\lfloor \frac{n}{p} \right\rfloor+\left\lfloor \frac{n}{p^{2}} \right\rfloor+\left\lfloor \frac{n}{p^{3}} \right\rfloor+\cdots\)

なぜ足すのか　\(p\) の倍数を1回ずつ数え、\(p^{2}\) の倍数は「2個目の \(p\) 」をもう1回数え、\(p^{3}\) の倍数はさらにもう1回――というふうに、「2階建て・3階建ての分を上の段で追加する」と読むと自然です。1つの数の中に \(p\) が何個あるかを、階層ごとに数え上げているだけです。

06積の形にして、約数を全部あてはめる

顔つき　「\(xy+2x+3y=0\)」「\(\dfrac1x+\dfrac1y=\dfrac13\)」など、掛け算に持ちこめる式。

中身　\((x+a)(y+b)=c\) の形に整理し、\(c\) の約数の組をすべてあてはめる。負の約数を忘れない。

なぜ効くか　三方針の①そのものです。積が定数なら、片方は定数の約数に限られ、約数は有限個。整数問題で「積の形を作る」ことが最優先とされるのは、それだけで無限が有限に変わるからです。1つ足して1つ引くような無理やりな変形も、この目的のためなら正当化されます。

07整数解をもつなら実数解をもつ

顔つき　\(x^{2}+xy+y^{2}=13\) のように、2次で因数分解できない式。

中身　1文字について2次式と見て判別式 \(\geqq 0\) を使うか、平方完成して平方の和にする。どちらも範囲がしぼれる。

なぜ効くか　\(x\) が整数なら当然実数なので、\(x\) についての2次方程式が実数解をもつ必要があります。この必要条件が \(y\) の範囲を有限に切ってくれる。「整数である」という強い条件をいったん「実数である」という弱い条件に落として、範囲だけ取り出す――弱くすることで前に進める、という発想です。

手順　① 1文字について2次式に整理 → ② 判別式 \(\geqq 0\) または平方完成 → ③ 有限個の候補を代入

08大小を決めてから絞る

顔つき　「\(\dfrac1x+\dfrac1y+\dfrac1z=1\) をみたす自然数」。

中身　対称式なら \(x\leqq y\leqq z\) と仮定してよい。すると \(\dfrac1x\) がいちばん大きいので \(1\leqq \dfrac3x\)、つまり \(x\leqq 3\)。

なぜ大小を決めてよいのか　式が \(x,y,z\) について対称だからです。1つの解の並べかえも解になるので、代表として小さい順のものだけ調べ、最後に並べかえを戻せばよい。そして大小を決めた瞬間に「いちばん大きい項で全体を評価する」という不等式が作れる――ここが本当のねらいです。対称性は、範囲をしぼるための道具として使います。

09不等式で挟んで、候補を数え上げる

顔つき　「\(x^{2}+y^{2}=41\)」「和が一定で条件をみたす自然数の組」。

中身　\(y^{2}\geqq 0\) などから \(x\) の範囲を出し、そこにある整数を全部試す。

なぜ効くか　三方針の②です。整数はとびとびだから、範囲さえ切れれば「全部調べる」が正当な解法になります。実数の問題では「全部調べる」は使えません。ここが整数問題のいちばんの特徴で、しぼりこみさえ書ければ、あとは根気の作業です。答案では「範囲を出した式」を必ず明示してください。

隣の型との境界　しぼった候補がまだ多いときは、型10（合同式）で「そもそもありえない余り」を落とすと一気に減ります。

10余りだけを見て、巨大な数を扱う

顔つき　「\(2^{2017}\) を7で割った余り」「\(3^{n}+1\) が5で割り切れる \(n\)」。

中身　\(a\equiv b \pmod m\) の計算規則を使って、指数を周期で折りたたむ。

なぜ効くか　余りの世界は有限なので、\(a,a^{2},a^{3},\dots\) の余りは必ずどこかで繰り返します（有限個の値しかとれないので、いつか同じ値が現れる）。周期さえ見つかれば、指数を周期で割った余りだけを見ればよい。「無限の指数」が「周期の中の位置」という有限の情報に変わるのがこの型です。

手順　① \(a^{1},a^{2},a^{3},\dots\) の余りを順に計算 → ② 1に戻る（または繰り返す）ところを見つける → ③ 指数を周期で割る

11すべての整数を m 通りに分けて、全部確かめる

顔つき　「\(n^{2}\) を3で割った余りは0か1であることを示せ」「\(n\) がどんな整数でも…」。

中身　\(n=mk,\ mk+1,\ \dots,\ mk+(m-1)\) の \(m\) 通りに分け、それぞれで確かめる。

なぜ効くか　三方針の③です。「すべての整数について」という無限の主張が、\(m\) 個のケースを確かめるだけの有限の作業に変わります。どの \(m\) で分けるかは、問題文に出てくる割る数（3の倍数なら3、平方数なら4や8）で決まることがほとんどです。

12連続 k 個の積は k! で割り切れる

顔つき　「\(n^{3}-n\) は6の倍数」「\((p+1)(p+3)(p+5)\) は48の倍数」。

中身　連続する2整数の積は2の倍数、連続する3整数の積は6の倍数。一般に連続 \(k\) 個の積は \(k!\) の倍数。

なぜ成り立つのか　連続する \(k\) 個の中には、\(2\) の倍数がおよそ \(k/2\) 個、\(3\) の倍数がおよそ \(k/3\) 個…と必ず含まれるからです。もっと簡潔には、連続 \(k\) 個の積を \(k!\) で割ったものが二項係数 \({}_n\mathrm{C}_k\) になり、これは「選び方の個数」だから整数――という説明がいちばん短い。整数であることを、数え上げの意味から言うのは強力な手です。

手順　① 与式を因数分解して連続整数の積を作る → ② 2の指数と3の指数を別々に数える

13大きいほうを小さいほうで割って置きかえる

顔つき　「\(\gcd(2017,225)\) を求めよ」「\(\gcd(n,n+3)\) を求めよ」。

中身　\(a=bq+r\) のとき \(\gcd(a,b)=\gcd(b,r)\)。余りが0になるまで繰り返す。

なぜ公約数が保たれるのか　\(d\) が \(a\) と \(b\) の公約数なら \(r=a-bq\) も \(d\) で割り切れ、逆に \(d\) が \(b\) と \(r\) の公約数なら \(a=bq+r\) も割り切れるからです。公約数の集合そのものが等しいので、最大のものも等しい。この「公約数は引き算で生き残る」という性質が、\(\gcd(n,n+3)=\gcd(n,3)\) のような文字式の計算にもそのまま使えます。

14特殊解を1つ見つけ、差をとる

顔つき　「\(7x+11y=1\) の整数解をすべて求めよ」。

中身　解が存在する条件は \(\gcd(a,b)\mid c\)。特殊解 \((x_0,y_0)\) を1つ見つけ、辺々引いて \(a(x-x_0)=-b(y-y_0)\) から一般解を出す。

なぜ解が等差数列になるのか　\(\gcd(a,b)=1\) のとき \(a(x-x_0)=-b(y-y_0)\) の左辺は \(a\) の倍数、右辺は \(b\) の倍数。互いに素なので両辺は \(ab\) の倍数となり、\(x-x_0=bk\) と書けます。「互いに素な2数が等式の両辺にある」ときは、必ず片方が他方の倍数になる――これは整数分野で最も出番の多い論法の一つです。

手順　① 互除法を逆にたどって特殊解を作る → ② 一般解との差をとる → ③ 互いに素を使って \(k\) を導入

152つの余り条件から、元の数を復元する

顔つき　「3で割ると2余り、5で割ると3余る数」。

中身　\(n=3k+2\) とおいて第2の条件に代入し、型14に持ちこむ。法が互いに素なら、答えは \(\pmod{15}\) で一意に決まる。

なぜ一意に決まるのか　\(0\) から \(14\) までの15個の数に対して「3で割った余り」と「5で割った余り」の組を作ると、15通りの組がすべて1回ずつ現れるからです（同じ組になる2数があれば差が3でも5でも割り切れ、15の倍数になって矛盾）。個数が等しい2つの集合の間に単射があれば全単射――数え上げの論法が、そのまま整数の定理になっています。

16有理数と仮定して、既約分数の矛盾を出す

顔つき　「\(\sqrt2\) が無理数であることを示せ」「\(a+b\sqrt2=0\) ならば \(a=b=0\)」。

中身　\(\dfrac{q}{p}\)（既約）とおいて素因数の指数を比べ、矛盾を導く。

なぜ背理法なのか　「無理数である」は「有理数でない」という否定形の主張で、直接示す足場がありません。否定形の主張は、否定して肯定形に変えると手がかりが生まれる――これが背理法を選ぶ理由です。仮定した瞬間に「既約分数」という具体的な形が手に入り、素因数分解（型01）が使えるようになります。

17位取りは、n のべきの和で書くこと

顔つき　「\(100\) を3進法で表せ」「\(n\) 進法で3桁になる条件」。

中身　\(N=a_k n^{k}+\cdots+a_1 n+a_0\)（\(0\leqq a_i\leqq n-1\)）。桁数の条件は \(n^{k}\leqq N\lt n^{k+1}\)。

なぜ表し方が一通りなのか　各位の数が \(0\) から \(n-1\) に制限されているからです。もし制限がなければ、繰り上がりの自由度で何通りにも書けてしまいます。「制限つきの表し方は一意」というのが位取り記数法の核心で、この一意性があるから桁ごとの比較が使えます。

18不等式に直してから扱う

顔つき　「\([x]\) を \(x\) 以下の最大の整数とする」。

中身　\([x]=n \iff n\leqq x\lt n+1\)。等式のままでは扱えないので、必ず不等式に直す。

なぜ不等式に直すのか　ガウス記号は関数としては段々になっていて、代数計算の規則（\([x+y]=[x]+[y]\) など）が成り立たないからです。成り立たない規則を使わないためには、定義そのものである不等式に戻すしかない。\(x-1\lt [x]\leqq x\) の形も覚えておくと、はさみうちに持ちこめます。