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

この項目では、最大公約数を求めるアルゴリズムとその応用について述べる。
ユークリッドの互除法とは、ユークリッドが自著「原論」に記した、最大公約数を求めるアルゴリズムである。その根幹を成す定理は、次の定理である。
証明 a = b q + r , ( a , b ) = g ⋯ ( 0 ) {\displaystyle a=bq+r,(a,b)=g\cdots (0)} とする。すると仮定より、 a = g a ′ , b = g b ′ ⋯ ( 1 ) {\displaystyle a=ga',b=gb'\cdots (1)} となる。このとき、 ( a ′ , b ′ ) = 1 ⋯ ( 2 ) {\displaystyle (a',b')=1\cdots (2)} である。なぜなら、仮に ( a ′ , b ′ ) = d > 1 {\displaystyle (a',b')=d>1} とすると、 a ′ = d a ′′ , b ′ = d b ′′ {\displaystyle a'=da'',b'=db''} となってこれを (1) に代入すれば a = g d a ′′ , b = g d b ′′ {\displaystyle a=gda'',b=gdb''} となり、公約数 g d > g {\displaystyle gd>g} が存在することになってしまい、矛盾するからである。
(0) に (1) を代入して、 g a ′ = g b ′ q + r ⟺ g ( a ′ − b ′ q ) = r {\displaystyle ga'=gb'q+r\iff g(a'-b'q)=r} となり、 r {\displaystyle r} も g {\displaystyle g} の倍数。したがって、 g {\displaystyle g} は b , r {\displaystyle b,r} の公約数。 gcd ( b , r ) = g ′ {\displaystyle \gcd(b,r)=g'} とすると、定理 1.4 より、 g ′ = g e {\displaystyle g'=ge} となる。よって g ′ ≧ g . ⋯ ( 3 ) {\displaystyle g'\geqq g.\cdots (3)}
b = g ′ c , r = g ′ r ′ {\displaystyle b=g'c,r=g'r'} とおけば、これを (0) へ代入して、 a = g ′ c + g ′ r ′ ⟺ a = g ′ ( c + r ′ ) {\displaystyle a=g'c+g'r'\iff a=g'(c+r')} となり、 a {\displaystyle a} も g ′ {\displaystyle g'} の倍数。したがって、 g ′ {\displaystyle g'} は a , b {\displaystyle a,b} の公約数。したがって定理 1.5 より g = g ′ e ′ {\displaystyle g=g'e'} となる。すなわち g ′ ≦ g . {\displaystyle g'\leqq g.} これと (3) によって、 g = g ′ . {\displaystyle g=g'.} これらの数の定め方から、 gcd ( a , b ) = gcd ( b , r ) . {\displaystyle \gcd(a,b)=\gcd(b,r).}
例
470 と 364 の最大公約数をユークリッドの互除法を繰り返し用いて求める。
470 = 364 ⋅ 1 + 106 364 = 106 ⋅ 3 + 46 106 = 46 ⋅ 2 + 14 46 = 14 ⋅ 3 + 4 14 = 4 ⋅ 3 + 2 4 = 2 ⋅ 2 {\displaystyle {\begin{aligned}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{aligned}}}
よって最大公約数は 2 であることが分かる。ユークリッドの互除法では、余りの数が着実に 1 減っているので、無限降下列を作ることはできないという自然数の性質から、必ず有限回で終わることが分かる。
これを次は、余りを主体にして書きなおしてみる。
a = 470 , b = 364 {\displaystyle a=470,b=364} とおく。
106 = a − b ⋅ 1 ⋯ ( 1 ) 46 = b − 106 ⋅ 3 ⋯ ( 2 ) 14 = 106 − 46 ⋅ 2 ⋯ ( 3 ) 4 = 46 − 14 ⋅ 3 ⋯ ( 4 ) 2 = 14 − 4 ⋅ 3 ⋯ ( 5 ) 4 = 2 ⋅ 2 ⋯ ( 6 ) {\displaystyle {\begin{aligned}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{aligned}}}
(1) を (2) に代入して、 46 = b − ( a − b ⋅ 1 ) ⋅ 3 ⟺ 46 = − 3 a + 4 b {\displaystyle 46=b-(a-b\cdot 1)\cdot 3\iff 46=-3a+4b} これと (1) を (3) に代入して、
14 = ( a − b ⋅ 1 ) − ( − 3 a + 4 b ) ⋅ 2 ⟺ 14 = 7 a − 9 b {\displaystyle 14=(a-b\cdot 1)-(-3a+4b)\cdot 2\iff 14=7a-9b} これと (2) を (4) に代入して、
4 = ( − 3 a + 4 b ) − ( 7 a − 9 b ) ⋅ 3 ⟺ 4 = − 24 a + 31 b {\displaystyle 4=(-3a+4b)-(7a-9b)\cdot 3\iff 4=-24a+31b} これと (3) を (5) に代入して、
2 = ( 7 a − 9 b ) − ( − 24 a + 31 b ) ⋅ 3 ⟺ 2 = 79 a − 102 b {\displaystyle 2=(7a-9b)-(-24a+31b)\cdot 3\iff 2=79a-102b}
こうして、470, 364 の 最大公約数である 2 を、 79 ⋅ 470 − 102 ⋅ 364 = 2 {\displaystyle 79\cdot 470-102\cdot 364=2} と表すことができた。
先ほど問題を一般化して、次の不定方程式を満たす数を全て求めるということを考える。
a x + b y = c ( a ≠ 0 ∧ b ≠ 0 ) {\displaystyle ax+by=c\ \ \ (a\neq 0\wedge b\neq 0)} が解を持つのはどんな場合か、解はどのように求めるか、を考察してゆく。
まずは証明をする前に、次の定理を証明する。
( a , b ) = 1 {\displaystyle (a,b)=1} ならば、 a , 2 a , 3 a , ⋯ , ( b − 1 ) a , b a {\displaystyle a,2a,3a,\cdots ,(b-1)a,ba} を b {\displaystyle b} で割った余りは全て異なり、任意の余り r {\displaystyle r} についても、 c a {\displaystyle ca} を b {\displaystyle b} で割ると r {\displaystyle r} 余るような c {\displaystyle c} が存在する。
証明 仮に、この中で同じものがあったとして、それらを i a , j a ( i ≠ j ∧ 1 ≦ i < j ≦ b ) {\displaystyle ia,ja\ \ (i\neq j\,\wedge \,1\leqq i<j\leqq b)} とおく。これらの余りは等しいのだから、 b | i a − j a ⟺ b | a ( i − j ) {\displaystyle b\,|\,ia-ja\iff b\,|\,a(i-j)} となる。定理 1.6 より、 b | i − j {\displaystyle b\,|\,i-j} だが、 − b < i − j < b {\displaystyle -b<i-j<b} より、 i − j = 0 ⟺ i = j {\displaystyle i-j=0\iff i=j} となり、矛盾。よって定理の前半は満たされ、定理の後半は鳩の巣原理によって難なく証明される。
( a , b ) = g {\displaystyle (a,b)=g} としたとき、 a x + b y = c {\displaystyle ax+by=c} が解を持つには、 g | c {\displaystyle g\,|\,c} が必要十分条件である。
証明 一次不定方程式が解を持っていて、そのうちの一つを a x + b y = c , ( a , b ) = g {\displaystyle ax+by=c,(a,b)=g} とし、 a = g a ′ , b = g b ′ {\displaystyle a=ga',b=gb'} とする。 a x + b y = c ⟺ g a ′ x + g b ′ x = c ⟺ g ( a ′ x + b ′ x ) = c {\displaystyle ax+by=c\iff ga'x+gb'x=c\iff g(a'x+b'x)=c} より、 c {\displaystyle c} は g {\displaystyle g} の倍数。よって必要条件である。
次に、 g | c {\displaystyle g\,|\,c} であるとする。 c = g c ′ {\displaystyle c=gc'} とおく。
すると、 a x + b y = c ⟺ g a ′ x + g b ′ x = g c ′ ⟺ a ′ x + b ′ y = c ′ ⋯ ( 1 ) {\displaystyle ax+by=c\iff ga'x+gb'x=gc'\iff a'x+b'y=c'\cdots (1)} となる。
ここで、 a ′ , b ′ {\displaystyle a',b'} は互いに素である。仮に、 a ′ x + b ′ y = 1 {\displaystyle a'x+b'y=1} が解を持つならば、両辺を c ′ {\displaystyle c'} 倍することで (1) も解を持つ。なので a ′ x + b ′ y = 1 {\displaystyle a'x+b'y=1} が解を持つことを証明すれば良い。
定理 1.8 より、 m a ′ {\displaystyle ma'} を b ′ {\displaystyle b'} で割ると 1 {\displaystyle 1} 余るような m {\displaystyle m} が存在する。(※)
すなわち、 m a ′ = b ′ n + 1 ⟺ a ′ m + b ′ ( − n ) = 1 {\displaystyle ma'=b'n+1\iff a'm+b'(-n)=1} となり、解が存在する。
以上より、十分条件であることが証明され、必要十分条件であることが証明された。
ユークリッドの互除法を使って実際に解を構成することで証明することもできる。詳しくは次節を参照。
(※)について : この時点で正であるとしてしまっているが、負の場合もうまく符号操作することで正の場合に帰着することができるので、大した問題にはならない。
さて、定理 1.9 より、全辺を最大公約数で割れば、係数が互いに素な一次不定方程式に持ち込むことができる。ここで a x + b y = 1 ∧ ( a , b ) = 1 {\displaystyle ax+by=1\wedge (a,b)=1} に解 ( x , y ) = ( m , n ) {\displaystyle (x,y)=(m,n)} が存在して、 a m + b n = 1 {\displaystyle am+bn=1} だったとする。ここで、 ( x , y ) = ( m − b k , n + a k ) ( k ∈ Z ) {\displaystyle (x,y)=(m-bk,n+ak)\ \ (k\in \mathbb {Z} )} も解である。なぜなら、
a ( m − b k ) + b ( n + a k ) = a m − a b k + b n + a b k = a m + b n = 1 {\displaystyle {\begin{aligned}a(m-bk)+b(n+ak)&=am-abk+bn+abk\\&=am+bn\\&=1\end{aligned}}}
となるからである。
逆に、他の解、 ( m ′ , n ′ ) {\displaystyle (m',n')} が存在するとき、 ( m ′ , n ′ ) = ( m − b k , n + a k ) {\displaystyle (m',n')=(m-bk,n+ak)} という形で書くことができる。なぜなら、
{ a m + b n = 1 ⋯ ( 1 ) a m ′ + b n ′ = 1 ⋯ ( 2 ) {\displaystyle {\begin{cases}am+bn=1\cdots (1)\\am'+bn'=1\cdots (2)\end{cases}}}
∴ a m + b n = a m ′ + b n ′ ⟺ a ( m − m ′ ) = b ( n ′ − n ) {\displaystyle \therefore am+bn=am'+bn'\iff a(m-m')=b(n'-n)}
したがって、 a | b ( n ′ − n ) {\displaystyle a\,|\,b(n'-n)} となるが、 ( a , b ) = 1 {\displaystyle (a,b)=1} なので定理 1.6 より、 a | n ′ − n ⟺ a k = n ′ − n ⟺ n ′ = n + a k . {\displaystyle a\,|\,n'-n\iff ak=n'-n\iff n'=n+ak.}
さらに、(2) へ代入して a m ′ + b ( n + a k ) = 1 {\displaystyle am'+b(n+ak)=1} となり、これと (1) から、 a m + b n = a m ′ + b ( n + a k ) ⟺ a m = a m ′ + a b k ⟺ m = m ′ + b k ⟺ m ′ = m − b k {\displaystyle am+bn=am'+b(n+ak)\iff am=am'+abk\iff m=m'+bk\iff m'=m-bk}
以上より、解を全て決定することができた。それらは、ある解 ( x , y ) = ( m , n ) {\displaystyle (x,y)=(m,n)} があったとき、 ( x , y ) = ( m − b k , n + a k ) ( k ∈ Z ) {\displaystyle (x,y)=(m-bk,n+ak)\ \ (k\in \mathbb {Z} )} が全てである。
つまり、問題は、最初の解 ( m , n ) {\displaystyle (m,n)} をいかにして見つけるか、である。
そこで先ほどのユークリッドの互除法を用いた方法を応用する。まずは例として、 248 x + 105 y = 1 {\displaystyle 248x+105y=1} の解を求める。ユークリッドの互除法を用いて、
248 = 105 ⋅ 2 + 38 105 = 38 ⋅ 2 + 29 38 = 29 ⋅ 1 + 9 29 = 9 ⋅ 3 + 2 9 = 2 ⋅ 4 + 1 {\displaystyle {\begin{aligned}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{aligned}}}
これを余り主体に書き直す。 a = 248 , b = 105 {\displaystyle a=248,b=105} とおく。
38 = a − 2 b ⋯ ( 1 ) 29 = b − 38 ⋅ 2 ⋯ ( 2 ) 9 = 38 − 29 ⋅ 1 ⋯ ( 3 ) 2 = 29 − 9 ⋅ 3 ⋯ ( 4 ) 1 = 9 − 2 ⋅ 4 ⋯ ( 5 ) {\displaystyle {\begin{aligned}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{aligned}}}
(1) を (2) に代入して 29 = b − 2 ( a − 2 b ) ⟺ 29 = − 2 a + 5 b {\displaystyle 29=b-2(a-2b)\iff 29=-2a+5b} 、これと (1) を (3) に代入して、 9 = ( a − 2 b ) − 1 ( − 2 a + 5 b ) ⟺ 9 = 3 a − 7 b {\displaystyle 9=(a-2b)-1(-2a+5b)\iff 9=3a-7b} 、これと (2) を (4) に代入して、 2 = ( − 2 a + 5 b ) − 3 ( 3 a − 7 b ) ⟺ 2 = − 11 a + 26 b {\displaystyle 2=(-2a+5b)-3(3a-7b)\iff 2=-11a+26b} 、これと (3) を (5) に代入して、 1 = ( 3 a − 7 b ) − 4 ( − 11 a + 26 b ) ⟺ 47 a − 111 b = 1 {\displaystyle 1=(3a-7b)-4(-11a+26b)\iff 47a-111b=1}
となって、解が求まった。
今度はこれを一般化して考える。互いに素な2数 a , b {\displaystyle a,b} が与えられたとき、互除法を用いて、
a = b q 1 + r 1 ⟺ r 1 = b q 1 − a ⋯ ( 1 ) b = r 1 q 2 + r 2 ⟺ r 2 = b − r 1 q 2 ⋯ ( 2 ) r 1 = r 2 q 3 + r 3 ⟺ r 3 = r 1 − r 2 q 3 ⋯ r k = r k + 1 q k + 2 + 1 ⟺ 1 = r k − r k + 1 q k + 2 {\displaystyle {\begin{aligned}a=&bq_{1}+r_{1}\iff r_{1}=bq_{1}-a\cdots (1)\\b=&r_{1}q_{2}+r_{2}\iff r_{2}=b-r_{1}q_{2}\cdots (2)\\r_{1}=&r_{2}q_{3}+r_{3}\iff r_{3}=r_{1}-r_{2}q_{3}\\&\cdots \\r_{k}=&r_{k+1}q_{k+2}+1\iff 1=r_{k}-r_{k+1}q_{k+2}\\\end{aligned}}}
ここで、 r k = x k a + y k b {\displaystyle r_{k}=x_{k}a+y_{k}b} とおいてみると、
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 {\displaystyle {\begin{aligned}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{aligned}}}
となり、これらを、 r k = r k − 2 − r k − 1 q k {\displaystyle 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 {\displaystyle r_{k}=(x_{k-2}a+y_{k-2}b)-(x_{k-1}a+y_{k-1}b)q_{k}\iff 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 {\displaystyle (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 {\displaystyle 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 {\displaystyle x_{1}=1,\ \ y_{1}=q_{1},\ \ x_{2}=-q_{2},\ \ y_{2}=1+q_{1}q_{2}}
以上の結果をまとめると、
互いに素な二数 a , b {\displaystyle a,b} について、 a x + b y = 1 {\displaystyle ax+by=1} の方程式の解は、ユークリッドの互除法によって得られる逐次商 q 1 , q 2 , ⋯ , q k {\displaystyle 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 {\displaystyle 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 ≧ 3 ) {\displaystyle x_{k}=x_{k-2}-x_{k-1}q_{k},\ \ y_{k}=y_{k-2}-y_{k-1}q_{k}\ \ \ (k\geqq 3)}
で求められる。
※について : 係数を比較してこの式を導くのではなく、この式が成り立つならば先ほどの式も成り立つのは自明なのでこのように議論を展開しているのである。