第二部分: 数论与关系 (Topic 2: Number Theory and Relations)

mobius week04

2.1 整除性与最大公约数 (Divisibility and GCDs)

• 整除 (Divides): 对于整数a和b，如果存在整数k使得 b=ak，则称a整除b，记作 a∣b。
• 算术基本定理 (Fundamental Theorem of Arithmetic): 任何大于1的自然数都可以唯一地分解为素数的乘积。
• 最大公约数 (Greatest Common Divisor, GCD): 记作 gcd(a, b)。
• 互质 (Coprime): 如果 gcd(a, b) = 1。
• 最小公倍数 (Least Common Multiple, LCM): 记作 lcm(a, b)。
• GCD与LCM的关系: 对于正整数a, b，gcd(a,b)×lcm(a,b)=ab。

2.2 欧几里得算法 (The Euclidean Algorithm)

• 除法定理 (Division Theorem): 对于任意整数a和非零整数b，存在唯一的整数q (商, quotient) 和 r (余数, remainder) 使得 a=qb+r，其中 0≤r<∣b∣。
• 贝祖等式 (Bézout's Identity): 对于任意非零整数a, b，存在整数x, y使得 ax+by=gcd(a,b)。
• 线性丢番图方程 (Linear Diophantine Equation): 形如 ax+by=c 的方程，有整数解的充分必要条件是 gcd(a, b) 整除 c。

2.3 模运算 (Modular Arithmetic)

• 同余 (Congruence): a≡b(modm) 当且仅当 m∣(a−b)。
• 模运算性质:
  • 若 a≡b(modm) 且 c≡d(modm)，则:
    • a+c≡b+d(modm)
    • ac≡bd(modm)
  • 若 ak≡bk(modm) 且 gcd(k,m)=1，则 a≡b(modm) (消去律)。
• 费马小定理 (Fermat's Little Theorem): 如果p是素数，且a不是p的倍数，则 ap−1≡1(modp)。

2.4 线性同余方程 (Solving Linear Modular Congruences)

• 线性同余方程: 形如 ax≡c(modm) 的方程。
• 解的存在性:
  • 设 d=gcd(a,m)。如果 d∤c (d不整除c)，则方程无解。
  • 如果 d∣c，则方程恰好有 d 个模 m 的解。