初等整数論/ユークリッドの互除法
この項目では、最大公約数を求めるアルゴリズムとその応用について述べる。
ユークリッドの互除法

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

証明 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)}
一次不定方程式

で求められる。
一次不定方程式

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