整除

概念和性质

定义（整除）：

• 设 $$a, b \in \mathbb{Z}, b \neq 0.$$ 如果 $$\exist q \in \mathbb{Z}, s.t. a = qb.$$ 那么就称 b 整除 a，或 a 被 b 整除，记作 $$b | a.$$

完全数、梅森素数和费马素数

Basic

费尔马素数和梅森素数的研究都基于这样一个重要的因式分解：

• $$\displaystyle 2^{st} - 1 = (2^s - 1)(\sum_{i=1}^{t} 2^{s(t-i)})$$

• 若 t 为奇数：$$\displaystyle 2^{st} + 1 = (2^s + 1)(\sum_{i = 1}^{t}(-1)^{i+1} 2^{s(t-i)})$$

Concept

定义（完全数）：

• 如果一个正整数 N 的所有正因子之和为 2N，则 N 称为完全数。
• $$\sigma(a)$$ 表示 a 的素因子之和。

定理：

• 若正整数 n 的标准分解式 $$\displaystyle n = p_1^{a_1} p_2^{a_2} … p_s^{a_s}$$
• 则：$$\displaystyle \sigma(n) = \frac{p_1^{a_1 + 1} - 1}{p_1 - 1}…\frac{p_s^{a_s + 1} - 1}{p_s - 1}$$

定理：

• 若 $$2^n -1$$ 是素数，则 $$2^{n-1} (2^n - 1)$$ 是偶完全数，且所有偶完全数均可以用这种形式表示。

定理：

• 若 $$2^n - 1$$ 为素数，则 n 必为素数。

定义（梅森数）：

• 设 p 是一个素数，形如 $$2^p - 1$$ 的数叫做梅森数，记为 $$M_p = 2^p - 1$$，当 $$M_p$$ 为素数时，则称其为梅森素数。

定理：

• 若 $$2^m + 1$$ 为素数，则 $$m = 2^n$$

定义（费马数）：

• 若 n 为非负数，则称 $$F_n = 2^{2^n} + 1$$ 为费马数。当 $$F_n$$ 为素数时，则称其为费马素数。