# 数论中的整除性与同余

数论是离散数学中的一个重要分支，主要研究整数的性质及其之间的关系。在这篇博客中，我们将深入探讨数论中的两个核心概念：整除性和同余。我们将定义相关术语，推导相关公式，并通过实例进行说明，以帮助读者深入理解这一领域。





## 一、整除性

### 1.1 整除的定义

如果存在整数 $k$ 使得 $a = b \times k$，则称 $b$ 整除 $a$，记作 $b \mid a$。例如，$3 \mid 12$，因为 $12 = 3 \times 4$。在数论中，整除性是许多其他概念的基础。

### 1.2 最大公约数与最小公倍数

- **最大公约数（GCD）**：两个整数 $a$ 和 $b$ 的最大公约数是能够整除 $a$ 和 $b$ 的最大的整数，记作 $\gcd(a, b)$。
- **最小公倍数（LCM）**：两个整数 $a$ 和 $b$ 的最小公倍数是能够被 $a$ 和 $b$ 整除的最小的正整数，记作 $\mathrm{lcm}(a, b)$。

这两个概念之间存在如下关系：

$$
\gcd(a, b) \times \mathrm{lcm}(a, b) = |a \times b|
$$

### 1.3 例题

**例题 1**：计算 $\gcd(48, 180)$ 和 $\mathrm{lcm}(48, 180)$。

**解答**：

1. 使用欧几里得算法计算 $\gcd(48, 180)$：
   - $180 = 48 \times 3 + 36$
   - $48 = 36 \times 1 + 12$
   - $36 = 12 \times 3 + 0$

   所以 $\gcd(48, 180) = 12$。

2. 利用公式计算 $\mathrm{lcm}(48, 180)$：
   $$
   \mathrm{lcm}(48, 180) = \frac{|48 \times 180|}{\gcd(48, 180)} = \frac{8640}{12} = 720
   $$

因此，$\gcd(48, 180) = 12$，$\mathrm{lcm}(48, 180) = 720$。

## 二、同余

### 2.1 同余的定义

如果两个整数 $a$ 和 $b$ 被同一个正整数 $m$ 整除的余数相同，则称 $a$ 和 $b$ 在模 $m$ 意义下同余，记作 $a \equiv b \ (\text{mod} \ m)$。例如，$17 \equiv 5 \ (\text{mod} \ 12)$，因为 $17 - 5 = 12$ 是 $12$ 的倍数。

### 2.2 模运算

模运算是处理同余的基本工具。对于任意整数 $a$ 和正整数 $m$，$a$ 的模 $m$ 运算定义为 $a \mod m$，即 $a$ 除以 $m$ 的余数。

### 2.3 费马小定理

费马小定理指出，如果 $p$ 是质数且 $a$ 是整数且不被 $p$ 整除，则有：

$$
a^{p-1} \equiv 1 \ (\text{mod} \ p)
$$

### 2.4 中国剩余定理

中国剩余定理为我们提供了一种在模不同的情况下求解同余方程组的方法。其基本形式为：

若 $m_1, m_2, \ldots, m_k$ 是互质的正整数，且 $a_1, a_2, \ldots, a_k$ 是任意整数，则存在唯一的整数 $x$ 满足：

$$
\begin{align*}
x & \equiv a_1 \ (\text{mod} \ m_1) \\
x & \equiv a_2 \ (\text{mod} \ m_2) \\
& \vdots \\
x & \equiv a_k \ (\text{mod} \ m_k)
\end{align*}
$$

并且 $x$ 的取值范围是 $0 \leq x < M$，其中 $M = m_1 \times m_2 \times \ldots \times m_k$。

### 2.5 例题

**例题 2**：求解以下同余方程组：
$$
\begin{align*}
x & \equiv 2 \ (\text{mod} \ 3) \\
x & \equiv 3 \ (\text{mod} \ 4) \\
x & \equiv 2 \ (\text{mod} \ 5)
\end{align*}
$$

**解答**：

