拡張されたユークリッドの互除法を筆算で行う方法

拡張されたユークリッドの互除法

拡張されたユークリッドの互除法とは不定方程式

$$ax+by=gcd(a,b)a,b,x,y∈Z ax + by = \text{gcd}(a, b) \quad a,b,x,y \in \mathbb{Z}$$

の解（の１つ）を求めるアルゴリズムで、これをプログラミング言語で実装する方法はあちこちで解説されています。この記事では筆算を使って拡張されたユークリッドの互除法による解を求めてみましょう。

例 1

$11x+7y=111x + 7y = 1$ の解を求めます。

まず 11/7 と書きます。これは $11÷711 \div 7$ を計算することを表します。

割り算
11/7

次に $11÷711 \div 7$ を計算し、商と余りを求めます。奇妙な記法ですが、ここでは 余り..商 の順で書きます。

割り算	余り..商
11/7	4..1

次の行では前の行の除数（$77$）を前の行の余り（$44$）で割ります。

割り算	余り..商
11/7	4..1
7/4

記述的には「前の行を左にシフト」と覚えるとわかりやすいです。この例では $1111$ が左に押し出されて消え、$77$ を被除数の位置に、余りの $44$ を除数の位置に移動します。

$7÷47 \div 4$ を計算します（$11$ 余り $33$）。

割り算	余り..商
11/7	4..1
7/4	3..1

以上のステップを余りが $00$ になるまで繰り返します。

割り算	余り..商
11/7	4..1
7/4	3..1
4/3	1..1
3/1	0..3

右側に２カラム増設し、１行目の右側が□になるように市松に塗ります。

割り算	余り..商	$xx$	$yy$
11/7	4..1		□
7/4	3..1	□
4/3	1..1		□
3/1	0..3	□

一番下の□に $11$ を入れます。

割り算	余り..商	$xx$	$yy$
11/7	4..1		□
7/4	3..1	□
4/3	1..1		□
3/1	0..3	1

下から２行目の□に、「□の斜め下の数」 $×\times$ 「□と同一行の商」を入れます。この場合は $1×1=11 \times 1 = 1$ です。

割り算	余り..商	$xx$	$yy$
11/7	4..1		□
7/4	3..1	□
4/3	1..1		1
3/1	0..3	1

上から２行目の□には、「□の真下^[1]の数」 $++$ 「□の斜め下の数」 $×\times$ 「□と同一行の商」を入れます。この場合は $1+1×1=21 + 1 \times 1 = 2$ です。

割り算	余り..商	$xx$	$yy$
11/7	4..1		□
7/4	3..1	2
4/3	1..1		1
3/1	0..3	1

このステップを１行目まで繰り返します。今回の場合の１行目の□は $1+2×1=31 + 2 \times 1 = 3$ です。

割り算	余り..商	$xx$	$yy$
11/7	4..1		3
7/4	3..1	2
4/3	1..1		1
3/1	0..3	1

最後に、下から２行目の□に入れた数値にマイナスをつけ、その数値と同じカラムにある全ての数値にもマイナスをつけます。

割り算	余り..商	$xx$	$yy$
11/7	4..1		-3
7/4	3..1	2
4/3	1..1		-1
3/1	0..3	1

１行目と２行目の□に入れた数が解（の１つ）です。

今回の例の $11x+7y=111x + 7y = 1$ の解は $(x,y)=(2,−3)(x, y) = (2, -3)$ となります。

（説明のために表をたくさん載せていますが、実際に計算する場合には表は１枚で済みます）

例 2

$111x+30y=3111x + 30y = 3$

↓

割り算	余り..商
111/30	21..3
30/21	9..1
21/9	3..2
9/3	0..3

↓

111/30	21..3		□
30/21	9..1	□
21/9	3..2		□
9/3	0..3	□

↓

111/30	21..3		11 ($=2+3×3=2+3\times3$)
30/21	9..1	3 ($=1+2×1=1+2\times1$)
21/9	3..2		2 ($=1×2=1\times2$)
9/3	0..3	1

↓

111/30	21..3		-11
30/21	9..1	3
21/9	3..2		-2
9/3	0..3	1

$111x+30y=3111x + 30y = 3$ の解は $(x,y)=(3,−11)(x, y) = (3, -11)$ となります。

負数の扱い

$a,ba, b$ が負数の場合は、$∣a∣,∣b∣|a|, |b|$ を用いて解を求め、$aa$ が負数の場合は $xx$ の解の符号を逆転し、$bb$ が負数の場合は $yy$ の解の符号を逆転します。

筆算を使わないやり方

$11x+7y=111x + 7y = 1$ について、筆算を使わないやり方を示します。

筆算と同様の互除法のテーブルを作ります。余り..商 ではなく通常順の 商..余り で書き直してあります。

割り算	商..余り
11/7	1..4
7/4	1..3
4/3	1..1
3/1	3..0

これを元に還元用の式を導出します。

割り算	商..余り	還元式
11/7	1..4	$4=11−1×74 = 11 - 1 \times 7$
7/4	1..3	$3=7−1×43 = 7 - 1 \times 4$
4/3	1..1	$1=4−1×31 = 4 - 1 \times 3$
3/1	3..0

この還元式によって不定方程式の右辺の $11$ を還元していきます。

$$1=4−1×3=4−1×(7−1×4)=−1×7+2×4=−1×7+2×(11−1×7)=2×11−3×7 \begin{aligned} 1 &= 4 - 1 \times 3 \\ &= 4 - 1 \times ( 7 - 1 \times 4 ) \\ &= -1 \times 7 + 2 \times 4 \\ &= -1 \times 7 + 2 \times ( 11 - 1 \times 7 ) \\ &= 2 \times 11 -3 \times 7 \end{aligned}$$

