入試整数入門 第2講

整数問題の解き方

前回は合同式と一次不定方程式について話しました。これらは整数問題を解くための"道具"です。今回からは実際の整数問題を解くための方法を伝授します。実は、整数問題には3つの解き方のパターンがあります。その3つとは

因数分解を試みる

不等式評価をする

倍数・あまりに着目する(合同式)

です。(超大事)
今回は一つ目、「因数分解を試みる」について解説します。

因数分解を試みる

因数分解って言っても、それの何がおいしいのでしょうか。確かに、経験的に積の形の方が制約が強くて解を絞りやすいという感覚があるでしょう。まあ、百聞は一見に如かずということで実際に問題を見てみましょう。

左辺が因数分解できる形であるということが一瞬で見抜けるでしょう。実際に因数分解を実行すると
$(a+b)(a-b)=4$
となります。ここで$a+b$は正の整数であるため、
$(a+b,a-b)=(1,4),(2,2),(4,1)$
とわかります。それぞれの場合で$(a,b)$は
$(\dfrac{5}{2},-\dfrac{3}{2}),(2,0),(\dfrac{5}{2},\dfrac{3}{2})$
となり、唯一の解として$(2,0)$が求まります。

※ $a+b-(a-b)=2b\equiv0\pmod{2}$
なので
$a+b\equiv a-b\pmod{2}$
です。つまり、
$(a+b,a-b)=(1,4),(4,1)$
からは整数解が得られません。
$a+b$と$a-b$の偶奇が等しいということは頭の片隅においておくとよいでしょう。

これは非常に簡単な例です。次も見てみましょう。

あれ、左辺が因数分解できない、、、。困った。
なんてことはありません。先ほどの例からわかる通り、因数分解さえできてしまえば定数項は何でもいい！のです。すると、左辺は
$(2x-3)(y-\dfrac{1}{2})-\dfrac{3}{2}$
になるので元の方程式は
$(2x-3)(y-\dfrac{1}{2})-\dfrac{3}{2}=11$
両辺$2$倍して
$(2x-3)(2y-1)=25$
先ほどと同様に
$(2x-3,2y-1)=(1,25),(5,5),(25,1),(-1,-25),(-5,-5),(-25,-1)$
となり(負の場合を忘れないようにしましょう)、それぞれの場合について
$(x,y)=(2,13),(4,3),(14,1),(1,-12),(-1,-2),(-11,0)$
と解が求まります。
慣れてきたら同じことですが、
$2xy-x-3y=11$
$\Leftrightarrow 4xy-2x-6y=22$
$\Leftrightarrow(2x-3)(2y-1)=25$
という風に初めから$2$倍しておいてもいいです。
とにかく、因数分解された式=(定数)になったらほぼ勝ち確です。
ちょっとレベルを上げましょう。

一橋だからって名前負けしてはいけません。
場合分けしなくても解けますが、ここではわかりやすいように場合分けして解きます。
まず、絶対値の中身が正の時、つまり
$x<\dfrac{7-3\sqrt{5}}{2},\dfrac{7+3\sqrt{5}}{2}< x$
の時を考えます。$x$は整数なので$x\le0,7\le x$となります。この時、
$x^2-7x+1=y^2 $
$\Leftrightarrow (x-\dfrac{7}{2})^2-y^2=\dfrac{45}{4} $
$ \Leftrightarrow (2x-7)^2-(2y)^2=45 $
$\Leftrightarrow (2x+2y-7)(2x-2y-7)=45$
$y>0$より$2x+2y-7>2x-2y-7$なので
$(2x+2y-7,2x-2y-7)=(45,1),(15,3),(9,5),(-1,-45),(-3,-15),(-5,-9)$
$6$回も連立方程式を解くのは大変ですが、
$y=\dfrac{2x+2y-7-(2x-2y-7)}{4}$
なので、それぞれの場合の$y$は$11,3,1,11,3,1$となります。同様に、
$x=\dfrac{(2x+2y-7)+(2x-2y-7)+14}{4}$
だから、それぞれの場合の$x$は$15,8,7,-8,-1,0$
これは$x\le0,7\le x$を満たします。
よって$(x,y)=(15,11),(8,3),(7,1)(-8,11),(-1,3),(0,1)$
が解として出てきます。
次に、絶対値の中身が負の時、つまり
$1\le x\le 6$
の時を考えます。
この時
$-x^2+7x-1=y^2 $
$\Leftrightarrow x^2-7x+1=-y^2 $
$\Leftrightarrow (x-\dfrac{7}{2})^2+y^2=\dfrac{45}{4} $
$\Leftrightarrow (2x-7)^2+4y^2=45$
ここで、$y\ge 4$のとき$4y^2\ge64>45$より、$(2x-7)^2+4y^2>45$となってしまい不適です。よって$y=1,2,3$のどれかです。(ここは不等式評価が少し入っていますね。)
$y=1$の時
$(2x-7)^2=45-4y^2=41$ですが、$41$は平方数でないので$(2x-7)^2$という形では表せず、これは不適です。
$y=2$の時、
$(2x-7)^2=45-16=29$ですがこれも平方数ではないので不適です。
$y=3$の時
$(2x-7)^2=45-36=9$で、これは平方数です。
よって$2x-7=\pm3\Leftrightarrow x=5,2$で、いずれも$1\le x\le 6$を満たします。
よって$(x,y)=(2,3),(5,3)$
以上をまとめて
$(x,y)=(2,3),(5,3),(15,11),(8,3),(7,1)(-8,11),(-1,3),(0,1)$
が求める答えです。