1. 先求出 $M = 3 \times 4 \times 5 = 60$。
2. 对于每个模数，计算 $M_i = \frac{M}{m_i}$：
   - $M_1 = \frac{60}{3} = 20$
   - $M_2 = \frac{60}{4} = 15$
   - $M_3 = \frac{60}{5} = 12$

3. 计算 $y_i$，使得 $M_i y_i \equiv 1 \ (\text{mod} \ m_i)$：
   - 对于 $m_1 = 3$，$20y_1 \equiv 1 \ (\text{mod} \ 3)$，解得 $y_1 \equiv 2$。
   - 对于 $m_2 = 4$，$15y_2 \equiv 1 \ (\text{mod} \ 4)$，解得 $y_2 \equiv 3$。
   - 对于 $m_3 = 5$，$12y_3 \equiv 1 \ (\text{mod} \ 5)$，解得 $y_3 \equiv 3$。

4. 最后代入公式：
$$
x \equiv a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 \ (\text{mod} \ M)
$$

代入已知值：
$$
x \equiv 2 \cdot 20 \cdot 2 + 3 \cdot 15 \cdot 3 + 2 \cdot 12 \cdot 3 \ (\text{mod} \ 60)
$$

计算得：
$$
x \equiv 80 + 135 + 72 \equiv 287 \ (\text{mod} \ 60) \equiv 47
$$

因此，解为 $x \equiv 47 \ (\text{mod} \ 60)$。

## 结论

在本篇博客中，我们详细探讨了数论中的整除性及同余的基本概念和性质，通过相关的公式和例题加深了对这些概念的理解。数论不仅在理论上具有重要性，也在计算机科学、密码学等多个领域发挥着重要作用。希望读者能在后续的学习中继续深入探索这一富有魅力的数学分支。

离散数学：数论

## 引言

图灵机是计算理论中的一个核心概念，它不仅为理解算法提供了框架，也为研究可计算性和计算复杂性奠定了基础。在此博客中，我们将深入探讨图灵机的定义、其与算法的关系，以及可计算性的基本分类，涵盖可判定问题、不可判定问题、P类问题、NP类问题及NP完全性。





## 图灵机的定义及其与算法的关系

图灵机由艾伦·图灵于1936年提出，是一种理论上的计算模型，其结构如下：

- **带**：一个无限长的纸带，用于存储输入、输出及中间结果。
- **读写头**：可以在带上左右移动，并读取或写入符号。
- **状态寄存器**：保存图灵机当前的状态。
- **状态转移函数**：根据当前状态和读写头读取的符号，确定接下来要执行的操作。

图灵机的数学形式化定义为一个七元组 $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$，其中：

- $Q$ 是状态集；
- $\Sigma$ 是输入字母表；
- $\Gamma$ 是带上的符号集（包含空白符）；
- $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ 是状态转移函数；
- $q_0 \in Q$ 是初始状态；
- $q_{accept} \in Q$ 是接受状态；
- $q_{reject} \in Q$ 是拒绝状态。

图灵机的运算过程可以通过状态转移函数进行描述，算法可以视为图灵机在某一输入上的运行。换句话说，任何可计算的函数都可以通过某种图灵机来实现。

## 计算的复杂性

在计算理论中，问题的复杂性可以通过可判定性来分类。可判定性决定了一个问题是否存在算法来提供正确的答案。

### 可判定问题与不可判定问题

- **可判定问题**：存在图灵机能够在有限步骤内给出是/否答案的问题。举例来说，确定某个给定的自然数是否为素数的问题是可判定的。
  
- **不可判定问题**：不存在任何图灵机能够在有限步骤内解决的问题。经典例子是“停机问题”，即给定一台图灵机和输入，判断该图灵机是否在有限步骤内停止。形式化地，我们可以表示为：

$$
\text{停机问题} = \{ (M, w) \mid M \text{ 是图灵机且在输入 } w \text{ 上停止} \}
$$

### P类问题与NP类问题

