約数と倍数
【定義】
2つの整数 $a$，$b$ について，ある整数 $k$ を用いて $a=bk$ と表されるとき，$b$ は $a$ の約数であるといい，$a$ は $b$ の倍数であるという。$a=bk$ のとき，$a=(-b) \cdot (-k)$ でもあるから，$b$ が $a$ の約数ならば $-b$ も $a$ の約数である。
自然数についての倍数の判定法
- 2の倍数：一の位が偶数
- 3の倍数：各位の数の和が3の倍数
- 4の倍数：下2桁が4の倍数
- 5の倍数：一の位が0または5
- 6の倍数：2の倍数かつ3の倍数
- 8の倍数：下3桁が8の倍数
- 9の倍数：各位の数の和が9の倍数
素数，合成数，素因数分解
【定義】
素数：2以上の自然数で，正の約数が1とその数自身のみである数
合成数：2以上の自然数で，素数でない数
因数：整数がいくつかの整数の積で表されるときのそれぞれの整数
素因数：素数である因数
素因数分解：自然数を素数だけの積の形に表すこと
※合成数は必ず素因数分解できる。
※素因数分解の一意性：1つの合成数の素因数分解は積の順序を考えなければ1通りであること
最大公約数・最小公倍数
【定義】
公約数：2つ以上の整数について，共通する約数
最大公約数：公約数のうち最大のもの
※最大公約数を英語の greatest common divisor の頭文字 gcd で，値を $g$ で表すことがある。
公倍数：2つ以上の整数について，共通する倍数
最小公倍数：正の公倍数のうち最小のもの
※最小公倍数を英語の least common multiple の頭文字 lcm で，値を $l$ で表すことがある。
※公約数は最大公約数の約数，公倍数は最小公倍数の倍数である。
※0でない2つ以上の整数の最大公約数は常に正の数であるから，最大公約数，最小公倍数を求めるときは，正の数に限定して考えればよい。
互いに素：2つの整数の最大公約数が1であること
【定理】
$a$，$b$，$c$ は整数で，$a$，$b$ は互いに素であるとすると，次のことが成り立つ。
- $ac$ が $b$ の倍数であるとき，$c$ は $b$ の倍数である。
- $a$ の倍数であり，$b$ の倍数でもある整数は，$ab$ の倍数である。
2つの自然数 $a$，$b$ の最大公約数を $g$，最小公倍数を $l$ とする。$a=ga’$，$b=gb’$ であるとすると，次のことが成り立つ。
- $a’$，$b’$ は互いに素である。
- $l=ga’b’$
- $ab=gl$
整数の割り算における商と余り
整数 $a$ と正の整数 $b$ について $a=bq+r$，$0 \leqq r<b$ となる整数 $q$，$r$ は1通りに定まる。
$a=bq+r$ において，$q$ は $a$ を $b$ で割ったときの商，$r$ は $a$ を $b$ で割ったときの余りという。
$r=0$ のとき $a$ は $b$ で割り切れるという。$r \neq 0$ のとき $a$ は $b$ で割り切れないという。
和，差，積の余り
$a=mq+r$，$b=mq’+r’$ とおくと
- $a+b$ を $m$ で割った余りは，$r+r’$ を $m$ で割った余りに等しい。
- $a-b$ を $m$ で割った余りは，$r-r’$ を $m$ で割った余りに等しい。
- $ab$ を $m$ で割った余りは，$rr’$ を $m$ で割った余りに等しい。
- $a^k$ を $m$ で割った余りは，$r^k$ を $m$ で割った余りに等しい。
余りによる整数の分類
整数を正の整数 $m$ で割ったときの余りに着目すると，すべての整数は，整数 $k$ を用いて次のいずれかの形に表される。
$\begin{array}{cccc} mk， & mk+1， & ……， & mk+(m-1) \\ 余り0 & 余り1 & …… & 余りm-1 \end{array}$