拡張Euclidの互除法

同義語：拡張Euclid互除法拡張ユークリッドの互除法extended Euclidean algorithm

概要

前提知識: 整数, 最大公約数, Euclidの互除法, Bézoutの等式

$240x+46y=2$ を満たす整数 $x,y$ を探してみる。$240$ と $46$ の最大公約数は $2$ なので、Bézoutの等式によりそのような $x,y$ は存在するが、当てずっぽうではなかなか見つからない。そこでEuclidの互除法の割り算を行いながら、各段の余りが $240$ と $46$ を何倍して足したものかを横に記録していく。
$$ \begin{aligned} 10&=240-5\cdot46&&=240\cdot1+46\cdot(-5),\\ 6&=46-4\cdot10&&=240\cdot(-4)+46\cdot21,\\ 4&=10-1\cdot6&&=240\cdot5+46\cdot(-26),\\ 2&=6-1\cdot4&&=240\cdot(-9)+46\cdot47. \end{aligned} $$
右の列の係数は、1 つ前と 2 つ前の係数から左の式と同じ引き算で求まる（たとえば $21=1-4\cdot(-5)$）。最後の行から $240\cdot(-9)+46\cdot47=-2160+2162=2$ であり、$(x,y)=(-9,47)$ が答である。次の段 $4=2\cdot2+0$ で互除法は止まる。
このように、互除法の各段で余りを 2 つの入力の整数係数の和として記録し、最大公約数 $d$ と $ax+by=d$ を満たす係数 $x,y$ を同時に求める手続きを 拡張Euclidの互除法 という。記録は 1 段ごとに掛け算と引き算を 2 回増やすだけなので、互除法とほぼ同じ手間で済む。得られる係数は小さく（上の例では $|x|=9\le46/(2\cdot2)$）、合同式の法での逆元、一次合同式や一次不定方程式の解、中国剰余定理の解の構成、RSA暗号の鍵の計算に使われる。

定義

以下、$a\ge b>0$ を整数とし、Euclidの互除法の記事の定義「互除法の手続き」の記号を使う。すなわち $r_0:=a$、$r_1:=b$ とおき、$r_i\neq0$ である限り $r_{i-1}=q_ir_i+r_{i+1}$（$0\le r_{i+1}< r_i$）で商 $q_i$ と余り $r_{i+1}$ を定め、初めて $r_{n+1}=0$ となる $n\ge1$ で止める。$r_n=\gcd(a,b)$ である（同記事の定理「互除法の停止と正しさ」）。$a\ge b$ なので $q_1\ge1$ であり、$i\ge2$ でも $r_{i-1}>r_i$ から $q_i\ge1$ である。

拡張互除法の手続き

上の記号のもとで
$$ (s_0,t_0):=(1,0),\qquad(s_1,t_1):=(0,1),\qquad s_{i+1}:=s_{i-1}-q_is_i,\quad t_{i+1}:=t_{i-1}-q_it_i\quad(1\le i\le n) $$
と定め、$(d,x,y):=(r_n,s_n,t_n)$ を出力する手続きを 拡張Euclidの互除法（extended Euclidean algorithm）という。$s_i,t_i$ を $i$ 段目の係数という。

一般の整数の組 $(a,b)$（少なくとも一方は $0$ でない）は、この場合に帰着する。$\gcd(a,b)=\gcd(|a|,|b|)$ なので、$|a|\ge|b|$ となるよう順序を入れ替えて $(|a|,|b|)$ に適用し、得た係数の符号を $a,b$ の符号に合わせて付け替えればよい。$b=0$ なら割り算をせずに $a\cdot(\pm1)+0\cdot0=|a|$ とする。係数の漸化式は Bézoutの等式の記事の命題「互除法による係数の計算」、Euclidの互除法の記事の命題「拡張互除法の係数」と同じものであり、そこでは $a< b$ も許して $r_i=as_i+bt_i$ と $s_it_{i+1}-t_is_{i+1}=(-1)^i$、最後の係数 $(s_{n+1},t_{n+1})=\pm(b/d,\,-a/d)$ が示されている。本記事では $a\ge b>0$ に限り、これらを行列の形で見直したうえで、係数の符号と大きさ、連分数との関係、応用を扱う。

直感

