数论中的整除性与同余

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

一、整除性

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)$。

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

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$ 整除，则有：

2.4 中国剩余定理

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

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

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

2.5 例题

例题 2：求解以下同余方程组：

解答：

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 47 \ (\text{mod} \ 60)$。

结论

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