約数（数論）

定義と基本表記

約数を扱う際には、正の約数と負の約数を区別することが多い。m が n を割り切るなら、(−m)(−k)=n であるため、−m も n を割り切る。分類や個数の計算では、通常 n の正の約数を列挙する。n の真の約数とは、n 自身を除く、n より小さい任意の正の約数である。素数は、正の約数が 1 とその数自身だけである 1 より大きい整数であり、合成数にはそれ以外の約数も存在する。

主な性質と例

• a が b を割り切り、b が c を割り切るなら、a は c を割り切る（推移性）。
• a が b を割り切るなら、a は b の任意の倍数を割り切る。
• 2つの整数の最大公約数（gcd）とは、両方を割り切る最大の整数である。これは反復除算（ユークリッドの互除法）によって求められる。
• 整除判定法により、小さな素数での整除可能性を迅速に確認できる。たとえば、2、3、5、9、11についての整除規則がある。

関連概念

因数分解とは、数を通常は素数である約数の積として表す過程である。約数の研究は、約数の個数を数える約数関数、整数環の構造、最大公約数および最小公倍数と結び付いている。数学における整数の背景については数学を、表記の参照については整数 nを、余りについては余りを参照。

用途、歴史と意義

約数は、ディオファントス方程式の解法、算術関数の解析、ならびに大きな整数の因数分解が計算上困難であることを利用する暗号技術などの応用において基本的である。整除性と素数に関する考え方は、歴史的には古代ギリシャ数学にまでさかのぼり、ユークリッドによって体系化された。現代のアルゴリズムの発展は高速な計算を可能にし、コンピュータ科学において実用的な重要性を持つ。因数分解アルゴリズムとその応用については因数分解を、素数の定義については素数を参照。

約数を理解することは、数論と初等算術における多くの結果を表すための、単純で統一的な言語を与える。約数の個数を数える場合、素数判定を行う場合、または最大公約数を計算する場合のいずれにおいても、ある整数が別の整数に余りなく収まるという基本的な考え方は、基礎的な道具であり続ける。