初等整数論/ユークリッドの互除法

テンプレート:Nav この項目では、最大公約数を求めるアルゴリズムとその応用について述べる。

ユークリッドの互除法

ユークリッドの互除法とは、ユークリッドが自著「原論」に記した、最大公約数を求めるアルゴリズムである。その根幹を成す定理は、次の定理である。

定理 1.7

自然数 a, b が与えられたとき、除法の原理に基づき $a=bq+r$ とすると、$\gcd (a,b)=\gcd (b,r)$

証明
$a=bq+r,(a,b)=g\cdots (0)$ とする。すると仮定より、$a=g{a}^{\prime },b=g{b}^{\prime }\cdots (1)$ となる。このとき、$(a^{\prime },b^{\prime })=1\cdots (2)$ である。なぜなら、仮に$(a^{\prime },b^{\prime })=d>1$ とすると、$a^{\prime }=d{a}^{″},b^{\prime }=d{b}^{″}$ となってこれを (1) に代入すれば $a=gd{a}^{″},b=gd{b}^{″}$ となり、公約数 $gd>g$ が存在することになってしまい、矛盾するからである。

(0) に (1) を代入して、$g{a}^{\prime }=g{b}^{\prime }q+r⟺g(a^{\prime }-b^{\prime }q)=r$ となり、$r$ も $g$ の倍数。したがって、$g$ は $b,r$ の公約数。$\gcd (b,r)=g^{\prime }$ とすると、定理 1.4 より、$g^{\prime }=ge$ となる。よって $g^{\prime }\geqq g.\cdots (3)$

$b=g^{\prime }c,r=g^{\prime }{r}^{\prime }$ とおけば、これを (0) へ代入して、$a=g^{\prime }c+g^{\prime }{r}^{\prime }⟺a=g^{\prime }(c+r^{\prime })$ となり、$a$ も $g^{\prime }$ の倍数。したがって、$g^{\prime }$ は $a,b$ の公約数。したがって定理 1.5 より $g=g^{\prime }{e}^{\prime }$ となる。すなわち $g^{\prime }\leqq g.$ これと (3) によって、$g=g^{\prime }.$ これらの数の定め方から、$\gcd (a,b)=\gcd (b,r).$

例

470 と 364 の最大公約数をユークリッドの互除法を繰り返し用いて求める。

$\begin{array}{cc}470& =364\cdot 1+106\\ 364& =106\cdot 3+46\\ 106& =46\cdot 2+14\\ 46& =14\cdot 3+4\\ 14& =4\cdot 3+2\\ 4& =2\cdot 2\end{array}$

よって最大公約数は 2 であることが分かる。ユークリッドの互除法では、余りの数が着実に 1 減っているので、無限降下列を作ることはできないという自然数の性質から、必ず有限回で終わることが分かる。

これを次は、余りを主体にして書きなおしてみる。

$a=470,b=364$ とおく。

$\begin{array}{cc}106& =a-b\cdot 1\cdots (1)\\ 46& =b-106\cdot 3\cdots (2)\\ 14& =106-46\cdot 2\cdots (3)\\ 4& =46-14\cdot 3\cdots (4)\\ 2& =14-4\cdot 3\cdots (5)\\ 4& =2\cdot 2\cdots (6)\end{array}$

(1) を (2) に代入して、$46=b-(a-b\cdot 1)\cdot 3⟺46=-3a+4b$ これと (1) を (3) に代入して、

$14=(a-b\cdot 1)-(-3a+4b)\cdot 2⟺14=7a-9b$ これと (2) を (4) に代入して、

$4=(-3a+4b)-(7a-9b)\cdot 3⟺4=-24a+31b$ これと (3) を (5) に代入して、

$2=(7a-9b)-(-24a+31b)\cdot 3⟺2=79a-102b$

こうして、470, 364 の 最大公約数である 2 を、$79\cdot 470-102\cdot 364=2$ と表すことができた。

一次不定方程式

先ほど問題を一般化して、次の不定方程式を満たす数を全て求めるということを考える。

$ax+by=c(a\ne 0\wedge b\ne 0)$ が解を持つのはどんな場合か、解はどのように求めるか、を考察してゆく。

