1次不定方程式の整数解(一般解)

方針

解答

⓪ 発想 — どう考え始めるか。 $1$ 次不定方程式は「特殊解を $1$ つ見つけ、そこに周期を足す」のが定石。まず解を $1$ 組だけ探す。

合同式が速い。$17x-13y=5$ を $\mathrm{mod}13$ で見ると $17x\equiv 5$、$17\equiv 4$ だから $4x\equiv 5(\mathrm{mod}13)$。$4$ の逆数($4\cdot 10=40\equiv 1$)を掛けて $x\equiv 50\equiv 11(\mathrm{mod}13)$。$x=11$ なら $y=\frac{17\cdot 11-5}{13}=14$。

一般解は「特殊解 $+$ 係数を入れ替えた周期」。$x=11+13t$、$y=14+17t$($t$ は整数)。$x$ の周期が $13$($y$ の係数)、$y$ の周期が $17$($x$ の係数)になる。

① 特殊解を探す。 $17x-13y=5$ を $\mathrm{mod}13$ で見ると $17\equiv 4$ だから

$$4x\equiv 5(\mathrm{mod}13)$$

$4$ の逆数は $10$($4\cdot 10=40\equiv 1$)だから $x\equiv 50\equiv 11(\mathrm{mod}13)$。$x=11$ のとき $17\cdot 11=187$、$187-5=182=13\cdot 14$ より $y=14$。特殊解 $(x,y)=(11,14)$。

② 一般解を書く。 $x$ の係数 $17$、$y$ の係数 $13$ を入れかえてずらすと

$$x=11+13t,y=14+17t(t\text{は整数})$$

(検算:$17(11+13t)-13(14+17t)=187+221t-182-221t=5$。$t$ によらず成立。)

まとめ:$1$ 次不定方程式は「特殊解 $1$ つ + 周期」。特殊解は合同式(片方の文字を消す)で速く出る。一般解の周期は係数を入れかえた $x=x_0+bt,y=y_0+at$ で、$t$ を動かすとすべての解が得られる。

発展 — 一歩先へ。 $ax+by=c$ が整数解をもつ $⟺$ $\gcd (a,b)\mid c$。解があるとき、特殊解 $+$ 周期(周期は $\frac{b}{\gcd },\frac{a}{\gcd }$)ですべて表せる。互除法・合同式・不定方程式は同じ理論の $3$ つの顔で、暗号(RSA)の鍵計算でも逆数を求める同じ計算が使われる。

別解

別解 — ユークリッドの互除法で特殊解を作る(苦手な人にも確実なルート)。 合同式でなく、互除法で $\gcd (17,13)$ を求める過程を逆にたどって特殊解を作る。

$$17=13\cdot 1+4,13=4\cdot 3+1.$$

$\gcd =1$ で、$5$ は割り切れるから解がある。$1$ を作る式を逆算: $1=13-4\cdot 3=13-(17-13)\cdot 3=13\cdot 4-17\cdot 3$。すなわち $17\cdot (-3)+13\cdot 4=1$。

両辺を $5$ 倍: $17\cdot (-15)+13\cdot 20=5$、つまり $17\cdot (-15)-13\cdot (-20)=5$。特殊解 $(x,y)=(-15,-20)$。

一般解は $x=-15+13t$、$y=-20+17t$。$t=2$ とすると $(x,y)=(11,14)$ で、本解の形と一致する(特殊解の取り方が違うだけで、同じ解の集合)。

合同式(本解)は逆数を見つければ速いが、互除法は「$\gcd$ を求める計算をそのまま逆にたどる」ので、どんな係数でも機械的に特殊解が作れる。互除法と不定方程式は表裏一体だ。