よって $(x,y)=(2,−3)(x, y) = (2, -3)$.

この筆算法の利点

• 覚えやすい。
• 負数の演算を必要としないので、間違えにくい。小学生でも計算できる。

（追記）別の筆算手法

よりよいと思われる筆算法を見つけた^[2]ので、追記します。ただし負数の演算が必要です。

$11x+7y=111x + 7y = 1$ の解を求めます。

以下のように表を作り始めます。

	11	7		備考
$(1)(1)$	1	0	11

この行 $(1)(1)$ は等式 $11×1+7×0=1111 \times 1 + 7 \times 0 = 11$ を表します。

次の行を以下のように追加します。

	11	7		備考
$(1)(1)$	1	0	11	$11×1+7×0=1111\times1+7\times0=11$
$(2)(2)$	0	1	7	$11×0+7×1=711\times0+7\times1=7$

$(1)−(2)×n(1) - (2) \times n$ を行います（この場合 $n=1n=1$）。

	11	7		備考
$(1)(1)$	1	0	11
$(2)(2)$	0	1	7
$(3)(3)$	1	-1	4	$(1)−(2)(1)-(2)$

$(2)−(3)×n(2) - (3) \times n$ を行います（この場合 $n=1n=1$）。

	11	7		備考
$(1)(1)$	1	0	11
$(2)(2)$	0	1	7
$(3)(3)$	1	-1	4	$(1)−(2)(1)-(2)$
$(4)(4)$	-1	2	3	$(2)−(3)(2)-(3)$

$(3)−(4)×n(3) - (4) \times n$ を行います（この場合 $n=1n=1$）。

	11	7		備考
$(1)(1)$	1	0	11
$(2)(2)$	0	1	7
$(3)(3)$	1	-1	4	$(1)−(2)(1)-(2)$
$(4)(4)$	-1	2	3	$(2)−(3)(2)-(3)$
$(5)(5)$	2	-3	1	$(3)−(4)(3)-(4)$

行 $(5)(5)$ は等式 $11×2+7×(−3)=111 \times 2 + 7 \times (-3) = 1$ を表すので $(x,y)=(2,−3)(x,y)=(2,-3)$ となります。

$111x+30y=3111x + 30y = 3$ の解を求めます。

	111	30		備考
$(1)(1)$	1	0	111	$111×1+30×0=111111\times1+30\times0=111$
$(2)(2)$	0	1	30	$111×0+30×1=30111\times0+30\times1=30$

$(1)−(2)×n(1) - (2) \times n$ を行います（この場合 $n=3n=3$）。まず $(2)×3(2) \times 3$ を計算します。

	111	30		備考
$(1)(1)$	1	0	111
$(2)(2)$	0	1	30
$(3)(3)$	0	3	90	$(2)×3(2) \times 3$

次に $(1)−(3)(1) - (3)$ を計算します。

	111	30		備考
$(1)(1)$	1	0	111
$(2)(2)$	0	1	30
$(3)(3)$	0	3	90	$(2)×3(2) \times 3$
$(4)(4)$	1	-3	21	$(1)−(3)(1) - (3)$

以下同様に和の列に $33$ が出てくるまで続けます。

	111	30		備考
$(1)(1)$	1	0	111
$(2)(2)$	0	1	30
$(3)(3)$	0	3	90	$(2)×3(2) \times 3$
$(4)(4)$	1	-3	21	$(1)−(3)(1) - (3)$
$(5)(5)$	-1	4	9	$(2)−(4)(2) - (4)$
$(6)(6)$	-2	8	18	$(5)×2(5) \times 2$
$(7)(7)$	3	-11	3	$(4)−(6)(4) - (6)$

行 $(7)(7)$ は等式 $111×3+30×(−11)=3111 \times 3 + 30 \times (-11) = 3$ を表すので $(x,y)=(3,−11)(x,y)=(3,-11)$ となります。

慣れると $(3)(3)$ 行目の $(2)×3(2) \times 3$ のような行は省略できるので以下のように簡潔に計算できます。

	111	30		備考
$(1)(1)$	1	0	111
$(2)(2)$	0	1	30
$(3)(3)$	1	-3	21	$(1)−(2)×3(1) - (2) \times 3$
$(4)(4)$	-1	4	9	$(2)−(3)(2) - (3)$
$(5)(5)$	3	-11	3	$(3)−(4)×2(3) - (4) \times 2$

この筆算法の利点

• 各行が $a×x+b×y=ca \times x + b \times y = c$ を表しているだけなので理論的に覚えやすい（忘れても思い出しやすい）
• また、引き算の順序を多少間違えても間違った等式を導出するわけではないので、迂遠ながらも最終行にたどり着くことは容易です。
• 負数の場合も、行が $a×x+b×y=ca \times x + b \times y = c$ を表していることを覚えてさえいれば、１行目２行目の初期値の正負を理論的にいじれば良いだけです。

例えば $111x−30y=3111x - 30y = 3$ を計算するなら、初期テーブルは以下のようになります。

	111	-30		備考
$(1)(1)$	1	0	111	$111×1+(−30)×0=111111\times1+(-30)\times0=111$
$(2)(2)$	0	-1	30	$111×0+(−30)×(−1)=30111\times0+(-30)\times(-1)=30$

続けて計算を続ければ以下のようになります。

	111	-30		備考
$(1)(1)$	1	0	111
$(2)(2)$	0	-1	30
$(3)(3)$	1	3	21	$(1)−(2)×3(1) - (2) \times 3$
$(4)(4)$	-1	-4	9	$(2)−(3)(2) - (3)$
$(5)(5)$	3	11	3	$(3)−(4)×2(3) - (4) \times 2$

脚注

1. ２行下

2. 拡張ユークリッド互除法（２）計算の仕組み - YouTube