- **P类问题**：可以在多项式时间内被解决的问题。形式上，问题 $L$ 属于 P 类当且仅当存在一个图灵机能够在 $O(n^k)$ 的时间内接受输入字符串 $x$，其中 $n$ 是 $x$ 的长度，$k$ 是常数。

- **NP类问题**：非确定性多项式时间问题，指的是可以在多项式时间内验证的决策问题。即给定一个“证书”，能够在多项式时间内验证该证书是否有效。

### NP完全性

一个问题是 NP 完全的，当且仅当它是 NP 类中的最难问题，即每个 NP 问题都可以在多项式时间内归约为该问题。如果我们能在多项式时间内解决一个 NP 完全问题，那么所有 NP 问题都能在多项式时间内解决。

#### NP 完全性示例

一个经典的 NP 完全问题是 **旅行商问题**（TSP）。它可以形式化为：给定一组城市及其之间的距离，是否存在一条路径，使得旅行商访问每个城市恰好一次后返回起点，并且总旅行距离不超过某个给定值。

## 例题分析

**例题**：考虑图灵机 $M$，其任务是接受所有输入字符串 $w$，使得 $w$ 中的 0 和 1 的数量相等。请判断该问题的可判定性。

### 解答

1. **构造图灵机**：可以设计一台图灵机 $M$，如下：
   - 初始化状态，读取输入字符串的第一个符号。
   - 在读到 0 时，寻找下一个 1，并标记它；在读到 1 时，寻找下一个 0，并标记它。
   - 如果成功标记完所有 0 和 1，接受；否则拒绝。

2. **可判定性**：通过上述构造的图灵机，我们可以在有限步骤内判断输入字符串是否符合条件。因此，该问题是可判定的。

## 总结

图灵机不仅是计算模型的基石，也是理解可计算性和计算复杂性的关键工具。通过图灵机的概念，我们能够深入分析算法的能力，并通过对可判定问题与不可判定问题、P类问题与NP类问题的研究，进一步理解计算问题的复杂性。这些理论不仅为计算机科学奠定了基础，也为实际应用中的算法设计提供了指导。希望本文能够为相关领域的专家提供深刻的见解与思考。

离散数学：图灵机与可计算性

## 递归与递归算法

### 递归的定义

递归是指在定义一个对象时，使用该对象自身的特性。形式上，递归可以通过递归关系来建立，常见的定义形式为：

$$
T(n) = 
\begin{cases} 
c & \text{if } n = 1 \\
T(n-1) + d & \text{if } n > 1 
\end{cases}
$$

在此，$T(n)$ 表示求解规模为 $n$ 的问题所需的时间，$c$ 和 $d$ 为常数。这种定义方式不仅展示了问题的结构，还提供了求解路径。





#### 例题：计算阶乘

阶乘是递归的经典例子，其定义为：

$$
n! = 
\begin{cases} 
1 & \text{if } n = 0 \\
n \cdot (n-1)! & \text{if } n > 0 
\end{cases}
$$

通过递归调用，可以逐步分解问题：

- 计算 $5!$：
  - $5! = 5 \cdot 4!$
  - $4! = 4 \cdot 3!$
  - $3! = 3 \cdot 2!$
  - $2! = 2 \cdot 1!$
  - $1! = 1$

最终结果为 $120$。

### 递归算法

递归算法是利用递归思想解决问题的一种有效方式。它通常通过分治法和动态规划来实现。

#### 1. 分治算法

分治算法通过将一个大问题分解为若干个小问题，独立解决后再合并结果。经典的合并排序算法即是一个很好的例子。

**合并排序的递归定义**：

$$
\text{MergeSort}(A) =
\begin{cases} 
A & \text{if } \text{length}(A) = 1 \\
\text{Merge}(\text{MergeSort}(A_1), \text{MergeSort}(A_2)) & \text{otherwise} 
\end{cases}
$$

其中，$A_1$ 和 $A_2$ 是数组 $A$ 的两个部分。合并操作需要时间 $O(n)$，整个排序过程的时间复杂度为 $O(n \log n)$。

