不定方程式の解法

同義語：整数解の求め方techniques for solving Diophantine equations

概要

前提知識: 整数の割り算と互除法, 合同式の計算規則, 約数の個数と約数の総和

高校での出発点：整数解を探す 3 つの型

$xy-2x-3y=0$ や $x^2-3y^2=2$ のように、未知数の個数より式の個数が少ない方程式を、解を整数に限って考えると、解がどれだけあるか・そもそもあるのかが問題になる。実数の範囲なら $xy-2x-3y=0$ の解は双曲線上の点全部で無数にあるが、整数に限ると $8$ 組しかない。この記事では、$1$ 次でない方程式の整数解を求めるときによく使う 3 つの型を、「なぜ効くか・使える条件・効かない例」に分けて調べる。

積の形にする：$xy-2x-3y=0$

左辺に $6$ を足すと $xy-2x-3y+6=(x-3)(y-2)$ と因数分解できるので、方程式は
$$ (x-3)(y-2)=6 $$
と同じである。$x,y$ が整数なら $x-3$ と $y-2$ は掛けて $6$ になる整数の組なので、$6$ の約数の組に限られる。$(x-3,\,y-2)$ は
$$ (1,6),\ (2,3),\ (3,2),\ (6,1),\ (-1,-6),\ (-2,-3),\ (-3,-2),\ (-6,-1) $$
の $8$ 通りで、$(x,y)=(4,8),(5,5),(6,4),(9,3),(2,-4),(1,-1),(0,0),(-3,1)$ である。たとえば $(x,y)=(5,5)$ では $25-10-15=0$ である。

大小を仮定する：$\dfrac1x+\dfrac1y+\dfrac1z=1$

正の整数 $x,y,z$ で $\dfrac1x+\dfrac1y+\dfrac1z=1$ となるものを探す。式は $x,y,z$ を入れかえても変わらないので、まず $x\le y\le z$ の解だけを探す。このとき $\dfrac1x$ が 3 つの中でいちばん大きいので
$$ 1=\frac1x+\frac1y+\frac1z\le\frac1x+\frac1x+\frac1x=\frac3x $$
となり、$x\le3$ である。$x$ の候補が $1,2,3$ の 3 つに絞れた。残りは prop-dio-egyptian で調べる。

余りで調べる：$x^2-3y^2=2$

整数 $x$ を $3$ で割った余りが $0,1,2$ のとき、$x^2$ を $3$ で割った余りはそれぞれ $0,1,1$ である（$2^2=4=3+1$）。$3y^2$ は $3$ の倍数なので、$x^2-3y^2$ を $3$ で割った余りは $0$ か $1$ で、$2$ にはならない。よって $x^2-3y^2=2$ には整数解がない。$x,y$ を 1 つも試さずに「解がない」と分かる。

この記事で答える問いは次の 4 つである。

積の形にすると、なぜ解が有限個に絞れるのか。絞れないのはどんなときか。→ thm-dio-product
大小を仮定してよいのはどんなときか。仮定したあと何を忘れやすいか。→ prop-dio-egyptian、ex-dio-counter-symmetric
「ある数で割った余りで解がない」から「整数解がない」と言えるのはなぜか。→ thm-dio-mod

逆に、どの数で割っても解があれば整数解はあるのか。→ ex-dio-counter-21、rem-dio-hasse

高校の計算	この記事の言葉	大学の言葉
$(x-3)(y-2)=6$ と変形する	積の形と約数の組（thm-dio-product）	整数の約数、双曲線上の格子点
$x\le y\le z$ として $x\le3$	大小の仮定による候補の絞り込み（prop-dio-egyptian）	対称性で割る、有限の探索
$3$ で割った余りを比べる	法 $n$ で調べる（thm-dio-mod）	局所的な障害、$\mathbb{Z}/n\mathbb{Z}$ への還元
どの余りでも矛盾しない	余りだけでは決まらない（ex-dio-counter-21）	局所と大域、Hasse の原理

$1$ 次の不定方程式 $ax+by=c$（$a,b\ne0$）は、この記事の 3 つの型ではなく互除法で完全に解ける。整数解があるのは $\gcd(a,b)$ が $c$ を割るときに限り、解の全体は 1 つの解に $t\left(\dfrac bg,-\dfrac ag\right)$（$g=\gcd(a,b)$、$t$ は整数）を足したものである。証明は整数の割り算と互除法の定理「1 次不定方程式」にある。この記事では $2$ 次以上の方程式や分数の形の方程式を扱う。

不定方程式と整数解

整数を係数とする多項式 $f(x_1,\dots,x_k)$ について、方程式 $f(x_1,\dots,x_k)=0$ を、解を整数（または正の整数）に限って考えるとき、不定方程式 という。$f(a_1,\dots,a_k)=0$ をみたす整数の組 $(a_1,\dots,a_k)$ を 整数解 という。分母を払うと多項式になる方程式（$\dfrac1x+\dfrac1y=\dfrac16$ など）も、分母が $0$ でない解を考えることにして、同じように扱う。

解の個数はさまざま

$x^2+y^2=25$ の整数解は $(\pm5,0)$、$(0,\pm5)$、$(\pm3,\pm4)$、$(\pm4,\pm3)$ の $2+2+4+4=12$ 組である（$\pm$ は符号を独立に選ぶ）。$\lvert x\rvert\le5$ なので、$x=0,\pm1,\dots,\pm5$ を順に試せば確かめられる。
$3x+5y=1$ の整数解は $(x,y)=(2,-1)+t(5,-3)$（$t$ は整数）で、無数にある。
$x^2-3y^2=2$ には整数解がない（ex-dio-start-mod）。

