公約数
公約数（こうやくすう、common divisor, common factor）とは、2 つ以上の自然数について、そのいずれの約数にもなることができる整数のことである。
定義
2つ以上の整数に共通な約数。公約数は、最大公約数の約数となる。例えば、<math>12</math>と<math>15</math>の公約数は<math>12</math>と<math>15</math>の最大公約数<math>3</math>を求め、最大公約数<math>3</math>の約数<math>1,\ 3</math>となる。
例
一般には約数は自然数の範囲内で考えることが多いので、例えば、<math>36</math>と<math>48</math>と<math>108</math>の公約数は<math>\{1,\ 2,\ 3,\ 4,\ 6,\ 12 \}</math>である。約数を整数の範囲内で考えるとき、約数には符号の違いを許すので、その個数は<math>2</math>倍となる。どういう範囲で考えているのかを常にはっきりさせておくべきである。
諸概念
公約数の内最大のものを最大公約数という。公約数は、全て最大公約数の約数であるので、最大公約数を求めれば全ての公約数を求めることができる。前述の例で言えば、<math>36</math>と<math>48</math>と<math>108</math>との最大公約数は<math>12</math>であるので、<math>12</math>の約数をすべて求めればそれが3つの数の全ての公約数になる。<math>1</math>は全ての自然数の公約数である。
また、2つ以上の多項式について、それぞれを因数分解したときに共通に現れる因数（因子、factor）も公約数（あるいは公約元、共通因子、common factor など）と呼ぶ。例えば、<math>(x+1)^2</math>と<math>x^2-1</math>について、<math>x+1</math>は公約数である。
最大公約数が<math>1</math>であるような2つの整数の組は、互いに素であるという。
一般化
単項イデアル整域<math>R</math>（例えば整数の全体<math>\mathbb{Z}</math>や実数係数多項式の全体<math>R[x]</math>はそうである）において、その2つの元<math>a,\ b</math>に対し、集合
- <math>aR+bR = \{ax+by|x,\ y \in R \}</math>
に含まれるイデアルの生成元を<math>a</math>と<math>b</math>の公約元という。特に
- <math>aR+bR = cR</math>
を満たす<math>c \in R</math>を<math>a</math>と<math>b</math>の最大公約元という。更に、この<math>c</math>が<math>R</math>の単位元であるとき、<math>a</math>と<math>b</math>は互いに素であるという。つまり、
- <math>a</math>と<math>b</math>が互いに素<math>\Leftrightarrow ax+by = 1</math>となる<math>x,\ y \in R</math>が存在する。
互いに素という概念は、更に一般の環でイデアルの間の関係として一般化される。環<math>S</math>の2つのイデアル<math>I,\ J</math>が
- <math>I+J = S</math>
を満たすとき、<math>I</math>と<math>J</math>は互いに素であるという。
