当前没有测试数据。

初等数论

1、整除、因数、倍数、指数、质数、合数

整除：若整数 a 除以 整数 b （b != 0）的余数 为 0

a % b == 0

因数：若整数 a 能被 整数 b 整除，则称 b 是 a 的因数

倍数：若整数 a 能被 整数 b 整除，则 a 是 b 的倍数

指数：在幂运算$a^{n}$中，n 称为 指数，a 称为 底数，表示a 进行 n 次相乘。

同底数指数幂运算

一、基本定义

设底数为 ( a )，指数为 ( m, n )，其中 ( a != 0 )，则有以下运算规律：

1. 同底数幂的乘法:底数相同，指数相加。

$$a^m \times a^n = a^{m+n}$$

示例：

$$2^3 \times 2^4 = 2^{3+4} = 2^7 = 128$$

2. 同底数幂的除法:底数相同，指数相减。

$$\frac{a^m}{a^n} = a^{m-n} \quad (a \neq 0)$$

示例：

$$\frac{5^6}{5^2} = 5^{6-2} = 5^4 = 625$$

3. 幂的乘方:幂的再幂运算，相当于指数相乘。

$$(a^m)^n = a^{m \times n}$$

示例：

$$(3^2)^4 = 3^{2 \times 4} = 3^8 = 6561$$

4. 幂的积的幂:依次分配

$$(ab)^n = a^n \times b^n$$

示例：

$$(2 \times 3)^4 = 6^4 = 1296$$ $$2^4 \times 3^4 = 16 \times 81 = 1296$$

5. 幂的商的幂：依次分配

$$\left(\frac{a}{b}\right)^n = \frac{a^n}{b^n} \quad (b \neq 0)$$

示例：

$$\left(\frac{2}{5}\right)^3 = \frac{2^3}{5^3} = \frac{8}{125}$$

质数：一个大于1的自然数，除了1 和 它本身以外，不再有其他的因数的数，叫做质数

合数：一个大于1的自然数，除了1 和 它本身以外，还有其他的因数的数，叫做合数

（1既不是质数也不是合数）

同余定理（Congruence Theorem）

一、同余的定义

设整数 a、b、m，且 m ≠ 0，如果 a 和 b 除以 m 所得的余数相同，我们就称：

$$a \equiv b \pmod{m}$$

则称 “$a$ 与 $b$ 模 $m$ 同余”，表示 $a$ 和 $b$ 除以 $m$ 后的余数相同。

等价定义：

$$m \mid (a - b)$$

即 $a - b$ 能被 $m$ 整除。

二、基本性质

设 $a \equiv b \pmod{m}$，$c \equiv d \pmod{m}$，则有：

1. 加法性质：

$$a + c \equiv b + d \pmod{m}$$

2. 减法性质：

$$a - c \equiv b - d \pmod{m}$$

3. 乘法性质：

$$a \cdot c \equiv b \cdot d \pmod{m}$$

4. 幂运算性质（若 $a \equiv b \pmod{m}$）：k是整数

$$a^k \equiv b^k \pmod{m}$$

三、常用定理

1. 同余传递性

若：

$$a \equiv b \pmod{m}, \quad b \equiv c \pmod{m}$$

则：

$$a \equiv c \pmod{m}$$

2. 同余与除法（条件使用）

若：

$$a \cdot d \equiv b \cdot d \pmod{m}$$

且 $\gcd(d, m) = 1$，则：

$$a \equiv b \pmod{m}$$

3. 模的缩小（模约简）

若：

$$a \equiv b \pmod{km}$$

则：

$$a \equiv b \pmod{m}$$

4. 模的合并（模提升）

若：

$$a \equiv b \pmod{m} \quad \text{且} \quad a \equiv b \pmod{n}$$

并且 $\gcd(m, n) = 1$，则：

$$a \equiv b \pmod{mn}$$

整数唯一分解定理（算术基本定理）

任何大于1的正整数 n 都可以 唯一 地 分解为 有限个质数的乘积

例如：$60=2^2 * 3^1 * 5^1$ = $60=2*2*3*5$

可以理解为因为有这个定理：使得为质因数分解的存在性和唯一性提供了保证