不定方程式を解くとは、整数解を「すべて」求めること、または「ない」ことを示すことである。いくつか見つけただけでは解いたことにならない。この記事の 3 つの型は、どれも「調べる候補を有限個に絞る」か「解がないことを一度に示す」ための道具である。

型 1：積の形にする

約数の組は有限個

ex-dio-start-product で解が $8$ 組に絞れたのは、$0$ でない整数 $N$ を 2 つの整数の積に分ける方法が有限個しかないからである。

積が $N$ になる整数の組

$N$ を $0$ でない整数とする。$uv=N$ をみたす整数の組 $(u,v)$ は、$u$ が $N$ の約数（負の約数も含む）全体を動き $v=\dfrac Nu$ としたものに限られる。その個数は $2\,d(\lvert N\rvert)$ である。ここで $d(m)$ は正の整数 $m$ の正の約数の個数である。

正の約数と負の約数に分ける

要点：$uv=N$ なら $u$ は $N$ の約数で、$v=\dfrac Nu$ は $u$ から決まる。$\lvert N\rvert$ の正の約数 $e$ 1 つにつき $u=e$ と $u=-e$ の 2 つがあるので、組は $2\,d(\lvert N\rvert)$ 個である。

詳しい証明を開く

段 1（$u$ は $N$ の約数）。$uv=N$ なら、$N$ は $u$ の $v$ 倍なので $u$ は $N$ を割る。$N\ne0$ なので $u\ne0$ であり、$v=\dfrac Nu$ と $u$ から決まる。逆に $u$ が $N$ の約数なら $v=\dfrac Nu$ は整数で、$uv=N$ である。

段 2（数える）。$u$ が $N$ の約数であることと、$\lvert u\rvert$ が $\lvert N\rvert$ の正の約数であることは同じである。正の約数 $e$ 1 つにつき $u=e$ と $u=-e$ の 2 つがあるので、$u$ の候補は $2\,d(\lvert N\rvert)$ 個である。$\square$

約数の組を数える

$N=6$：正の約数は $1,2,3,6$ の $d(6)=4$ 個で、組 $(u,v)$ は $2\cdot4=8$ 個ある（ex-dio-start-product の 8 通り）。
$N=-12$：$\lvert N\rvert=12$ の正の約数は $1,2,3,4,6,12$ の $6$ 個なので、組は $12$ 個ある。$u=3$ なら $v=-4$、$u=-3$ なら $v=4$ である。
$N=0$ では $u=0$ なら $v$ は何でもよく、組は無数にある。lem-dio-pairs で $N\ne0$ を仮定したのはこのためである。

約数の個数 $d(m)$ は、$m=p_1^{e_1}\cdots p_k^{e_k}$ と素因数分解すると $(e_1+1)\cdots(e_k+1)$ である。この公式と証明は約数の個数と約数の総和で扱う。

主定理 1：積の形で解が有限個に絞れる条件

$xy$ の項と $1$ 次の項だけをもつ方程式は、いつでも積の形に直せる。

$xy+ax+by=c$ の整数解

$a,b,c$ を整数とし、$N:=c+ab$ とおく。方程式
$$ xy+ax+by=c $$
は $(x+b)(y+a)=N$ と同じである。

$N\ne0$ のとき、整数解は
$$ (x,y)=\Bigl(u-b,\ \frac Nu-a\Bigr)\qquad(u\text{ は }N\text{ の約数。負の約数も含む}) $$
で全部であり、ちょうど $2\,d(\lvert N\rvert)$ 組ある。特に有限個である。
$N=0$ のとき、整数解は「$x=-b$ で $y$ は任意の整数」と「$y=-a$ で $x$ は任意の整数」を合わせたもので、無数にある。

両辺に $ab$ を足して因数分解する

方針：$ab$ を足して左辺を因数分解し、lem-dio-pairs を使う。
段 1（変形）。展開すると $(x+b)(y+a)=xy+ax+by+ab$ である。よって
$$ xy+ax+by=c\iff xy+ax+by+ab=c+ab\iff(x+b)(y+a)=N $$
である。どの変形も両辺に同じ数を足しただけなので、逆向きにもたどれる。
段 2（$N\ne0$）。$u:=x+b$、$v:=y+a$ とおくと、$x,y$ が整数であることと $u,v$ が整数であることは同じで、方程式は $uv=N$ になる。lem-dio-pairs により、$u$ は $N$ の約数全体を動き、$v=\dfrac Nu$ である。$x=u-b$、$y=v-a$ に戻すと 1 の形になる。$u$ が違えば $x$ が違うので、解の個数は $u$ の個数 $2\,d(\lvert N\rvert)$ に等しい。
段 3（$N=0$）。$(x+b)(y+a)=0$ は「$x+b=0$ または $y+a=0$」と同じである（2 つの整数の積が $0$ なら、どちらかが $0$）。$x=-b$ なら $y$ が何でも式が成り立ち、$y=-a$ なら $x$ が何でも成り立つ。$\square$