#### 2. 动态规划

动态规划是一种优化技术，通过存储中间结果避免重复计算。它在求解最优子结构的问题时尤为有效。例如，斐波那契数列的递归定义为：

$$
F(n) = 
\begin{cases} 
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F(n-1) + F(n-2) & \text{if } n > 1 
\end{cases}
$$

采用动态规划可以将时间复杂度降低到 $O(n)$，其实现如下：

```python
def fibonacci(n):
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]
```

### 结论

递归与递归算法是离散数学中极为重要的概念，能够有效解决复杂问题。通过深入理解递归关系的建立与求解，以及掌握分治与动态规划的应用，研究者能够在算法设计中更为高效地利用这些思想。对于专家而言，探索更深层次的优化策略和复杂度分析将是未来的挑战。

离散数学：递归与递归算法

离散概率是概率论的重要组成部分，涉及到样本空间、事件、条件概率、随机变量及其期望等概念。本文将系统探讨这些基础知识，并结合公式和例题，帮助专家读者深入理解离散概率的核心内容。





### 基本概率概念

在离散概率中，**样本空间**（Sample Space）$S$是所有可能结果的集合。事件（Event）是样本空间的一个子集，记作$A \subseteq S$。概率的公理化定义由以下三条公理构成：

1. $P(A) \geq 0$，对于任何事件$A$，其概率非负。
2. $P(S) = 1$，样本空间的概率为1。
3. 若$A_1, A_2, \ldots$为互不相交事件，则$P(\bigcup_{i=1}^{\infty} A_i) = \sum_{i=1}^{\infty} P(A_i)$。

### 条件概率与独立性

**条件概率**（Conditional Probability）定义为在事件$B$发生的条件下事件$A$发生的概率，表示为：

$$
P(A|B) = \frac{P(A \cap B)}{P(B)} \quad (P(B) > 0)
$$

**全概率公式**（Law of Total Probability）用于计算复杂事件的概率：

$$
P(A) = \sum_{i} P(A|B_i) P(B_i)
$$

其中，$B_i$为一组互不相交的事件，满足$\bigcup B_i = S$。

**贝叶斯定理**（Bayes' Theorem）则表达了条件概率之间的关系，公式为：

$$
P(B|A) = \frac{P(A|B) P(B)}{P(A)}
$$

当$A$和$B$独立时，$P(A|B) = P(A)$，事件$A$与$B$的独立性可以用以下条件判断：

$$
P(A \cap B) = P(A) P(B)
$$

### 随机变量与期望

**离散随机变量**（Discrete Random Variable）是一个取值为有限或可数无穷的变量。随机变量$X$的**期望值**（Expectation）定义为：

$$
E(X) = \sum_{x} x P(X=x)
$$

**方差**（Variance）用于衡量随机变量的波动性：

$$
Var(X) = E(X^2) - [E(X)]^2
$$

常见的离散分布包括：

- **二项分布**（Binomial Distribution）：用于描述n次独立试验中成功次数的分布，概率质量函数为：

$$
P(X=k) = C(n, k) p^k (1-p)^{n-k}
$$

其中$C(n, k)$是组合数，$p$为单次成功概率。

- **泊松分布**（Poisson Distribution）：用于描述单位时间内事件发生的次数，概率质量函数为：

$$
P(X=k) = \frac{\lambda^k e^{-\lambda}}{k!} \quad (k=0, 1, 2, \ldots)
$$

其中$\lambda$为单位时间内的平均事件发生次数。

### 例题

**例题1**：抛掷一枚公平的六面骰子，求点数为偶数的概率。

**解**：
样本空间$S = \{1, 2, 3, 4, 5, 6\}$，事件$A = \{2, 4, 6\}$，即偶数点数。
因此，

$$
P(A) = \frac{|A|}{|S|} = \frac{3}{6} = \frac{1}{2}.
$$

**例题2**：设一颗均匀的硬币抛掷3次，求得到2次正面朝上的概率。

**解**：
这是一个二项分布问题，$n=3, k=2, p=\frac{1}{2}$。