まずは証明をする前に、次の定理を証明する。

定理 1.8

$(a,b)=1$ ならば、$a,2a,3a,\cdots ,(b-1)a,ba$ を $b$ で割った余りは全て異なり、任意の余り $r$ についても、$ca$ を $b$ で割ると $r$ 余るような $c$ が存在する。

証明
仮に、この中で同じものがあったとして、それらを $ia,ja(i\ne j\wedge 1\leqq i<j\leqq b)$ とおく。これらの余りは等しいのだから、$b|ia-ja⟺b|a(i-j)$となる。定理 1.6 より、$b|i-j$ だが、$-b<i-j<b$ より、 $i-j=0⟺i=j$ となり、矛盾。よって定理の前半は満たされ、定理の後半は鳩の巣原理によって難なく証明される。

定理 1.9

$(a,b)=g$ としたとき、$ax+by=c$ が解を持つには、$g|c$ が必要十分条件である。

証明
一次不定方程式が解を持っていて、そのうちの一つを $ax+by=c,(a,b)=g$ とし、$a=g{a}^{\prime },b=g{b}^{\prime }$ とする。$ax+by=c⟺g{a}^{\prime }x+g{b}^{\prime }x=c⟺g(a^{\prime }x+b^{\prime }x)=c$ より、$c$ は $g$ の倍数。よって必要条件である。

次に、$g|c$ であるとする。$c=g{c}^{\prime }$ とおく。

すると、$ax+by=c⟺g{a}^{\prime }x+g{b}^{\prime }x=g{c}^{\prime }⟺a^{\prime }x+b^{\prime }y=c^{\prime }\cdots (1)$ となる。

ここで、$a^{\prime },b^{\prime }$ は互いに素である。仮に、$a^{\prime }x+b^{\prime }y=1$ が解を持つならば、両辺を $c^{\prime }$ 倍することで (1) も解を持つ。なので $a^{\prime }x+b^{\prime }y=1$ が解を持つことを証明すれば良い。

定理 1.8 より、$m{a}^{\prime }$ を $b^{\prime }$ で割ると $1$ 余るような $m$ が存在する。（※）

すなわち、$m{a}^{\prime }=b^{\prime }n+1⟺a^{\prime }m+b^{\prime }(-n)=1$ となり、解が存在する。

以上より、十分条件であることが証明され、必要十分条件であることが証明された。

ユークリッドの互除法を使って実際に解を構成することで証明することもできる。詳しくは次節を参照。

（※）について : この時点で正であるとしてしまっているが、負の場合もうまく符号操作することで正の場合に帰着することができるので、大した問題にはならない。

解法

さて、定理 1.9 より、全辺を最大公約数で割れば、係数が互いに素な一次不定方程式に持ち込むことができる。ここで $ax+by=1\wedge (a,b)=1$ に解 $(x,y)=(m,n)$ が存在して、$am+bn=1$ だったとする。ここで、$(x,y)=(m-bk,n+ak)(k\in \mathbb{Z})$ も解である。なぜなら、

$\begin{array}{cc}a(m-bk)+b(n+ak)& =am-abk+bn+abk\\ & =am+bn\\ & =1\end{array}$

となるからである。

逆に、他の解、$(m^{\prime },n^{\prime })$ が存在するとき、$(m^{\prime },n^{\prime })=(m-bk,n+ak)$ という形で書くことができる。なぜなら、