双曲線 (x-3)(y-2)=6 と、その上の格子点 8 個（赤）。破線は漸近線 x=3 と y=2 で、格子点は漸近線から約数の分だけ離れた位置にある
図 1 は ex-dio-start-product の方程式のグラフである。実数の解は双曲線上の点全部だが、$x$ が大きくなると $y-2=\dfrac6{x-3}$ は $0$ と $1$ の間に入ってしまい、$y$ は整数になれない。格子点が漸近線の近くの有限個に限られるのは、このためである。$N=0$ の場合は、双曲線が 2 本の直線 $x=-b$、$y=-a$ につぶれ、直線上の格子点が無数にある。

定理をそのまま使う

$xy-2x-3y=0$ は $a=-2$、$b=-3$、$c=0$ で、$N=0+(-2)(-3)=6$ である。解は $2\,d(6)=8$ 組で、ex-dio-start-product と一致する。
$xy-2x-3y=-6$ は $N=-6+6=0$ なので、$(x-3)(y-2)=0$ となり、$x=3$ または $y=2$ をみたす組すべてが解である。たとえば $(3,100)$ では $300-6-300=-6$ である。
同じ型の例 (3) を開く
(3) $xy+x+y=5$ は $a=b=1$、$c=5$ で、$N=5+1=6$、$(x+1)(y+1)=6$ である。$u=x+1$ が $1,2,3,6,-1,-2,-3,-6$ のとき
$$(x,y)=(0,5),\ (1,2),\ (2,1),\ (5,0),\ (-2,-7),\ (-3,-4),\ (-4,-3),\ (-7,-2)$$
の $8$ 組である。たとえば $(1,2)$ では $2+1+2=5$ である。

分数の形とかけ算の係数

分数の形の方程式は、分母を払うと thm-dio-product の形になることが多い。

$\dfrac1x+\dfrac1y=\dfrac16$ の正の整数解

分母を払う（両辺に $6xy$ を掛ける）と $6y+6x=xy$、つまり $xy-6x-6y=0$ である。$36$ を足して
$$ (x-6)(y-6)=36 $$
となる。$x,y$ は正なので $\dfrac1x<\dfrac16$、つまり $x>6$ であり、同じく $y>6$ である。よって $x-6$ と $y-6$ は正の約数の組で、$36=2^2\cdot3^2$ の正の約数は $d(36)=3\cdot3=9$ 個あるから、解は $9$ 組である：
$$ (x,y)=(7,42),\ (8,24),\ (9,18),\ (10,15),\ (12,12),\ (15,10),\ (18,9),\ (24,8),\ (42,7). $$
たとえば $(10,15)$ では $\dfrac1{10}+\dfrac1{15}=\dfrac{3+2}{30}=\dfrac16$ である。負の約数の組が使えないことは、$x>6$ という大小の評価（型 2）から出ている。

$xy$ の係数が $1$ でないときは、両辺にその係数を掛けてから因数分解する。

$xy$ の係数が $2$ や $3$ のとき

$3xy+x+y=5$。両辺に $3$ を掛けて $1$ を足すと
$$ (3x+1)(3y+1)=16 $$
である。$x$ が整数なので、$3x+1$ は $3$ で割って $1$ 余る数である。$16$ の約数 $\pm1,\pm2,\pm4,\pm8,\pm16$ のうち、$3$ で割って $1$ 余り、しかも組になる $\dfrac{16}u$ も $3$ で割って $1$ 余るのは $u=1,4,16,-2,-8$ の $5$ つだけである。解は
$$ (x,y)=(0,5),\ (1,1),\ (5,0),\ (-1,-3),\ (-3,-1) $$
の $5$ 組である。たとえば $(-1,-3)$ では $9-1-3=5$ である。約数の組を作ったあとで、余りの条件でふるいにかける必要がある。これは型 1 と型 3 の組み合わせである。
係数が $2$ の例 (2) を開く
(2) $2xy+x+y=7$。両辺に $2$ を掛けて $1$ を足すと $4xy+2x+2y+1=15$、つまり
$$(2x+1)(2y+1)=15$$
である。$15$ の約数 $u=\pm1,\pm3,\pm5,\pm15$ はどれも奇数なので、$x=\dfrac{u-1}2$ はいつも整数になり、解は $8$ 組ある：$(0,7),(1,2),(2,1),(7,0),(-1,-8),(-2,-3),(-3,-2),(-8,-1)$。(1) と違って、約数でふるう必要がない。

平方の差も積の形になる

$x^2-y^2=(x-y)(x+y)$ なので、平方の差が一定の方程式も積の形になる。このとき $x-y$ と $x+y$ の和 $2x$ が偶数なので、2 つの因数の偶奇がそろうことが条件に加わる。

$x^2-y^2=45$ と $x^2=y^2+2y+13$

$x^2-y^2=45$ の正の整数解。$(x-y)(x+y)=45$ で、$x,y>0$ なら $x+y>0$ なので $x-y>0$ でもあり、$x-y< x+y$ である。$45$ を小さい方から $1\cdot45$、$3\cdot15$、$5\cdot9$ と分けると
$$ x=\frac{(x-y)+(x+y)}2,\qquad y=\frac{(x+y)-(x-y)}2 $$
から $(x,y)=(23,22),\ (9,6),\ (7,2)$ の $3$ 組である。$45$ は奇数なので、約数はどれも奇数で偶奇はそろっている。
同じ型の例 (2) を開く
(2) $x^2=y^2+2y+13$ の整数解。$y^2+2y+13=(y+1)^2+12$ なので $x^2-(y+1)^2=12$、つまり
$$(x-y-1)(x+y+1)=12$$
である。2 つの因数の和は $2x$ で偶数なので、2 つとも偶数か 2 つとも奇数である。積 $12$ は偶数なので 2 つとも奇数ではありえず、2 つとも偶数である。$12$ を偶数 2 つの積に分けるのは $(2,6),(6,2),(-2,-6),(-6,-2)$ だけで、$(x,y)=(4,1),(4,-3),(-4,-3),(-4,1)$ の $4$ 組である。たとえば $(4,1)$ では $16=1+2+13$ である。