$$
P(X=2) = C(3, 2) \left(\frac{1}{2}\right)^2 \left(\frac{1}{2}\right)^{3-2} = 3 \cdot \frac{1}{4} \cdot \frac{1}{2} = \frac{3}{8}.
$$

### 结论

离散概率为理解随机现象提供了强大的工具，通过样本空间、事件、条件概率及随机变量等概念的深度分析，专家们能够更有效地处理复杂的概率问题。未来的研究可进一步探讨离散概率在机器学习和统计推断中的应用。

离散数学：离散概率

组合数学是离散数学的一个重要分支，主要关注如何计数和排列不同的对象。本文将深入探讨几个关键概念：计数原理、生成函数、递归关系及鸽巢原理。





## 1. 计数原理

### 1.1 加法原理

加法原理指出，如果一个任务可以通过多种方式完成，而这些方式是互斥的，则完成这个任务的总方法数是各个方法数之和。公式如下：

$$
N = N_1 + N_2 + \ldots + N_k
$$

例如，假设有3种选择的水果和4种选择的饮料，则总选择数为：

$$
N = 3 + 4 = 7
$$

### 1.2 乘法原理

乘法原理表明，如果一个任务可以分为多个步骤，其中每个步骤都有多种选择，则完成整个任务的总方法数是各步骤选择数的乘积。公式为：

$$
N = N_1 \times N_2 \times \ldots \times N_k
$$

假设选择一件衣服有3种颜色，配件有2种选择，则总的搭配方式为：

$$
N = 3 \times 2 = 6
$$

### 1.3 排列与组合

排列是指从n个不同元素中选择r个元素，并考虑顺序的情况。排列数计算公式为：

$$
P(n, r) = \frac{n!}{(n-r)!}
$$

而组合则是从n个不同元素中选择r个元素，但不考虑顺序。组合数计算公式为：

$$
C(n, r) = \frac{n!}{r!(n-r)!}
$$

### 例题

从5个不同的书中选择2本并排列，排列数为：

$$
P(5, 2) = \frac{5!}{(5-2)!} = 20
$$

从5个不同的书中选择2本，组合数为：

$$
C(5, 2) = \frac{5!}{2!(5-2)!} = 10
$$

## 2. 生成函数

生成函数是一个强大的工具，用于处理计数问题。其定义为：

$$
G(x) = a_0 + a_1x + a_2x^2 + \ldots = \sum_{n=0}^{\infty} a_n x^n
$$

生成函数的应用可以帮助我们找到序列的显式表达式。例如，斐波那契数列的生成函数为：

$$
F(x) = \frac{x}{1 - x - x^2}
$$

通过对生成函数进行幂级数展开，可以直接获得数列的项。

## 3. 递归关系

递归关系常用于描述组合结构的性质。线性递归关系的标准形式为：

$$
a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}
$$

其通解通常通过特征方程获得。以斐波那契数列为例，其递归关系为：

$$
F(n) = F(n-1) + F(n-2) \quad (n \geq 2)
$$

解该递归关系可以得到斐波那契数列的显式公式：

$$
F(n) = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}}
$$

其中，$\varphi = \frac{1 + \sqrt{5}}{2}$。

## 4. 鸽巢原理

鸽巢原理是组合数学中的基本原理，表明如果n个鸽子放入m个鸽巢中，而$n > m$，则至少有一个鸽巢中有不止一个鸽子。这个原理在组合问题中应用广泛。例如，考虑10个人在9个房间中居住，至少有一个房间住有2人。

### 应用示例

在一个考试中，如果有12个学生和11个试卷，应用鸽巢原理可推断至少有一个试卷会被多于一个学生选择。

## 结论

组合数学通过计数原理、生成函数、递归关系和鸽巢原理为我们提供了强大的工具和方法，能够深入分析和解决复杂的组合问题。未来的研究可以进一步探讨这些理论在实际应用中的表现及其交叉领域的影响。

离散数学：组合数学

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。