練習問題

$\dfrac{5}{x}+\dfrac{2}{y}=2$を満たす整数$(x,y)$の組を全て求めよ
解答
$(x, y) = (3, 6), (5, 2), (2, -4)$

さらなる応用

先ほどまでのように、$x,y$の式の整数解を求める問題ではありませんが先ほどと同じように解くことができます。
さて、左辺は因数分解できるでしょうか？できなそう、、って思うかもしれませんができます。
$n^4+4=n^4-4n^2+4+4n^2=(n^2-2)^2-(2n)^2=(n^2-2n+2)(n^2+2n+2)$
そういえば数Iでも複2次式とかいうのをやりましたね。
ちなみに、この因数分解により得られる
$n^4+4=(n^2-2n+2)(n^2+2n+2)$
という等式はソフィー・ジェルマンの恒等式(の特別な場合)と呼ばれています。覚える必要はありませんが、因数分解できるということを知っておいたほうがいいかもしれません。
さて、本題に戻りましょう。問題はこの式が素数になる時の$n$を求めよというものでした。素数とは、$1$と自分自身のみを約数にもつ整数のことでした。
いま、
$(n^2-2n+2),(n^2+2n+2)$
はともに正の整数となりますが、その2つの整数の積が素数ということはどちらかは$1$です。よって
$n^2-2n+2=1$または$n^2+2n+2=1$
ということになり、$n>0$より$n=1$が必要になります。逆に、$n=1$の時は$n^4+4=5=$(素数)なのでOKです。したがって$n=1$が唯一の解であるとわかります。

確認ですが、平方数はある(非負)整数$m$を用いて$m^2$と表せる数のことです。よって、問題の条件は
$n^2+n+8=m^2　(m \in \mathbb{Z_{+}})$
となります。($\mathbb{Z_{+}}$は$0$以上の整数の集合をかっこよく書いただけ)
さて、どうしよう。とりあえず、因数分解された式=定数　→勝ち確
だったのを思い出して、因数分解を試みます。右に二乗の形があるので、左辺も平方完成して二乗の形(と定数)にすれば因数分解できそうです。
$(n+\dfrac{1}{2})^2+\dfrac{31}{4}=m^2$
$\Leftrightarrow(2n+1)^2+31=4m^2$
$\Leftrightarrow4m^2-(2n+1)^2=31$
$\Leftrightarrow(2m-2n-1)(2m+2n+1)=31$
$31$は素数であり、また$n>0$より$2m-2n-1<2m+2n+1$で、さらに$0\le m$から$2m+2n+1>0$なので
$(2m-2n-1,2m+2n+1)=(1,31)\Leftrightarrow(m,n)=(8,7)$
よって唯一の解$n=7$を得る。

おわり

因数分解だけで解ける問題は多くないので今回はここでおしまいですが、実際には他のテクニックと絡めて様々な因数分解を用いる問題があります。一つずつ焦らずに抑えていきましょう。