型 2：大小を仮定して範囲を絞る

対称な式では並べてから調べる

式が未知数の入れかえで変わらないとき、未知数を小さい順に並べた解だけを探し、最後に並べかえて戻せばよい。並べると「いちばん小さい未知数」の範囲が不等式で押さえられる。

$\dfrac1x+\dfrac1y+\dfrac1z=1$ の正の整数解

正の整数 $x,y,z$ で $\dfrac1x+\dfrac1y+\dfrac1z=1$ をみたすものは、$x\le y\le z$ と並べると
$$ (x,y,z)=(3,3,3),\ (2,4,4),\ (2,3,6) $$
の 3 つである。並べる前の順序を区別すると、全部で $1+3+6=10$ 組ある。

小さい順に 1 つずつ候補を絞る

方針：ex-dio-start-order と同じ不等式で $x$ を絞り、$x$ を決めたあと同じ考え方で $y$ を絞る。$z$ は最後に式から決まる。
段 1（並べてよい理由）。式の左辺は $x,y,z$ を入れかえても同じ値なので、解 $(x,y,z)$ の 3 つの数を小さい順に並べかえたものも解である。よって、$x\le y\le z$ の解をすべて求め、それを並べかえたものを集めれば、解の全体になる。
段 2（$x$ の範囲）。$x\le y\le z$ なので $\dfrac1x\ge\dfrac1y\ge\dfrac1z$ であり、
$$ 1=\frac1x+\frac1y+\frac1z\le\frac3x $$
から $x\le3$ である。また $x=1$ なら $\dfrac1y+\dfrac1z=0$ となるが、左辺は正なのでありえない。よって $x=2$ か $x=3$ である。
段 3（$x=2$ のとき）。$\dfrac1y+\dfrac1z=\dfrac12$ である。$\dfrac1y<\dfrac12$ なので $y>2$、つまり $y\ge3$ である。$y\le z$ から $\dfrac12=\dfrac1y+\dfrac1z\le\dfrac2y$ なので $y\le4$ である。$y=3$ なら $\dfrac1z=\dfrac12-\dfrac13=\dfrac16$ で $z=6$、$y=4$ なら $\dfrac1z=\dfrac12-\dfrac14=\dfrac14$ で $z=4$ である。
段 4（$x=3$ のとき）。$\dfrac1y+\dfrac1z=\dfrac23$ である。$y\ge x=3$ と $\dfrac23\le\dfrac2y$ から $y\le3$ なので $y=3$ で、$\dfrac1z=\dfrac23-\dfrac13=\dfrac13$ から $z=3$ である。
段 5（並べかえて戻す）。$(3,3,3)$ は並べかえても $1$ 通り、$(2,4,4)$ は $2$ の位置で $3$ 通り、$(2,3,6)$ は 3 つが異なるので $3!=6$ 通りある。合わせて $10$ 組である。$\square$

段 3 で「$\dfrac1y+\dfrac1z=\dfrac12$、$y\le z$」を解くのは、ex-dio-sixth と同じく積の形 $(y-2)(z-2)=4$ に直しても解ける。型 2 で候補を絞り、残りを型 1 で解くのは、よくある組み合わせである。

同じ方法で 2 つの場合

prf-dio-egyptian と同じく、小さい順に並べて最小の未知数を不等式で絞ると、(1) $\dfrac1x+\dfrac1y=\dfrac12$ の正の整数解は $(3,6),(6,3),(4,4)$ の $3$ 組、(2) $xyz=x+y+z$ の $x\le y\le z$ の正の整数解は $(1,2,3)$ だけである。

同じ方法の例 (1)(2) の解き方を開く

(1) 正の整数 $x\le y$ で $\dfrac1x+\dfrac1y=\dfrac12$。$\dfrac12\le\dfrac2x$ から $x\le4$、$\dfrac1x<\dfrac12$ から $x\ge3$ である。$x=3$ なら $y=6$、$x=4$ なら $y=4$ である。よって $(x,y)=(3,6),(4,4)$ で、並べかえを戻すと $(3,6),(6,3),(4,4)$ の $3$ 組である。

(2) 正の整数 $x\le y\le z$ で $xyz=x+y+z$。$z$ がいちばん大きいので $xyz=x+y+z\le3z$ で、両辺を $z$（$>0$）で割って $xy\le3$ である。$x\le y$ なので $(x,y)=(1,1),(1,2),(1,3)$ に限られる。$(1,1)$ なら $z=2+z$ で解なし、$(1,2)$ なら $2z=3+z$ で $z=3$、$(1,3)$ なら $3z=4+z$ で $z=2$ となり $y\le z$ に反する。よって $(x,y,z)=(1,2,3)$ だけで、実際 $1\cdot2\cdot3=6=1+2+3$ である。

平方数ではさむ

大小の評価は、未知数の範囲だけでなく「となり合う 2 つの平方数の間には平方数がない」という形でも使える。

$n^2+n+1$ が平方数になる整数 $n$

