最后更新: 2025-03-08 09:07 查看: 250 次反馈刷题

整除、同余、素数(质数)与合数

整除是两个整数之间的一种关系，它是数论中的最基本概念。

## 整除

设 $a, b \in \mathbb{Z}$ 且 $b \neq 0$ ，如果存在 $c \in \mathbb{Z}$ ，使得 $a=b c$ 我们就称 $b$ 整除（divide） $a$ ，记作 $b \mid a$ 。此时我们也称 $b$ 是 $a$ 的一个因子 (或约数， divisor)， $a$ 是 $b$ 的倍数 (multiple)。

如果满足上述条件的 $c$ 不存在，则称 $b$ 不整除 $a$ ，记作 $b \nmid a$ 。
例如， $2|4,(-5)| 15,3 \nmid 5$ 等等。
特别地， $\forall a \in \mathbb{Z}, 1 \mid a ，$ 且 $\forall b \in \mathbb{Z}-\{0\}, b \mid 0$.

一些整数整除的特征见整除的特征。

### 基本性质

设下列各条件均有意义，则

1. 传递性: $a|b, b| c \Longrightarrow a \mid c$;
2. $a|b, b| a \Longrightarrow a= \pm b$;
3. $a|b, a| c \Longrightarrow a \mid b x+c y, \forall x, y \in \mathbb{Z}$.

### 环上的整除

设 $R$ 是交换环， $a, b \in R$ ，如果存在 $c \in R$ 使得 $a=b c$ ，我们就说 $b$ 整除 $a$ ，记作 $b \mid a$ ，同时称 $b$ 是 $a$ 的因子， $a$ 是 $b$ 的倍数。如果不存在这样的 $c$ ，我们就说 $b \nmid a$.

如果 $b|a, a| b$ ，我们就说 $a, b$ 是相伴的 (associates)，常记作 $a \sim b$ ，它是一种等价关系。可以证明，整环中两个非零元 $a, b$ 相伴当且仅当存在单位 $u \in R$ (即满足存在 $v$ 使得 $u v=v u=1$ ) 使得 $b=a u$.

和单位元 1 相伴的元素是 $R$ 上的单位 (unit)，即 $1 \sim u$ ，这里 $u$ 满足: 存在 $v$ 使得 $u v=v u=1$.

同余是初等数论里的一个重要的概念，关于代数系统之间的同余，详见代数同余。

## 同余概念

若两个数 $a$ 与 $b$ 除以 $m$ 的余数相同，或说 $a-b$ 可被 $m$ 整除，则说 $a$ 与 $b$ 同余于 $m$ 或 $a$ 等于 $b$ 模 $m$ 。

一般将“ $a$ 与 $b$ 同余于 $m$ "记作 $a \equiv b \quad(\bmod m)$ 且有 $a \equiv b \quad(\bmod m) \Longleftrightarrow m \mid a-b$ ，而 $a \neq \equiv \quad(\bmod m) \Longleftrightarrow m \nmid a-b$

除整数集合外，所有整系数多项式所组成的集合，亦有类似整数的同余存在。

### 性质

- 同余是一个等价关系，是因为它有:

1. 自反性, $a \equiv a(\bmod m)$;
2. 对称性， $a \equiv b \quad(\bmod m) \Longleftrightarrow b \equiv a \quad(\bmod m)$;
3. 传递性: $a \equiv b \quad(\bmod m) \& b \equiv c \quad(\bmod m) \Longrightarrow a \equiv c(\bmod m)$.

- 同余式运算有像通常等式那样类似的加减乘运算:

1. 若 $a \equiv c \quad(\bmod m)$ 且 $b \equiv d \quad(\bmod m)$ ，则 $(a \pm b) \equiv(c \pm d) \quad(\bmod m)$ 且 $a b \equiv c d \quad(\bmod m)$ ；
2. 若 $a c \equiv b c \quad(\bmod m)$ 则 $a \equiv b \quad\left(\bmod \frac{m}{(c, m)}\right)$ ，特别地， $(c, m)=1$ ，则 $a \equiv b \quad(\bmod m)$ ；

- 若 $(a, m)=1$ ，则存在一数 $c$ ，使得 $c a \equiv 1 \quad(\bmod m)$ ；
- 若 $a \equiv b \quad(\bmod m)$ ，则 $\forall d: d \mid m, a \equiv b \quad(\bmod d)$ ；
- 若 $d>0$ ，则 $a \equiv b \quad(\bmod m) \Longleftrightarrow a d \equiv b d \quad(\bmod m d)$ ；
- 若 $a \equiv b \quad\left(\bmod m_i\right), 1 \leqslant i \leqslant n$ ，则 $a \equiv b \quad\left(\bmod \left[m_1, m_2, \cdots, m_n\right]\right)$ 。
-

### 推论

设 $f(x)$ 是整系数多项式，如果 $a \equiv b(\bmod m)$ ，则 $f(a) \equiv f(b) \quad(\bmod m)$ 。

## 质数(素数)

**质数**（Prime number）是指大于1的自然数，且只能被1和它本身整除的数。换句话说，质数只有两个正因数：1和它本身。

### 质数的性质
1. **最小的质数**是2，它也是唯一的偶质数。
2. 除了2以外，所有质数都是奇数。
3. 质数的个数是无限的（欧几里得证明了这一点）。
4. 1不是质数，因为它只有一个正因数。

### 质数的例子
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97……

### 质数的应用
质数在数学和计算机科学中有广泛的应用，例如：
- **密码学**：质数被用于RSA加密算法等公钥加密系统中。
- **数论**：质数是研究整数性质的基础。
- **哈希函数**：质数常用于设计高效的哈希函数。

### 判断质数的方法
1. **试除法**：对于一个数$ n $，检查从2到$ \sqrt{n} $之间的所有整数是否能整除$ n $。如果都不能整除，则$ n $是质数。
2. **筛法**：如埃拉托斯特尼筛法（Sieve of Eratosthenes），用于快速找出一定范围内的所有质数。

如果你有关于质数的具体问题，欢迎继续提问！

## 合数
**合数**（Composite number）是指大于1的自然数，且除了1和它本身外，至少还有一个其他正因数的数。换句话说，合数是至少有三个正因数的数。

### 合数的性质
1. **最小的合数**是4。
2. 合数可以分解为两个或更多质数的乘积（质因数分解）。
3. 1既不是质数，也不是合数。
4. 除了1和质数之外，所有的自然数都是合数。

### 合数的例子
- 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40……

### 合数与质数的关系
- 质数和合数是互补的概念：一个大于1的自然数要么是质数，要么是合数。
- 合数可以表示为多个质数的乘积，例如：
  - $ 4 = 2 \times 2 $
  - $ 6 = 2 \times 3 $
  - $ 12 = 2 \times 2 \times 3 $

### 判断合数的方法
1. **试除法**：对于一个数$ n $，检查从2到$ \sqrt{n} $之间的所有整数是否能整除$ n $。如果存在能整除的数，则$ n $是合数。
2. **质因数分解**：如果能将一个数分解为多个质数的乘积，则该数是合数。

### 合数的应用
合数在数学和计算机科学中也有一定的应用，例如：
- **因数分解**：合数的质因数分解是数论中的重要问题。
- **密码学**：某些加密算法（如RSA）依赖于大合数的质因数分解的困难性。

如果你有关于合数的具体问题，欢迎继续提问！

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：第二部分数论部分问题概述

下一篇：最大公约数与最小公倍数

本文对您是否有用？有用 (0) 无用 (0)