auto_ai 知识库

Appearance

初等数论研究整数的性质，是密码学（RSA）和计算机算术的直接数学基础。本笔记覆盖整除与素数、最大公约数与辗转相除法、同余运算、一次同余方程与中国剩余定理、欧拉定理与费马小定理。

整除与素数 ​

整除与带余除法 ​

  • b|a ⇔ 存在整数 c 使 a=bc。性质：a|b 且 a|c ⇒ a|(xb+yc)；a|b 且 b|a ⇒ a=±b
  • 带余除法：a = qb + r，0 ≤ r < |b|；r = a mod b
  • b|a ⇔ a mod b = 0

素数（核心考点） ​

  • 素数：大于 1 且只能被 1 和自身整除；合数 = 非素数的 >1 整数
  • 算术基本定理：任意 a>1 可唯一分解为素因子乘积 a = p₁ʳ¹p₂ʳ²…pₖʳᵏ
  • 因子个数公式：若 a = p₁ʳ¹…pₖʳᵏ，则 a 的正因子个数 = (r₁+1)(r₂+1)…(rₖ+1)
  • 素数无穷多（欧几里得反证法）
  • 素数定理：π(n)（≤n 的素数个数）≈ n/ln n

素数测试 ​

  • 若 a 是合数，则 a 必有 ≤ √a 的素因子（只需试除到 √a）
  • 埃拉托斯特尼筛法：从小到大筛掉素数的倍数，剩下的是素数

最大公约数与最小公倍数（考点） ​

  • gcd(a,b)、lcm(a,b)；gcd(0,a)=a；gcd(1,a)=1
  • 素因子分解法：各素因子取最小指数得 gcd、取最大指数得 lcm
  • 辗转相除法（欧几里得算法）：gcd(a,b) = gcd(b, a mod b)，重复直到余数 0
例：gcd(715,210)：715=3·210+85，210=2·85+40，85=2·40+5，40=8·5 → gcd=5
  • Bezout 定理：gcd(a,b) = xa + yb（辗转相除法回代求 x,y）
  • 互素：gcd(a,b)=1 ⇔ 存在整数 x,y 使 xa+yb=1

同余（考点） ​

定义与性质 ​

  • a≡b(mod m) ⇔ m | (a−b) ⇔ a mod m = b mod m ⇔ a = b + km
  • 同余是等价关系（自反、对称、传递），模 m 等价类构成 Zₘ
  • 模算术：a≡b, c≡d (mod m) ⇒ a±c≡b±d, ac≡bd (mod m), aᵏ≡bᵏ
  • 消去限制：c 与 m 互素时，ca≡cb(mod m) ⇒ a≡b(mod m)

应用 ​

  • 求个位数：如 3⁴⁵⁵ mod 10，利用 3⁴≡1(mod 10) 降幂
  • 日期星期几计算（蔡勒公式类）

一次同余方程与中国剩余定理（重点） ​

一次同余方程 ​

  • 方程 ax≡c(mod m) 有解 ⇔ gcd(a,m) | c
  • 模 m 逆：ab≡1(mod m)，b 记作 a⁻¹。a 的模 m 逆存在 ⇔ gcd(a,m)=1（此时唯一）
  • 求逆：解方程 / 辗转相除法回代 / 观察

中国剩余定理（孙子定理） ​

方程组 x≡aᵢ(mod mᵢ)（m₁,…,mₖ 两两互素）有唯一解（模 M=m₁…mₖ 下）：

求解步骤：① M = m₁…mₖ → ② Mᵢ = M/mᵢ → ③ 求 Mᵢ 的模 mᵢ 逆 Mᵢ⁻¹ → ④ x ≡ Σ aᵢMᵢ⁻¹Mᵢ (mod M)

"物不知数"：x≡2(mod 3), x≡3(mod 5), x≡2(mod 7) → x ≡ 23 (mod 105)。

大整数算术（模表示） ​

取两两互素的 m₁,…,mₖ，任意 x < M 用 (x mod m₁, …, x mod mₖ) 表示，加减乘可对各分量独立做（如取 mᵢ=2³²−1 等实现超大整数运算）。

欧拉定理与费马小定理（重点） ​

欧拉函数 ​

  • φ(n) = {0,…,n−1} 中与 n 互素的数个数
  • n 为素数时 φ(n) = n−1
  • 计算：φ(n) = n·Π(1−1/pᵢ)（容斥原理推导）

两大定理（必背） ​

定理内容前提
欧拉定理a^φ(n) ≡ 1 (mod n)gcd(a,n)=1
费马小定理a^(p−1) ≡ 1 (mod p)p 为素数，p∤a
费马小定理变形aᵖ ≡ a (mod p)p 为素数，任意 a
  • 应用：大指数降幂（a^b mod n 先对指数模 φ(n)）、判断合数（费马测试）

一句话总结 ​

数论主线：分解（算术基本定理）→ gcd（辗转相除）→ 同余（等价类）→ 同余方程（中国剩余定理）→ 欧拉/费马定理（降幂与 RSA 基础）；逆元存在 ⇔ 互素是判断金钥匙。

相关概念 ​