$n\ge1$ なら
$$ n^2< n^2+n+1< n^2+2n+1=(n+1)^2 $$
である（左の不等号は $n+1>0$、右の不等号は $n>0$ による）。$n^2$ と $(n+1)^2$ はとなり合う平方数なので、その間にある $n^2+n+1$ は平方数ではない（図 2）。
$n\le-2$ のときも、$m:=-n-1$（$\ge1$）とおくと $n^2+n+1=m^2+m+1$ となるので、前半により平方数ではない。

詳細

$n=-m-1$ を代入して展開すると $n^2+n+1=(m+1)^2-(m+1)+1=m^2+2m+1-m-1+1=m^2+m+1$ である。$n\le-2$ なら $m=-n-1\ge1$ なので、前半の $n\ge1$ の場合を $m$ に使える。

残りは $n=0$ と $n=-1$ で、どちらも $n^2+n+1=1=1^2$ である。よって $n^2+n+1$ が平方数になるのは $n=0,-1$ だけである。

n=0,1,…,6 について n²（青）、n²+n+1（赤）、(n+1)²（緑）を並べた図。n が 1 以上では赤い点がいつも青と緑の間に入る
型 2 の要点は、方程式から「ある未知数が小さい」か「ある量が 2 つの値の間にある」ことを不等式で導き、候補を有限個にすることである。式が対称でないのに大小を仮定すると解を落とす（ex-dio-counter-symmetric）。

型 3：余りで調べる

主定理 2：ある法で解がなければ整数解はない

ex-dio-start-mod の論法を一般の形で述べる。合同式の記号 $a\equiv b\pmod n$（$a-b$ が $n$ で割り切れること）と、その計算規則（足し算・引き算・掛け算は合同式のまま行える）は合同式の計算規則で扱う。

法 $n$ での解と整数解

$f(x_1,\dots,x_k)$ を整数係数の多項式とし、$n\ge2$ を整数とする。

方程式 $f(x_1,\dots,x_k)=0$ が整数解をもつなら、合同式 $f(x_1,\dots,x_k)\equiv0\pmod n$ も整数解をもつ。対偶をとると、ある $n$ で合同式が解をもたなければ、方程式は整数解をもたない。
$x_i\equiv x_i'\pmod n$（$i=1,\dots,k$）なら $f(x_1,\dots,x_k)\equiv f(x_1',\dots,x_k')\pmod n$ である。したがって、合同式が解をもつかどうかは、各 $x_i$ に $0,1,\dots,n-1$ を代入した $n^k$ 通りを調べれば決まる。

同じ整数を合同式の解として使う

方針：1 は、方程式の解がそのまま合同式の解になることから出る。2 は、多項式が足し算と掛け算だけで作られていることと、合同式の計算規則から出る。
段 1（1 の証明）。$(a_1,\dots,a_k)$ を方程式の整数解とすると $f(a_1,\dots,a_k)=0$ である。$0$ は $n$ の倍数なので $f(a_1,\dots,a_k)\equiv0\pmod n$ であり、同じ組が合同式の解である。対偶は「合同式が解をもたない $\Rightarrow$ 方程式が整数解をもたない」である。
段 2（累乗）。$x\equiv x'\pmod n$ なら、掛け算の規則を $m-1$ 回使って $x^m\equiv x'^m\pmod n$ である。
段 3（項と和）。$f$ の各項は、整数の係数 $c$ と累乗の積 $c\,x_1^{m_1}\cdots x_k^{m_k}$ である。段 2 と掛け算の規則により、各項は $x_i$ を $x_i'$ に替えても法 $n$ で合同である。項どうしを足すときは足し算の規則を使えば、$f(x_1,\dots,x_k)\equiv f(x_1',\dots,x_k')$ である。
段 4（有限個で決まる）。どの整数 $x_i$ も、$n$ で割った余り $r_i\in\{0,1,\dots,n-1\}$ と法 $n$ で合同である。段 3 により $f(x_1,\dots,x_k)\equiv f(r_1,\dots,r_k)$ なので、合同式の解があれば余りの組の中にも解がある。余りの組は $n^k$ 通りである。$\square$

型 3 の使い方は、「うまい $n$ を選び、余りの組を全部調べて、どれも $f\equiv0$ にならないことを確かめる」である。調べる組の個数が有限なので、必ず終わる。ただし、結論が出るのは「解がない」ときだけである。どの $n$ でも解があっても、整数解があるとは限らない（ex-dio-counter-21）。

平方数・立方数の余り

$2$ 乗や $3$ 乗を含む式では、累乗の余りの表をあらかじめ作っておくと、$n$ を選びやすい。

平方数と立方数の余り

整数 $x$ について、次が成り立つ。

$x^2$ を $3$ で割った余りは $0$ か $1$、$4$ で割った余りは $0$ か $1$、$8$ で割った余りは $0,1,4$ のどれかである。
$x^3$ を $9$ で割った余りは $0,1,8$ のどれかである。

余りを全部代入する

thm-dio-mod の 2 により、$x$ に $0,1,\dots,n-1$ を代入して調べればよい。法 $3$・法 $4$ では $2^2=4$、$3^2=9$ のように $x=0,\dots,n-1$ の平方を計算すればすぐ分かる（図 3 の表の法 $3$・法 $4$・法 $8$ の行）。

全部の余りの計算を開く

段 1（法 $3$）。$0^2=0$、$1^2=1$、$2^2=4\equiv1$。

段 2（法 $4$）。$0^2=0$、$1^2=1$、$2^2=4\equiv0$、$3^2=9\equiv1$。

