ChungZH 的小窝
·
初等数论入门
内容提要
文章讨论了整数的整除、最大公因子、线性组合和同余等数学概念，定义了整除条件，提出了相关定理和推论，包括带余除法和最大公因子的求法及性质。介绍了扩展欧几里得算法用于求解线性方程的特解，以及同余方程的解法，并通过实例展示了这些理论的实际应用。
关键要点
-
定义：如果 a 和 b 为整数且 a ≠ 0，a 整除 b 是指存在整数 c 使得 b=ac。
-
定理 1：如果 a, b 和 c 是整数，且 a | b, b | c，则 a | c。
-
定理 2：如果 a, b, m 和 n 为整数，且 c | a, c | b，则 c | (ma + nb)。
-
带余除法：如果 a 和 b 是整数且 b > 0，则存在唯一的整数 q 和 r，使得 a = bq + r, 0 ≤ r < b。
-
最大公因子定义：不全为零的整数 a 和 b 的最大公因子是指能够同时整除 a 和 b 的最大整数。
-
定理 6：两个不全为零的整数 a, b 的最大公因子是 a, b 的线性组合中最小的正整数。
-
扩展欧几里得算法用于求解线性方程的特解。
-
同余定义：若 a 和 b 是整数，m 为正整数，则称 a 和 b 模 m 同余，记作 a ≡ b (mod m)。
-
定理 9：若 a 和 b 是整数，则 a ≡ b (mod m) 当且仅当存在整数 k，使得 a = b + km。
-
定理 17：设 a, b, m 是整数，m > 0，(a, m) = d。若 d | b，则 ax ≡ b (mod m) 恰有 d 个模 m 不同余的解。
延伸解读
整除与因子的关系
整除是数论中的基本概念，理解整除关系有助于掌握因子的性质。若 a 整除 b，则 a 是 b 的因子，反之 b 是 a 的倍数。这一关系在求解最大公因子时尤为重要，因其直接影响到线性组合的构成。
最大公因子的求法
最大公因子（gcd）的求法不仅限于辗转相除法，还可以通过线性组合来求解。定理 6 指出，两个整数的最大公因子是它们的线性组合中最小的正整数，这一性质在实际应用中可以简化计算过程。
同余方程的解法
同余方程的解法依赖于最大公因子的性质。定理 17 说明，若 d 是 a 和 m 的最大公因子，且 d 整除 b，则方程 ax ≡ b (mod m) 有 d 个不同余的解。这一结果在解决实际问题时提供了重要的理论支持。
延伸问答
什么是整除的定义？
如果 a 和 b 为整数且 a ≠ 0，a 整除 b 是指存在整数 c 使得 b=ac。
如何求两个整数的最大公因子？
最大公因子是能够同时整除两个整数的最大整数，可以通过辗转相除法或扩展欧几里得算法求得。
什么是同余？
若 a 和 b 是整数，m 为正整数，则称 a 和 b 模 m 同余，记作 a ≡ b (mod m)，即 m 整除 (a-b)。
扩展欧几里得算法的用途是什么？
扩展欧几里得算法用于求解线性方程的特解，特别是在求解形如 ax + by = c 的方程时。
带余除法的定义是什么？
带余除法是指对于整数 a 和 b (b > 0)，存在唯一的整数 q 和 r，使得 a = bq + r，且 0 ≤ r < b。
如何判断线性同余方程是否有解？
若 d = gcd(a, m)，则线性同余方程 ax ≡ b (mod m) 有解当且仅当 d | b。