$\{\begin{array}{c}am+bn=1\cdots (1)\\ a{m}^{\prime }+b{n}^{\prime }=1\cdots (2)\end{array}$

$\therefore am+bn=a{m}^{\prime }+b{n}^{\prime }⟺a(m-m^{\prime })=b(n^{\prime }-n)$

したがって、$a|b(n^{\prime }-n)$ となるが、$(a,b)=1$ なので定理 1.6 より、 $a|n^{\prime }-n⟺ak=n^{\prime }-n⟺n^{\prime }=n+ak.$

さらに、(2) へ代入して $a{m}^{\prime }+b(n+ak)=1$ となり、これと (1) から、$am+bn=a{m}^{\prime }+b(n+ak)⟺am=a{m}^{\prime }+abk⟺m=m^{\prime }+bk⟺m^{\prime }=m-bk$

以上より、解を全て決定することができた。それらは、ある解$(x,y)=(m,n)$ があったとき、$(x,y)=(m-bk,n+ak)(k\in \mathbb{Z})$ が全てである。

つまり、問題は、最初の解 $(m,n)$ をいかにして見つけるか、である。

そこで先ほどのユークリッドの互除法を用いた方法を応用する。まずは例として、$248x+105y=1$ の解を求める。ユークリッドの互除法を用いて、

$\begin{array}{ccc}248& =& 105\cdot 2+38\\ 105& =& 38\cdot 2+29\\ 38& =& 29\cdot 1+9\\ 29& =& 9\cdot 3+2\\ 9& =& 2\cdot 4+1\\ \end{array}$

これを余り主体に書き直す。$a=248,b=105$ とおく。

$\begin{array}{ccc}38& =& a-2b\cdots (1)\\ 29& =& b-38\cdot 2\cdots (2)\\ 9& =& 38-29\cdot 1\cdots (3)\\ 2& =& 29-9\cdot 3\cdots (4)\\ 1& =& 9-2\cdot 4\cdots (5)\\ \end{array}$

(1) を (2) に代入して $29=b-2(a-2b)⟺29=-2a+5b$、これと (1) を (3) に代入して、$9=(a-2b)-1(-2a+5b)⟺9=3a-7b$、これと (2) を (4) に代入して、$2=(-2a+5b)-3(3a-7b)⟺2=-11a+26b$、これと (3) を (5) に代入して、$1=(3a-7b)-4(-11a+26b)⟺47a-111b=1$

となって、解が求まった。

今度はこれを一般化して考える。互いに素な2数 $a,b$ が与えられたとき、互除法を用いて、

$\begin{array}{cc}a=& b{q}_1+r_1⟺r_1=b{q}_1-a\cdots (1)\\ b=& r_1{q}_2+r_2⟺r_2=b-r_1{q}_2\cdots (2)\\ r_1=& r_2{q}_3+r_3⟺r_3=r_1-r_2{q}_3\\ & \cdots \\ r_k=& r_{k+1}{q}_{k+2}+1⟺1=r_k-r_{k+1}{q}_{k+2}\\ \end{array}$

ここで、$r_k=x_{k}a+y_{k}b$ とおいてみると、

$\begin{array}{ccc}{r}_{k-2}& =& x_{k-2}a+y_{k-2}b\\ r_{k-1}& =& x_{k-1}a+y_{k-1}b\\ r_k& =& x_{k}a+y_{k}b\end{array}$

となり、これらを、$r_k=r_{k-2}-r_{k-1}{q}_k$ に代入して、

$r_k=(x_{k-2}a+y_{k-2}b)-(x_{k-1}a+y_{k-1}b)q_k⟺r_k=(x_{k-2}-x_{k-1}{q}_k)a+(y_{k-2}-y_{k-1}{q}_k)b$

したがって、 $(x_{k-2}-x_{k-1}{q}_k)a+(y_{k-2}-y_{k-1}{q}_k)b=x_{k}a+y_{k}b$

係数比較（※）して、$x_k=x_{k-2}-x_{k-1}{q}_k,y_k=y_{k-2}-y_{k-1}{q}_k$

初項と第二項は、(1), (2) より$x_1=1,y_1=q_1,x_2=-q_2,y_2=1+q_1{q}_2$

以上の結果をまとめると、

互いに素な二数 $a,b$ について、$ax+by=1$ の方程式の解は、ユークリッドの互除法によって得られる逐次商 $q_1,q_2,\cdots ,q_k$ を用いて、

$x_1=1,y_1=q_1,x_2=-q_2,y_2=1+q_1{q}_2$
$x_k=x_{k-2}-x_{k-1}{q}_k,y_k=y_{k-2}-y_{k-1}{q}_k(k\geqq 3)$

で求められる。

※について : 係数を比較してこの式を導くのではなく、この式が成り立つならば先ほどの式も成り立つのは自明なのでこのように議論を展開しているのである。