《整除思维导图》

一、核心概念

1.1 整除的定义

• 定义： 设 a, b 为整数，b ≠ 0，若存在整数 q，使得 a = bq，则称 a 能被 b 整除，记作 b | a。
• 符号： " | " 代表整除关系。
• 术语：
  • a 是被除数
  • b 是除数
  • q 是商
• 整除的含义： 除尽，没有余数。

1.2 约数（因数）与倍数

• 约数（因数）： 若 b | a，则称 b 是 a 的约数或因数。
  • 1 和 -1 是任何整数的约数。
  • 一个整数的约数总是成对出现（除了完全平方数）。
• 倍数： 若 b | a，则称 a 是 b 的倍数。
  • 0 是任何整数的倍数。

1.3 公约数与最大公约数 (GCD)

• 公约数： 几个整数共有的约数称为它们的公约数。
• 最大公约数 (GCD)： 几个整数共有的约数中最大的一个，记作 gcd(a, b) 或 (a, b)。
  • 求最大公约数的方法：
    • 辗转相除法（欧几里得算法）： gcd(a, b) = gcd(b, a mod b)，直到 a mod b = 0，则 b 为最大公约数。
    • 更相减损术： gcd(a, b) = gcd(b, a-b) (a>b)，直到 a=b，则a(或b)为最大公约数。
    • 质因数分解法： 分解每个数的质因数，取公共质因数的最低次幂的乘积。
• 互质： gcd(a, b) = 1，则称 a 和 b 互质。

1.4 公倍数与最小公倍数 (LCM)

• 公倍数： 几个整数共有的倍数称为它们的公倍数。
• 最小公倍数 (LCM)： 几个整数共有的倍数中最小的一个，记作 lcm(a, b) 或 [a, b]。
  • 求最小公倍数的方法：
    • 公式法： lcm(a, b) = (a * b) / gcd(a, b)。
    • 质因数分解法： 分解每个数的质因数，取所有质因数的最高次幂的乘积。

二、整除的性质

2.1 基本性质

• 传递性： 若 a | b，b | c，则 a | c。
• 线性组合： 若 a | b，a | c，则对于任意整数 x, y，有 a | (bx + cy)。
• 乘法性质： 若 a | b，则对于任意整数 c，有 a | (bc)。
• 加减性质： 若 a | (b + c)，且 a | b，则 a | c。若 a | (b - c)，且 a | b，则 a | c。
• 约数倍数关系： 若 a | b，则 a ≤ b 或 a = -b (b为正整数)。

2.2 特殊数的整除特征

• 2 的倍数： 个位数字为偶数 (0, 2, 4, 6, 8)。
• 3 的倍数： 各个位上的数字之和是 3 的倍数。
• 4 的倍数： 末两位数字能被 4 整除。
• 5 的倍数： 个位数字为 0 或 5。
• 6 的倍数： 同时满足是 2 的倍数和 3 的倍数。
• 7 的倍数： 将末位数字乘以 2，用前面的数减去它，如果差能被 7 整除，则这个数能被 7 整除。(也可循环使用)
• 8 的倍数： 末三位数字能被 8 整除。
• 9 的倍数： 各个位上的数字之和是 9 的倍数。
• 10 的倍数： 个位数字为 0。
• 11 的倍数： 奇数位上的数字之和与偶数位上的数字之和的差是 11 的倍数（包括 0）。
• 25 的倍数： 末两位数字能被 25 整除。

2.3 与质数相关的性质

• 质数的定义： 大于 1 的正整数，除了 1 和它本身，没有其他约数。
• 合数的定义： 大于 1 的正整数，不是质数的数。
• 算术基本定理： 任何大于 1 的整数都可以唯一地分解为质因数的乘积。
• 质因数分解的应用： 求约数个数、求最大公约数和最小公倍数。

三、整除的应用

3.1 整数拆分与分组

• 拆分： 将一个整数拆分成若干个整数的和或积，用于简化计算或分析。
• 分组： 将一组数按照某种规则分组，例如按奇偶性、是否能被某个数整除等。

3.2 同余理论基础

• 同余的定义： 若 a 和 b 除以 m 的余数相同，则称 a 和 b 模 m 同余，记作 a ≡ b (mod m)。
• 同余的性质：
  • 反身性： a ≡ a (mod m)。
  • 对称性： 若 a ≡ b (mod m)，则 b ≡ a (mod m)。
  • 传递性： 若 a ≡ b (mod m)，b ≡ c (mod m)，则 a ≡ c (mod m)。
  • 加法： 若 a ≡ b (mod m)，c ≡ d (mod m)，则 a + c ≡ b + d (mod m)。
  • 减法： 若 a ≡ b (mod m)，c ≡ d (mod m)，则 a - c ≡ b - d (mod m)。
  • 乘法： 若 a ≡ b (mod m)，c ≡ d (mod m)，则 ac ≡ bd (mod m)。
  • 乘方： 若 a ≡ b (mod m)，则 a^n ≡ b^n (mod m) (n 为正整数)。
• 同余的应用： 简化计算、判断整除性、解决剩余问题（例如孙子定理）。

3.3 解不定方程

• 不定方程： 未知数个数多于方程个数的方程。
• 利用整除性质解不定方程： 通过分析方程中各项的整除性质，缩小未知数的取值范围，进而求解。
• 例： ax + by = c，如果 gcd(a, b) 不能整除 c，则方程无整数解。

3.4 数论问题

• 素数判断： 判断一个数是否为素数。
• 约数个数的计算： 如果一个数 N 质因数分解为 p1^a1 p2^a2 ... * pn^an, 那么 N 的约数个数为 (a1+1)(a2+1)...(an+1)。
• 数论函数的计算： 例如欧拉函数。

四、例题分析

(此处可插入具体的例题，例如判断整除性，求最大公约数和最小公倍数，解不定方程，以及应用整除性质的实际问题。)

五、总结

• 重要性： 整除是数论的基础，也是解决很多数学问题的关键。
• 学习方法： 掌握基本概念和性质，多做练习，培养数感。
• 进一步学习： 深入学习同余理论、数论函数等。

上一个主题： 西游记思维导图 下一个主题： 球类思维导图