段 3（法 $8$）。$x=0,1,\dots,7$ について $x^2=0,1,4,9,16,25,36,49$ で、$8$ で割った余りは $0,1,4,1,0,1,4,1$ である。

段 4（立方、法 $9$）。$x=0,1,\dots,8$ について $x^3=0,1,8,27,64,125,216,343,512$ で、$9$ で割った余りは $0,1,8,0,1,8,0,1,8$ である（$64=63+1$、$125=117+8$、$343=342+1$、$512=504+8$）。$\square$

法 3 から法 10 までについて、余り 0,1,…,n−1 のうち平方数の余りとして現れるもの（赤）を並べた表。法 3・4 では 2 個、法 8 では 3 個しか現れない
図 3 のように、平方数の余りとして現れる数は、法によって多い少ないがあるが、全部の余りが現れることはない（$x$ と $-x$ の平方は同じ余りになるので、法 $n\ge3$ では現れない余りが必ずある）。法 $6$ や法 $10$ のように半分を超える法もある。現れない余りが多い法ほど、型 3 で「解がない」と言える場面が多い。法 $4$ や法 $8$ がよく使われるのは、現れる余りが特に少ないからである。

余りで解がないことを示す

$x^2+y^2=4k+3$（$k$ は整数）。lem-dio-squares の 1 により $x^2,y^2$ を $4$ で割った余りは $0,1$ なので、和の余りは $0,1,2$ で、$3$ にならない。よって $x^2+y^2=2027$ などに整数解はない（$2027=4\cdot506+3$）。4 で割って 3 余る数が 2 つの平方数の和にならないことは Cri24 Fact 13.1.1 にもある。
ほかの例 (2)(3)(4) を開く
(2) $x^2+y^2+z^2=8k+7$。$8$ で割った余りが $0,1,4$ の数を 3 つ足した余りは、$0,1,2,3,4,5,6$ のどれかで、$7$ にならない。よって $7,15,23,31,\dots$ は 3 つの平方数の和にならない。
(3) $x^2-y^2=2026$。$x^2-y^2$ を $4$ で割った余りは $0-0,\ 0-1,\ 1-0,\ 1-1$ から $0,3,1,0$ で、$2$ にならない。$2026=4\cdot506+2$ なので整数解はない。ex-dio-difference の偶奇の議論と同じことを、余りで一度に言っている。
(4) $x^3+y^3=2030$。lem-dio-squares の 2 により 2 つの立方数の和を $9$ で割った余りは $0+0,0+1,0+8,1+1,1+8,8+8$ から $0,1,8,2,0,7$ で、$\{0,1,2,7,8\}$ に限られる。$2030=9\cdot225+5$ なので、整数解はない。

$n$ の選び方の目安をまとめておく。係数に $3$ が付いた項（$3y^2$ など）があれば法 $3$ でその項が消える。平方数の和・差には法 $4$ と法 $8$、立方数には法 $7$ か法 $9$ が効きやすい。定数項の余りが「現れない余り」になる法を探すのが基本である。

余りだけでは足りないとき：無限降下法

$x^2+y^2=3z^2$ には $(0,0,0)$ という解があるので、どの $n$ で調べても合同式には解がある。それでも、$0$ 以外の解がないことは余りと大小を組み合わせて示せる。

$x^2+y^2=3z^2$ の整数解

$x^2+y^2=3z^2$ をみたす整数の組は $(x,y,z)=(0,0,0)$ だけである。

法 $3$ で調べて 3 で割り続ける

方針：解があれば $x,y,z$ はすべて $3$ の倍数であることを示す。すると全部を $3$ で割っても解になり、$0$ でない解があれば、どこまでも小さくなる正の整数の列ができて矛盾する。
段 1（$x,y$ は $3$ の倍数）。右辺は $3$ の倍数なので $x^2+y^2\equiv0\pmod3$ である。lem-dio-squares の 1 により $x^2,y^2$ の余りは $0$ か $1$ で、和の余りが $0$ になるのは 2 つとも $0$ のときだけである。$x^2\equiv0$ となるのは $x\equiv0$ のときだけなので（$1^2\equiv2^2\equiv1$）、$x,y$ は $3$ の倍数である。
段 2（$z$ も $3$ の倍数）。$x=3x_1$、$y=3y_1$ とおくと $9x_1^2+9y_1^2=3z^2$、つまり $z^2=3(x_1^2+y_1^2)$ である。$z^2$ が $3$ の倍数なので、段 1 と同じく $z$ は $3$ の倍数で、$z=3z_1$ と書ける。代入すると $9z_1^2=3(x_1^2+y_1^2)$、つまり $x_1^2+y_1^2=3z_1^2$ である。
段 3（降下）。$(0,0,0)$ でない解 $(x,y,z)$ があったとする。段 1・2 により $(x_1,y_1,z_1)=\left(\dfrac x3,\dfrac y3,\dfrac z3\right)$ も解で、$(0,0,0)$ でない。$\lvert x\rvert+\lvert y\rvert+\lvert z\rvert$ は正の整数で、$(x_1,y_1,z_1)$ に移ると $3$ 分の $1$ になる。これを繰り返すと、正の整数が $3$ 分の $1$ ずつ小さくなる列が限りなく続くが、正の整数はいくらでも小さくはなれない（$1$ より小さい正の整数はない）ので矛盾である。$\square$

