整除と最大公約数

整数 $a, b$ について、$b = ac$ を満たす整数 $c$ が存在するとき、$a$ は $b$ を割り切るといい、$a \mid b$ と書きます。割り切らないときは $a \nmid b$ と書きます。

$a, b$ が共に $0$ ではないとき、$a$ と $b$ の最大公約数 $\gcd(a,b)$ を、$a$ と $b$ の共通の約数のうち最大のものと定めます。共通の約数は $\min(|a|,|b|)$ 以下なので、最大値は存在します。$\gcd(a,b) = 1$ のとき $a, b$ は互いに素であるといいます。