最大公約数
著者:梅谷 武
語句:倍数,約数,同伴,素数,合成数,公約数,最大公約数,ユークリッドの互除法
整除関係と最大公約数について述べる。
作成:2006-04-24
更新:2013-06-16
 自然数の場合と同様に二つの整数a,b(≠0)がある整数qによってa=bqと表されるとき、ab倍数ばいすう, multipleである、あるいはba約数やくすう, divisorであるといい、b|aと書くことにします。この二つの整数のちょうど割れるか割れないかという関係を整除関係といいます。この節では整除関係の基本的な性質について調べてみます。
 まず、任意の整数aについてa=1×a0=0×aですから、
a|a, 1|a, a|0
であることがわかります。次にa|b,b|cとするとb=aq,c=bq'と書けるのでc=aqq'となり、a|cであることがわかります。したがって、
a|b, b|c ⇒ a|c
が成り立ちます。さらにa|b,b|aであるとしましょう。割る側は0でないと仮定していますからa≠0,b≠0であることに注意してください。b=aq,a=bq'よりa=aqq'となりqq'=1ですからq=q'=±1となります。したがって、
a|b, b|a ⇒ b = ±a
が成り立ちます。整数a,ba|bかつb|aという条件を満たすときab同伴どうはん, associatedであるといい、a⋍bと書くことにします。 これはb=±aと同じことです。同伴関係をで表すと、 上で述べたことは、同伴関係は整数上の同値関係であって、その同値類全体の集合ℤ/⋍において整除関係|が順序関係になっていると言い換えることができます。この同値類の代表として正の数をとることにすれば、ℤ/⋍は自然数の集合と1対1に対応します。このことを命題の形で整理しておきましょう。

命題2.2.3 整除関係の順序性

 自然数の集合の整除関係について次の性質が成り立つ。すなわち、 整除関係は自然数に順序を与える。
(1) 任意の元a∈ℕについてa|a
(2) 任意の2元a,b∈ℕについてa|b, b|a ⇒ a=b
(3) 任意の3元a,b,c∈ℕについてa|b, b|c ⇒ a|c

例題2.2.4

a|b, a|c ⇒ a|(b+c)

証明

b=aq,c=aq'よりb+c=a(q+q')

例題2.2.6

a|b, n∈ℤ ⇒ a|nb

証明

b=aqよりnb=anq

例題2.2.8

b|ai, i=1,⋯,n ⇒ b|(t1 a1+ t2 a2+ ⋯ + tn an ), ti∈ℤ

証明

ai=bqiを代入すればt1 a1+ t2 a2+ ⋯ + tn an = b(t1 q1+ t2 q2+ ⋯ + tn qn)
b|aであれば-b|aですから、約数という概念は同伴類に対して定まるものであることがわかります。ですから整数aの約数全体の集合を考えるときに、整数全体の集合ではなくて、その同伴類の集合ℤ/⋍を考えるのが自然です。さらにℤ/⋍は自然数の集合と1対1に対応しますから、今後は簡単のために自然数の部分集合である正の約数全体の集合だけを考えることにしましょう。整数aの正の約数全体の集合をD(a)で表すことにします。例えば1215の場合、次のようになります。
D(12)
=
{ 1, 2, 3, 4, 6, 12 }
D(15)
=
{ 1, 3, 5, 15 }
整数aの任意の正の約数dについて0<d≦aが成り立ちますから、D(a)は有限集合です。2以上の整数pD(p)={1,p}となるとき、すなわち正の約数が1と自分自身しかないときにp素数そすう, prime numberといいます。素数でない数を合成数ごうせいすう, composite numberといいます。
 整数d(≠0)が二つの整数a,bについてd|a,d|bとなっているときda,b公約数こうやくすう, common divisorであるといいます。a,bの正の公約数全体の集合はD(a)∩D(b)と一致します。その集合の最大の数、すなわちabの公約数の中で最大のものをab最大公約数さいだいこうやくすう, greatest common divisorといい、gcd(a,b)あるいは単に(a,b)と書くことにします。例えば1215の場合、
D(12) ∩ D(15) = { 1, 3 }
ですから、gcd(12,15)=3となります。gcd(a,b)=1のときabは互いに素であるといいます。
 図に示すように二つの整数a,bの最大公約数を求めるという問題は辺の長さがa,bである長方形の領域を同じ大きさの正方形のタイルで埋め尽くすときに正方形の辺の長さの最大値を求めるという幾何学の問題に置き換えることができます。
 ユークリッド原論の第VII巻命題2に二つの整数の最大公約数を求める算法が解説されています。この算法はユークリッドの互除法ゆーくりっどのごじょほう, Euclidean algorithmと呼ばれています。現代においても整数の計算のみならず多項式の計算においても簡単でとても効率がよい算法として重宝されているものです。

算法2.2.15 ユークリッドの互除法

 二つの整数a,bの最大公約数dを求める。
Step 1. もしb=0であればd=|a|として終了する。
Step 2. abで割った余りをrとする。(a=bq+r, 0≦r<|b|)
Step 3. a=b, b=rとして、Step 1.へ。
 これで最大公約数が求まることは、d∈D(a)∩D(b)とするとd|r(=a-bq)であり、d'∈D(b)∩D(r)とするとd'|a(=bq+r)となることから、
D(a) ∩ D(b) = D(b) ∩ D(r)
となり、公約数の集合が一致することと繰り返しの際に変数a,bがとも前回よりも小さくなるのでいつかはr=0となることからわかります。
 図の例にこれを当てはめてみましょう。
15
=
1・12 + 3
12
=
4・3 + 0
幾何学的な言葉で表現すれば、長方形から短い辺の正方形を取れるだけ取り去り、残りがまた長方形であれば同じことを繰り返し、残りがなくなったときの辺の長さが最大公約数であるということになります。これをプログラミングしてみます。

sample2.2.5.py

def gcd( a, b ):
  while b != 0:
    r = a % b
    a = b
    b = r
  if a < 0:
    return -a
  else:
    return a
 
a = 9749560641517
b = 8770036831691
d = gcd( a, b )
print 'gcd( %d, %d ) = %d' % ( a, b, d )

sample2.2.5.pyの実行結果

gcd( 9749560641517, 8770036831691 ) = 6972593

sample2.2.5.rb

def gcd(a, b)
  while b != 0
    r = a % b
    a = b
    b = r
  end
  if a < 0
    return -a
  else
    return a
  end
end
 
a = 9749560641517
b = 8770036831691
d = gcd(a, b)
printf "gcd(%d, %d) = %d", a, b, d

sample2.2.5.rbの実行結果

gcd(9749560641517, 8770036831691) = 6972593
[1] 中村幸四郎, 伊東俊太郎, 寺阪英孝, 池田美恵 訳, ユークリッド原論, 共立出版, 1996
img
 
 
数  学
倍数 ばいすう, multiple
約数 やくすう, divisor
同伴 どうはん, associated
素数 そすう, prime number
合成数 ごうせいすう, composite number
公約数 こうやくすう, common divisor
最大公約数 さいだいこうやくすう, greatest common divisor
ユークリッドの互除法 ゆーくりっどのごじょほう, Euclidean algorithm
 
Published by SANENSYA Co.,Ltd.