この論法を 無限降下法 という。「正の整数の集合には最小のものがある」（整列性）を使っていて、その根拠は数学的帰納法と整列性で扱う。同じ論法で $x^4+y^4=z^2$ に正の整数解がないことも示せる（ピタゴラス数と円の有理点）。prop-dio-descent は、円 $X^2+Y^2=3$ の上に有理数の座標の点が 1 つもないことと同じである（$X=\dfrac xz$、$Y=\dfrac yz$）。

3 つの型のまとめ

型	いつ使うか	例	限界
1：積の形にする	$xy$ と 1 次の項だけ、平方の差、分母を払うとそうなる式	ex-dio-start-product、ex-dio-sixth、ex-dio-difference	右辺が $0$ になると無数の解（thm-dio-product の 2）。係数を掛けたら余りでふるう
2：大小を仮定する	対称な式、分数の和、積と和の比較、平方数ではさめる式	prop-dio-egyptian、ex-dio-egyptian-two、ex-dio-squeeze	対称でない式では仮定できない。最後に並べかえを戻す
3：余りで調べる	解がないことを示したいとき。平方・立方を含む式	ex-dio-start-mod、ex-dio-mod-use	解があることは示せない。$(0,0,0)$ のような解があると無限降下法が要る

実際の問題では型を組み合わせる。ex-dio-coefficient の (1) は型 1 のあと型 3 でふるい、ex-dio-sixth は型 1 のあと型 2 で負の約数を除き、prop-dio-descent は型 3 と大小（型 2 の考え方）を組み合わせている。

例と反例

外す条件	反例	成り立たなくなること
式が未知数の入れかえで変わらない	$\dfrac2x+\dfrac1y=1$ で $x\le y$ と仮定する（ex-dio-counter-symmetric）	大小を仮定しても解を落とさない
最後に並べかえを戻す	$\dfrac1x+\dfrac1y+\dfrac1z=1$ の答を 3 組とする（ex-dio-counter-symmetric）	解の全体を答える
負の約数も数える	$(x-3)(y-2)=6$ で正の約数だけを使う（ex-dio-counter-negative）	解の個数 $2\,d(\lvert N\rvert)$
$N\ne0$	$xy-2x-3y=-6$（ex-dio-product-use の (2)）	解が有限個
「法 $n$ で解なし」の向き	$x^2+y^2=21$ は法 $3$・法 $4$ で解がある（ex-dio-counter-21）	法 $n$ で解がある $\Rightarrow$ 整数解がある（これは一般には成り立たない）

反例：対称でない式で大小を仮定する

正の整数で $\dfrac2x+\dfrac1y=1$ を解くとき、prop-dio-egyptian をまねて $x\le y$ と仮定すると、$1=\dfrac2x+\dfrac1y\le\dfrac3x$ から $x\le3$、$\dfrac2x<1$ から $x\ge3$ なので $x=3$、$y=3$ だけが得られる。しかし $(x,y)=(4,2)$ も解である（$\dfrac24+\dfrac12=1$）。式は $x$ と $y$ を入れかえると $\dfrac1x+\dfrac2y=1$ に変わるので、prf-dio-egyptian の段 1 の理由（入れかえても解のまま）が使えない。正しくは、分母を払って $xy-x-2y=0$、$(x-2)(y-1)=2$ とし、$x-2>0$（$\dfrac2x<1$ から $x>2$）から $(x-2,y-1)=(1,2),(2,1)$、つまり $(x,y)=(3,3),(4,2)$ である。
並べかえを戻し忘れる例 (2) を開く
(2) prop-dio-egyptian で $x\le y\le z$ の 3 組 $(3,3,3),(2,4,4),(2,3,6)$ だけを答えると、たとえば $(4,2,4)$ や $(6,3,2)$ を落とす。求められているのが順序を区別した解なら、prf-dio-egyptian の段 5 のように並べかえを戻して $10$ 組と答える。

反例：負の約数を忘れる

$(x-3)(y-2)=6$ で $x-3$ を正の約数 $1,2,3,6$ だけに限ると、$(x,y)=(4,8),(5,5),(6,4),(9,3)$ の $4$ 組しか出ない。$x-3=-3$ とすると $y-2=-2$ で $(x,y)=(0,0)$ が解になるように（$0-0-0=0$）、負の約数からも解が出る。lem-dio-pairs で、正の約数 $e$ ごとに $u=\pm e$ の 2 つを数えたのはこのためである。正の約数だけでよいのは、ex-dio-sixth のように大小の評価で負の場合を除けたときに限る。

反例：余りでは矛盾しないのに整数解がない

$x^2+y^2=21$ を考える。$\lvert x\rvert\le4$ なので $x^2=0,1,4,9,16$ を試すと、$y^2=21,20,17,12,5$ で、どれも平方数ではない。よって整数解はない。
ところが法 $4$ では $21\equiv1$ で、$x^2+y^2\equiv0+1$ と表せるので合同式は解をもつ（$x=0$、$y=1$）。法 $3$ でも $21\equiv0$ で、$x\equiv y\equiv0$ が合同式の解である。この 2 つの法を調べただけでは「解がない」と言えない。$21$ は、4 で割った余りでは除けないのに 2 つの平方数の和にならない数の例として Cri24 Fact 13.1.2 に挙がっている。
法 $9$ では言える。平方数を $9$ で割った余りは $0,1,4,7$（$x=0,\dots,8$ で $0,1,4,0,7,7,0,4,1$）で、2 つの和の余りは $0,1,2,4,5,7,8$ のどれかであり、$21\equiv3$ にならない。このように、解がないときでも、効く法を見つけるまで試す必要がある。
さらに、どの法でも合同式が解をもつのに整数解がない方程式もある（rem-dio-hasse）。thm-dio-mod の 1 の逆は成り立たない。