互除法の 1 段 $r_{i+1}=r_{i-1}-q_ir_i$ は、「2 つ前の余りから 1 つ前の余りを $q_i$ 回引く」操作である。余り $r_{i-1},r_i$ がそれぞれ $a,b$ の整数係数の和で書けていれば、同じ操作を係数に施すと $r_{i+1}$ の係数が得られる。つまり拡張互除法は、余りと一緒に「その余りの作り方」を持ち運ぶ手続きである。最初の 2 つ $r_0=a=a\cdot1+b\cdot0$、$r_1=b=a\cdot0+b\cdot1$ の作り方は明らかなので、最後の $0$ でない余り $d$ の作り方も分かる。
幾何的に見ると、$ax+by=d$ の整数解 $(x,y)$ は平面の直線上に等間隔に並ぶ格子点である。拡張互除法が返すのは、その中で原点に近いものである（cor-ext-euclid-minimal。Crisman は、この解が原点に最も近いという S. A. Rankin の指摘を紹介している。Cri24 §3.2、p. 26）。

例と反例

法 97 での 38 の逆元

$a=97$、$b=38$ に拡張互除法を施すと次の表を得る。

$i$	$r_i$	$q_i$	$s_i$	$t_i$
$0$	$97$		$1$	$0$
$1$	$38$	$2$	$0$	$1$
$2$	$21$	$1$	$1$	$-2$
$3$	$17$	$1$	$-1$	$3$
$4$	$4$	$4$	$2$	$-5$
$5$	$1$	$4$	$-9$	$23$
$6$	$0$		$38$	$-97$

$97\cdot(-9)+38\cdot23=-873+874=1$ なので $38\cdot23\equiv1\pmod{97}$ であり、法 $97$ での $38$ の逆元は $23$ である（$38\cdot23=874=9\cdot97+1$）。逆元だけが目的なら、$b$ の係数 $t_i$ の列だけを計算すればよい。最後の行 $(38,-97)$ は $(b/d,-a/d)$ に等しい（thm-ext-euclid-size の 3）。

反例：逆元をもたない場合

$a=123$、$b=45$ に拡張互除法を施すと、余りは $123,45,33,12,9,3,0$、商は $2,1,2,1,3$ で、$123\cdot(-4)+45\cdot11=-492+495=3$ を得る。最大公約数が $3\neq1$ なので、$45x\equiv1\pmod{123}$ には解がない。実際、解 $x$ があれば $45x-1$ は $123$ の、したがって $3$ の倍数となるが、$45x$ は $3$ の倍数なので $-1$ が $3$ の倍数となり矛盾する。この例は「$\gcd(b,a)=1$」という仮定を破っており、「どの $b$ も法 $a$ で逆元をもつ」という含意を破る。ただし出力は無駄にならず、一次合同式 $45x\equiv c\pmod{123}$ が $3\mid c$ のときに解けることを示す（prop-ext-euclid-congruence の後の例）。

反例：割り算が 1 回の場合の係数の大きさ

$a=b=4$ では、$4=1\cdot4+0$ で $n=1$ であり、出力は $(d,x,y)=(4,s_1,t_1)=(4,0,1)$ である。このとき $|y|=1$ は $a/(2d)=1/2$ より大きい。$a=6$、$b=3$ でも $6=2\cdot3+0$ で $n=1$、$(x,y)=(0,1)$ となり、$|y|=1$ は $a/(2d)=1$ 未満ではない。これは thm-ext-euclid-size の 4 の仮定「$n\ge2$」を破る例であり、「出力はいつも $|y|< a/(2d)$ を満たす」という含意は成り立たない。$n=1$ となるのは $b\mid a$ のときで、そのときは $d=b$ で $(x,y)=(0,1)$ が自明な答である。

性質

行列による表示と正しさ

$2\times2$ の整数行列
$$ Q_i:=\begin{pmatrix}0&1\\1&-q_i\end{pmatrix}\quad(1\le i\le n),\qquad M_i:=\begin{pmatrix}s_i&t_i\\ s_{i+1}&t_{i+1}\end{pmatrix}\quad(0\le i\le n) $$
を考える。$Q_i$ を縦ベクトル $(u,v)^{\mathsf T}$ に掛けると $(v,\,u-q_iv)^{\mathsf T}$ になる。

拡張互除法の行列表示

$0\le i\le n$ について次が成り立つ。

