互除法による1次不定方程式の解

方針

解答

⓪ 発想 — どう考え始めるか。 係数が $37$ と $13$ と大きく、特殊解が目で見つからない。こういうときのための道具が互除法だ。

互除法は最大公約数を求める計算だが、その割り算の式を「逆にたどる」と、$37$ と $13$ の組み合わせで $1$ を作る式が組み上がる。それが特殊解になる。

特殊解が1組あれば、全解はそこからのずれ($13$ と $37$ を単位に動く)で書ける。「1組見つける → ずれで全部書く」の2段構成だ。

互除法で割り算を書く。

$$37=2\times 13+11$$ $$13=1\times 11+2$$ $$11=5\times 2+1$$

余りが $1$ になった(だから $\gcd (37,13)=1$ で、解が存在する)。

逆にたどって $1$ を作る。 いちばん下の式から順に、余りを上の式で置きかえていく。

$$1=11-5\times 2$$

$2=13-1\times 11$ を代入して

$$1=11-5(13-11)=6\times 11-5\times 13$$

$11=37-2\times 13$ を代入して

$$1=6(37-2\times 13)-5\times 13=6\times 37-17\times 13$$

よって $x=6$、$y=-17$ が特殊解($37\times 6+13\times (-17)=222-221=1$)。

全部の解を表す。 もとの式と $37\times 6+13\times (-17)=1$ を辺々引くと $37(x-6)+13(y+17)=0$、つまり $37(x-6)=-13(y+17)$。$37$ と $13$ は互いに素なので $x-6=13t$、$y+17=-37t$。

$$x=6+13t,y=-17-37t(t\text{ は整数})$$

発展 — 一歩先へ。 互いに素な $a,b$ に対して $ax+by=1$ に必ず整数解があるという事実は、整数論の土台となる定理である。互除法の逆算は、その解を実際に構成する手続きだ。

右辺が $1$ でなく $c$ の方程式は、特殊解を $c$ 倍すればよい。また「$37x$ を $13$ で割った余りが $1$」という別解の見方は、「$37$ の逆数(のようなもの)が余りの世界に存在する」ことを意味していて、暗号(RSA)の計算にも直結している。

別解

余りの目で見ると、逆算をたどらずに特殊解へ届く道もある。

$37x+13y=1$ で、$13y$ の部分は $13$ で割り切れる。だから「$37x$ を $13$ で割った余りが $1$」になればよい。

$37=13\times 3-2$ だから、$37x$ の余りは $-2x$ の余りと同じ。つまり $-2x$ が($13$ で割って)余り $1$、言いかえると $2x$ が余り $12$ になればよい。

$x=6$ で $2x=12$。ぴったりだ。$x=6$ を元の式に入れて $y=\frac{1-222}{13}=-17$。

特殊解 $(6,-17)$ が、互除法の逆算と同じものが得られた。「片方の項を余りの世界で消す」この見方は、合同式として整理すると本格的な道具になる。大きい係数を小さい余り($37\to -2$)に置き換えるところが威力の源だ。