大学数学で見る：局所と大域

局所的な障害と Hasse の原理

thm-dio-mod は、方程式を整数の世界 $\mathbb{Z}$ から有限の世界 $\mathbb{Z}/n\mathbb{Z}$（$n$ で割った余りの世界。剰余環）へ移して調べる方法である。$\mathbb{Z}/n\mathbb{Z}$ で解がないことを、大学では 局所的な障害 と呼ぶ。整数解（大域的な解）があれば、どの $n$ でも合同式の解（局所的な解）と実数の解がある。
逆向きが成り立つかどうかが、大学の整数論の大きな問題の 1 つである。

Hasse–Minkowski の定理と、逆が成り立たない例を開く

$2$ 次形式（各項の次数がちょうど $2$ の整数係数の多項式、たとえば $x^2+y^2-3z^2$）については、逆が成り立つ。$2$ 次形式 $q$ について、$q=0$ が $(0,\dots,0)$ 以外の整数解をもつことは、実数の範囲で $(0,\dots,0)$ 以外の解をもち、かつすべての素数 $p$ とすべての正の整数 $k$ について、$p^k$ を法とする合同式 $q\equiv0$ が「成分のどれかが $p$ の倍数でない」解をもつことと同値である。これを Hasse–Minkowski の定理 といい、このように局所的な解から大域的な解が出ることを Hasse の原理 という（Cla25 Theorem 18.7。同書は「すべての正の整数 $n$ を法として自明でない解をもつ」と述べている。ここでは「自明でない」の意味をはっきりさせるため、素数の累乗を法とし、成分のどれかが $p$ の倍数でない解の形で述べた。本記事では証明しない）。prop-dio-descent の段 1・段 2 は、$x^2+y^2-3z^2\equiv0\pmod 9$ に「$x,y,z$ のどれかが $3$ の倍数でない」解がないことを示しており、これが整数解がない理由になっている。

$3$ 次以上では Hasse の原理は一般に成り立たない。Selmer の例 $3x^3+4y^3+5z^3=0$ は、$(0,0,0)$ 以外の実数の解をもち、上と同じ意味の合同式の解もすべての $p^k$ でもつが、$(0,0,0)$ 以外の整数解をもたない（Cla25 Theorem 18.9。証明しない）。

1 変数でも逆は成り立たない。$f(x)=(x^2-2)(x^2-17)(x^2-34)$ とすると、$f(x)=0$ の実数解は $\pm\sqrt2,\pm\sqrt{17},\pm\sqrt{34}$ で、どれも整数ではない。一方、どの $n\ge2$ でも $f(x)\equiv0\pmod n$ は解をもつことが知られている（素数の累乗 $p^k$ ごとに、$2$ か $17$ か $34$ のどれかが法 $p^k$ で平方数になることを確かめ、中国剰余定理（高校数学）で貼り合わせる。$p=2$ では $17\equiv1\pmod8$ から $17$ がどの $2^k$ を法としても平方数になる。$p=17$ では $2\equiv6^2$ を使う。ほかの素数 $p$ では、$2$ と $17$ がどちらも法 $p$ で平方数でなければ $34$ が平方数になることを使い、法 $p$ の解を法 $p^k$ の解へ持ち上げる。本記事では証明しない）。$2\le n\le3000$ のすべての $n$ で解があることは、計算機で確かめた。

Pell 方程式：解が無数にある 2 次の方程式

3 つの型は、どれも「解が有限個」か「解がない」ときに効く。$x^2-2y^2=1$ のように解が無数にある 2 次の方程式は、別の道具で解く。$(3+2\sqrt2)^k=x_k+y_k\sqrt2$ と展開した係数 $(x_k,y_k)$ がすべての正の整数解を与え、$k=1,2,3$ で $(3,2),(17,12),(99,70)$ となる（Pell方程式。本記事では証明しない）。

計算の確認と、右辺を変えた例を開く

たとえば $17^2-2\cdot12^2=289-288=1$ である。$x^2-3y^2=2$ に解がない（ex-dio-start-mod）のに、$x^2-3y^2=1$ には $(2,1),(7,4),\dots$ と無数に解がある。右辺の数が変わるだけで、答えの様子がまったく変わる。

さらに先へ

$1$ 次の不定方程式 $ax+by=c$ は互除法で完全に解ける（整数の割り算と互除法）。1 次の合同式 $ax\equiv b\pmod n$ も同じ条件で解ける（合同式の割り算と逆元）。
型 3 で法を 2 つ以上使うとき、それぞれの法での解を 1 つの法での解にまとめるのが中国剰余定理（高校数学）である。rem-dio-hasse の最後の例もこれを使う。
$x^2+y^2=z^2$ の整数解（ピタゴラス数）は、型 1（$z^2-x^2=(z-x)(z+x)$）と素因数分解の組み合わせで全部求まる（ピタゴラス数と円の有理点）。$x^2+y^2=n$ となる $n$ の特徴づけは Fermatの二平方定理で扱う。
2 次の不定方程式を、座標を取りかえて標準形に直すと、2次曲線と2次形式の分類と同じ話になる。楕円なら解は有限個、双曲線なら無数にありうる。