$M_i=Q_iQ_{i-1}\cdots Q_1$ である（$i=0$ では単位行列）。
$M_i\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}r_i\\r_{i+1}\end{pmatrix}$、すなわち $as_i+bt_i=r_i$、$as_{i+1}+bt_{i+1}=r_{i+1}$ である。
$\det M_i=s_it_{i+1}-t_is_{i+1}=(-1)^i$ である。
特に $as_n+bt_n=r_n=\gcd(a,b)$ であり、拡張Euclidの互除法の出力 $(d,x,y)$ は $d=\gcd(a,b)$、$ax+by=d$ を満たす。

1 段ずつ行列を掛ける

1 を $i$ に関する帰納法で示す。$M_0=\begin{pmatrix}1&0\\0&1\end{pmatrix}$ である。$1\le i\le n$ で $M_{i-1}=Q_{i-1}\cdots Q_1$ とすると
$$ Q_iM_{i-1}=\begin{pmatrix}0&1\\1&-q_i\end{pmatrix}\begin{pmatrix}s_{i-1}&t_{i-1}\\ s_i&t_i\end{pmatrix}=\begin{pmatrix}s_i&t_i\\ s_{i-1}-q_is_i&t_{i-1}-q_it_i\end{pmatrix}=M_i $$
である。
2 も同じ帰納法による。$i=0$ では $(a,b)^{\mathsf T}=(r_0,r_1)^{\mathsf T}$ である。$M_{i-1}(a,b)^{\mathsf T}=(r_{i-1},r_i)^{\mathsf T}$ なら、1 から
$$ M_i\begin{pmatrix}a\\b\end{pmatrix}=Q_i\begin{pmatrix}r_{i-1}\\r_i\end{pmatrix}=\begin{pmatrix}r_i\\r_{i-1}-q_ir_i\end{pmatrix}=\begin{pmatrix}r_i\\r_{i+1}\end{pmatrix} $$
である。
3 は、$\det Q_i=0\cdot(-q_i)-1\cdot1=-1$ と行列式の乗法性から、1 により $\det M_i=(-1)^i$ である。最後の主張は 2 を $i=n$ に使い、$r_n=\gcd(a,b)$ を合わせたものである。$\square$

3 から、$s_i$ と $t_i$ の公約数は $(-1)^i$ を割り切るので、各 $i$ で $s_i,t_i$ は互いに素である。また $M_i$ の逆行列も整数行列であり、$(a,b)^{\mathsf T}=M_i^{-1}(r_i,r_{i+1})^{\mathsf T}$ と、逆に入力を余りから復元できる。これは互除法の各段で公約数全体が変わらないことの行列による言い換えである。

係数の符号と大きさ

拡張互除法の係数の符号と大きさ

$a\ge b>0$、$d:=\gcd(a,b)$ とし、拡張Euclidの互除法の記号を使う。

$0\le i\le n$ について $t_it_{i+1}\le0$ かつ $|t_i|\le|t_{i+1}|$ である。$1\le i\le n$ について $s_is_{i+1}\le0$ かつ $|s_i|\le|s_{i+1}|$ である。
$1\le i\le n+1$ について
$$ |t_i|\,r_{i-1}+|t_{i-1}|\,r_i=a,\qquad |s_i|\,r_{i-1}+|s_{i-1}|\,r_i=b $$
である。特に $|t_i|\le a/r_{i-1}$、$|s_i|\le b/r_{i-1}$ である。
$(s_{n+1},t_{n+1})=\pm(b/d,\,-a/d)$ である（Euclidの互除法の記事の命題「拡張互除法の係数」の 3。ここでは 2 から導く）。
$n\ge2$ ならば、出力 $(x,y)=(s_n,t_n)$ は $|x|\le\dfrac{b}{2d}$、$|y|<\dfrac{a}{2d}$ を満たす。

符号の交代と行列式

