因数

一个可以整除另一个整数的整数。例如：2、3、4、6都是12的因数。

倍数

一个可以被另一个整数整除的整数。例如：6、12、18都是3的倍数。

素（质）数与合数

设整数 $p\ne0,\pm1$。如果 p 除了平凡约数（1和其本身）外没有其他约数，那么称 p 为素数（不可约数）。

若整数 $a\ne0,\pm 1$ 且 a 不是素数，则称 a 为合数。

p 和 -p 总是同为素数或者同为合数。如果没有特别说明，素数总是指正的素数。

整数的因数是素数，则该素数称为该整数的素因数（素约数）。

素数与合数的简单性质：

• 大于 1 的整数 a 是合数，等价于 a 可以表示为整数 d 和 e（1<d,e<a）的乘积。
• 如果素数 p 有大于 1 的约数 d，那么 d=p。
• 大于 1 的整数 a 一定可以表示为素数的乘积。
• 对于合数 a，一定存在素数 $p\le\sqrt{a}$使得 $p\mid a（p能整除a）$。
• 素数有无穷多个。
• 所有大于 3 的素数都可以表示为 $6n\pm 1$ 的形式。

最大公约数

最大公约数即为 Greatest Common Divisor，常缩写为 gcd。

一组整数的公约数，是指同时是这组数中每一个数的约数的数。$\pm 1$ 是任意一组整数的公约数。

一组整数的最大公约数，是指所有公约数里面最大的一个。

欧几里得算法(辗转相除法)求最大公约数

它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。