整除

对 a, b \in \mathbb{Z}，若存在 c \in \mathbb{Z}，使得 bc = a，则称 b 整除（divides）a，记为 b \mid a。此时，称 b 是 a 的因数或约数（divisor），a 是 b 的倍数（multiple）。若对任意的整数 c 都有 bc \ne a，则称 b 不整除 a，记为 b \nmid a。

带余除法

最大公因数和互质

最大公因数

定理：对任意的两个整数 a, b，存在整数 d，满足 d 是 a, b 的公因数，且若 c 也是 a, b 的公因数，则 c \mid d。d 称为 a, b 的最大公因数（greatest common divisor, GCD）。

互质

若 (a, b) = 1，称 a, b 互质或互素（coprime, or relatively prime）。

Euclid 引理：若 a \mid bc, (a, b) = 1，则 a \mid c。

Bezout 定理

设 d = (a, b)，则存在 x, y \in \mathbb{Z}，满足：ax + by = d。特殊地，a, b 互质可得到 ax + by = 1。

逆定理：若存在 x, y \in \mathbb{Z}，满足 ax + by = 1，则 a, b 互质；若存在 x, y \in \mathbb{Z} 满足 ax + by = d，且 d 是 a, b 的公因数，则 d = (a, b)。

Euclid 算法

质数

定义

对一个大于 1 的整数 n，若其因数只有 1, n，则称 n 为质数或素数（prime）。

全体质数的集合通常记为 \mathbb{P}。

定理

对于任意的正整数 a 和质数 p ，要么 p \mid a ，要么 (p, a) = 1 。

证明

令 d = (p, a) ，则 d \mid p ，由质数的定义（只有 1 和它本身为正因数），要么 d = 1 ，要么 d = p ，且由 p \ne 1 ，两者不可能同时成立。当 d = p 时，因为 d \mid a 即 p \mid a ，前者成立；当 d = 1 时，(p, a) = d= 1 ，后者成立。