$t$ について $i$ に関する帰納法で示す。$i=0$ では $t_0t_1=0$、$|t_0|=0\le1=|t_1|$ である。$1\le i\le n$ で $t_{i-1}t_i\le0$、$|t_{i-1}|\le|t_i|$ とする。$t_{i+1}=t_{i-1}-q_it_i$ で、$t_{i-1}$ と $-q_it_i$ は同じ符号をもつか一方が $0$ なので（$q_i\ge1$）、$|t_{i+1}|=|t_{i-1}|+q_i|t_i|\ge|t_i|$ であり、$t_i\neq0$ なら $t_{i+1}$ の符号は $t_i$ と逆である（$t_i=0$ となるのは $i=0$ だけである）。よって $t_it_{i+1}\le0$ である。$s$ については $s_1=0$、$s_2=s_0-q_1s_1=1$ から始めて同じ議論を $i\ge2$ について行う。
prop-ext-euclid-matrix の 2 と 3 を使うと
$$ t_ir_{i-1}-t_{i-1}r_i=t_i(as_{i-1}+bt_{i-1})-t_{i-1}(as_i+bt_i)=a(s_{i-1}t_i-t_{i-1}s_i)=(-1)^{i-1}a $$
である。1 により $t_i$ と $t_{i-1}$ は逆符号か一方が $0$ であり、$r_{i-1},r_i\ge0$ なので、左辺の絶対値は $|t_i|r_{i-1}+|t_{i-1}|r_i$ に等しい。よって 1 つ目の等式を得る。2 つ目は同様に $s_ir_{i-1}-s_{i-1}r_i=b(s_it_{i-1}-t_is_{i-1})=(-1)^ib$ と、$s_i,s_{i-1}$ が逆符号か一方が $0$ であること（$i=1$ では $s_1=0$）から従う。$r_i\ge0$ なので不等式も従う。
2 を $i=n+1$ に使うと、$r_n=d$、$r_{n+1}=0$ なので $|t_{n+1}|d=a$、$|s_{n+1}|d=b$ である。prop-ext-euclid-matrix の 2 から $as_{n+1}+bt_{n+1}=r_{n+1}=0$ なので $s_{n+1}$ と $t_{n+1}$ は逆符号であり（$a,b>0$、どちらも $0$ でない）、$(s_{n+1},t_{n+1})=\pm(b/d,-a/d)$ である。
$n\ge2$ とする。$r_{n-1}>r_n=d$ であり、$r_{n-1}=q_nr_n+0$ なので $q_n\ge2$、すなわち $r_{n-1}\ge2d$ である。2 を $i=n$ に使うと $|s_n|r_{n-1}\le b$ なので $|s_n|\le b/(2d)$ である。また 1 により $|t_{n-1}|\ge|t_1|=1$ なので、$|t_n|r_{n-1}=a-|t_{n-1}|d\le a-d< a$ となり、$|t_n|< a/r_{n-1}\le a/(2d)$ である。$\square$

2 は、互除法が進んで余り $r_{i-1}$ が小さくなるにつれて係数が大きくなり、両者の積がほぼ一定（$a$ または $b$ 以下）に保たれることを述べている。冒頭の例では $(r_{i-1},|t_i|)=(240,1),(46,5),(10,21),(6,26),(4,47)$ であり、$|t_i|r_{i-1}+|t_{i-1}|r_i$ はすべて $240$ である（たとえば $47\cdot4+26\cdot2=240$）。係数が $a,b$ を超えないので、計算の途中で数が大きくなりすぎることはなく、全体の計算量は $a,b$ のビット長の積の程度に収まる（Sho08 Theorem 4.4、p. 80）。

出力は絶対値の最も小さい係数

$a\ge b>0$、$d=\gcd(a,b)$ とし、拡張互除法の割り算の回数 $n$ が $2$ 以上とする。$ax+by=d$ を満たす整数の組 $(x,y)$ 全体のうちで、出力 $(s_n,t_n)$ は $|x|$ を最小にし、$|y|$ も最小にする。$|y|$ を最小にする組はこれだけである。

解の全体と比べる

Bézoutの等式の記事の命題「Bézout係数の全体」により、解の全体は $(x,y)=(s_n+kb/d,\ t_n-ka/d)$（$k\in\mathbb{Z}$）である。$k\neq0$ なら、thm-ext-euclid-size の 4 により
$$ |s_n+kb/d|\ge|k|\frac bd-|s_n|\ge\frac bd-\frac b{2d}=\frac b{2d}\ge|s_n|,\qquad |t_n-ka/d|\ge\frac ad-|t_n|>\frac ad-\frac a{2d}=\frac a{2d}>|t_n| $$
である。$\square$

$|x|$ の最小は一意とは限らない。$a=5$、$b=2$ では $5=2\cdot2+1$、$2=2\cdot1$ で $n=2$、出力は $(x,y)=(1,-2)$ であるが、$(x,y)=(-1,3)$ も $5x+2y=1$ を満たし $|x|=1=b/(2d)$ である。

連分数との関係

