1次不定方程式の一般解

方針

解答

⓪ 発想 — どう考え始めるか。 係数が $11$ と $8$ 程度なら、特殊解は目で探せる。$11x$ を $1,2,3,\dots$ 倍して、$1$ との差が $8$ の倍数になる瞬間を待てばよい。

$x=3$ で $33$。$33-1=32=8\times 4$。見つかった。$y=-4$ だ。

特殊解から全解へは「ずれ」で書く。$x$ を $8$ 増やすと $11\times 8$ 増える分を、$y$ を $11$ 減らして打ち消す。この交換が解のすべてである。

特殊解を1組見つける。 試すと $x=3$、$y=-4$ が当てはまる($11\times 3+8\times (-4)=33-32=1$)。

全部の解を表す。 もとの式から $11\times 3+8\times (-4)=1$ を辺々引くと

$$11(x-3)+8(y+4)=0\text{すなわち}11(x-3)=-8(y+4)$$

左辺は $11$ の倍数、$11$ と $8$ は互いに素なので、$y+4$ が $11$ の倍数。$y+4=-11t$ とおくと $y=-4-11t$。戻して $11(x-3)=88t$、$x-3=8t$、$x=3+8t$。

$$x=3+8t,y=-4-11t(t\text{ は整数})$$

(ずれ幅は、$x$ が $y$ の係数 $8$、$y$ が $x$ の係数 $11$。係数がそのまま入れかわる。)

発展 — 一歩先へ。 「解のずれが $(+8,-11)$ の倍数に限る」ことの根拠には、$8$ と $11$ が互いに素であることが効いている。互いに素でない係数(例: $6x+4y=1$)では、そもそも解が存在しない(左辺は必ず偶数)。解の存在条件は「右辺が最大公約数の倍数」だ。

別解の「係数つぶし」は、変数の置き換えを繰り返して係数を互除法の要領で縮める方法で、どんなに大きい係数でも確実に特殊解へ着く。手品のような逆算が苦手なら、こちらを主砲にしてよい。

別解

目で見つからないときのために、「係数を小さくつぶす」機械的な方法も知っておくとよい。

$11=8+3$ に注目して、$11x+8y=3x+8(x+y)$ と書き直す。$u=x+y$ と置けば

$$3x+8u=1$$

係数が $(11,8)$ から $(3,8)$ に縮んだ。この式なら $x=3,u=-1$ が見える($9-8=1$)。

$u=x+y=-1$ だから $y=-1-3=-4$。特殊解 $(3,-4)$ が復元できた。

まだ大きければ、同じ置き換えを繰り返して係数をどんどん縮めればよい。実はこれ、互除法の逆算と同じ計算を「前向きに」やっている。どんな係数でも必ず終わる、安心の避難路だ。