有理数 $a/b$ の連分数展開は、互除法の商をそのまま並べた $a/b=[q_1;q_2,\dots,q_n]$ である（連分数の記事の定理「有理数の連分数展開」）。ここで記号の衝突を避けるため、$[q_1;q_2,\dots,q_{k+1}]$ を既約分数で表したもの（$k$ 番目の収束子）を $P_k/R_k$ と書く（連分数の記事の $p_k/q_k$）。$P_{-1}=1$、$R_{-1}=0$、$P_0=q_1$、$R_0=1$、$P_k=q_{k+1}P_{k-1}+P_{k-2}$、$R_k=q_{k+1}R_{k-1}+R_{k-2}$ である。

係数と収束子

$2\le i\le n+1$ について $|t_i|=P_{i-2}$、$|s_i|=R_{i-2}$ である。特に $\left|\dfrac{t_i}{s_i}\right|=\dfrac{P_{i-2}}{R_{i-2}}$ は $a/b$ の収束子であり、$|t_{n+1}|/|s_{n+1}|=(a/d)/(b/d)$ は $a/b$ を既約分数で表したものである。

同じ漸化式を満たすこと

thm-ext-euclid-size の 1 の証明で見たとおり、$1\le i\le n$ について $|t_{i+1}|=q_i|t_i|+|t_{i-1}|$、$2\le i\le n$ について $|s_{i+1}|=q_i|s_i|+|s_{i-1}|$ である。また $|t_1|=1=P_{-1}$、$|t_2|=|{-q_1}|=q_1=P_0$、$|s_1|=0=R_{-1}$、$|s_2|=1=R_0$ である。$|t_{i+1}|$ と $P_{i-1}$ は同じ漸化式 $u_{i+1}=q_iu_i+u_{i-1}$ を満たし、最初の 2 項が一致するので、帰納法によりすべて一致する。$|s_i|$ と $R_{i-2}$ も同様である。最後の主張は thm-ext-euclid-size の 3 による。$\square$

冒頭の例では $240/46=120/23=[5;4,1,1,2]$ で、収束子は $5,\ \frac{21}4,\ \frac{26}5,\ \frac{47}9,\ \frac{120}{23}$ であり、表の $(|t_i|,|s_i|)=(5,1),(21,4),(26,5),(47,9),(120,23)$（$i=2,\dots,6$）と一致する。prop-ext-euclid-matrix の 3 は、連分数の隣り合う収束子の関係 $p_kq_{k-1}-p_{k-1}q_k=\pm1$（連分数の記事の命題「隣り合う収束子の行列式」）と同じものである。

応用

一次合同式と逆元

一次合同式の解法

$m\ge2$ を整数、$a,c$ を整数とし、$d:=\gcd(a,m)$ とする。拡張互除法などで $as+mt=d$ となる整数 $s,t$ をとる。

合同式 $ax\equiv c\pmod m$ が解をもつことと $d\mid c$ は同値である。
$d\mid c$ のとき、$x_0:=s\cdot(c/d)$ は解であり、解の全体は $x\equiv x_0\pmod{m/d}$ を満たす整数全体である。特に $0\le x< m$ の範囲にちょうど $d$ 個の解がある。
特に $\gcd(a,m)=1$ なら、$s$ は法 $m$ での $a$ の逆元である（$as\equiv1\pmod m$）。

係数を $\frac{c}{d}$ 倍する

解 $x$ があれば $ax-c=mk$ と書け、$d\mid a$、$d\mid m$ から $d\mid c$ である。
$d\mid c$ とする。$as+mt=d$ に $c/d$ を掛けると $a\,x_0+m\,t(c/d)=c$ なので $ax_0\equiv c\pmod m$ である。$x$ を任意の解とすると $a(x-x_0)\equiv0\pmod m$、すなわち $m\mid a(x-x_0)$ である。$d$ で割って $(m/d)\mid(a/d)(x-x_0)$ となり、$as+mt=d$ を $d$ で割った $(a/d)s+(m/d)t=1$ から $a/d$ と $m/d$ は互いに素なので、$(m/d)\mid x-x_0$ である（互いに素の記事の命題「互いに素な因子の消去」）。逆に $x\equiv x_0\pmod{m/d}$ なら $a(x-x_0)=d(a/d)(x-x_0)$ は $d\cdot(m/d)=m$ の倍数なので $x$ は解である。$0\le x< m$ の中で $m/d$ を法とする 1 つの剰余類に属するものは $d$ 個ある。
2 の $d=1$、$c=1$ の場合で $x_0=s$ である。$\square$

ex-ext-euclid-no-inverse の $123\cdot(-4)+45\cdot11=3$ を使うと、$45x\equiv12\pmod{123}$ は $3\mid12$ なので解けて、$x_0=11\cdot4=44$、解の全体は $x\equiv44\equiv3\pmod{41}$、法 $123$ では $x\equiv3,44,85$ の 3 個である（$45\cdot3=135=123+12$）。

一次不定方程式と連立合同式

$0$ でない整数 $a,b$ と整数 $c$ について、$ax+by=c$ の整数解は $d=\gcd(a,b)$ が $c$ を割り切るときに限って存在し、解の全体は 1 つの解から $(x+kb/d,\ y-ka/d)$ で得られる（Bézoutの等式の記事の命題「Bézout係数の全体」）。拡張互除法はその 1 つの解を与える。冒頭の $240\cdot(-9)+46\cdot47=2$ を $5$ 倍すると $240x+46y=10$ の解 $(-45,235)$ が得られ、$k=2$ とずらすと $(1,-5)$、すなわち $240-230=10$ という小さな解になる。
法 $m_1,m_2$ が互いに素なら、$m_1s+m_2t=1$ となる $s,t$ から、連立合同式 $x\equiv c_1\pmod{m_1}$、$x\equiv c_2\pmod{m_2}$ の解 $x=c_2\,m_1s+c_1\,m_2t$ が得られる（$m_1s\equiv0\pmod{m_1}$、$m_1s\equiv1\pmod{m_2}$ などによる。中国剰余定理の記事の証明と同じ構成）。たとえば $61\cdot(-5)+17\cdot18=1$ から、$x\equiv5\pmod{61}$、$x\equiv1\pmod{17}$ の解は $x=1\cdot61\cdot(-5)+5\cdot17\cdot18=1225\equiv188\pmod{1037}$ である（$188=3\cdot61+5=11\cdot17+1$）。法が互いに素でない場合は中国剰余定理の記事の命題「2 つの合同式の可解条件」にある。

多項式の場合

体 $K$ 上の多項式環 $K[x]$ では、次数を下げる割り算（除法の原理）ができるので、同じ手続きで最大公約多項式 $d(x)$ と $f(x)u(x)+g(x)v(x)=d(x)$ を満たす $u,v$ が求まる。係数の漸化式も行列による議論もそのまま通る。

位数 8 の有限体での逆元

$\mathbb{F}_2=\{0,1\}$ 上で $f(x)=x^3+x+1$ は根をもたない 3 次式なので既約多項式であり、$\mathbb{F}_2[x]/(f)$ は 8 個の元からなる有限体である。そこでの $x^2$ の逆元を求める。$\mathbb{F}_2$ では $-1=1$ である。
$$ x^3+x+1=x\cdot x^2+(x+1),\qquad x^2=(x+1)\cdot(x+1)+1 $$
（$(x+1)^2=x^2+1$）であり、余りが $1$ になったので最大公約多項式は $1$ である。係数を記録すると $x+1=f-x\cdot x^2$、$1=x^2-(x+1)^2=x^2-(x+1)(f-x\cdot x^2)=x^2\bigl(1+x(x+1)\bigr)-(x+1)f$ なので、$x^2(x^2+x+1)\equiv1\pmod f$ であり、逆元は $x^2+x+1$ である。実際 $x^3\equiv x+1$、$x^4\equiv x^2+x$ を使うと $x^4+x^3+x^2\equiv(x^2+x)+(x+1)+x^2=1$ となる。

係数が体でないと手続きは進まない。$\mathbb{Z}[x]$ の $2$ と $x$ は最大公約元 $1$ をもつが、$2u(x)+xv(x)=1$ となる $u,v$ は存在せず（Bézoutの等式の記事の例「反例：整数係数多項式環の 2 と x」）、実際 $x$ を $2$ で割る割り算ができない。

補足

歴史と文献

互除法を使って一次不定方程式を解く方法は、ヨーロッパでは 17 世紀の Bachet de Méziriac に知られていた（Cri24 の Historical remark 2.4.7、p. 15）。本記事の $a\ge b\ge0$ の形の手続きと、係数の符号の交代・$r_{i-1}|t_i|\le a$・$r_{i-1}|s_i|\le b$ の評価は Sho08 Theorem 4.3（pp. 78–79）にあり、行列による表示も同書 p. 80 に述べられている。逆元の計算への応用は Ste17 Algorithm 2.3.7（p. 33）と Example 2.3.9（p. 34）、余りを逆に代入する計算は Cri24 §2.4（pp. 14–16）を参照。