丢番图方程与费马小定理

要求整数解的方程

[[diophantine-equation|丢番图方程]]是普通的方程，但我们坚持解必须是整数。最简单而有趣的情形是线性的 ax + by = c。设想购物：如果铅笔每支 4 枚硬币、钢笔每支 6 枚，你能恰好花掉 30 枚吗？两者都需为整数——半支铅笔是不允许的。

这里有一条简洁的法则，直接源自裴蜀恒等式：ax + by = c 有整数解当且仅当 a 与 b 的最大公约数整除 c。GCD 是 a、b 所能凑出的最小正数，因此 c 必须是它的倍数。

Solve 4x + 6y = 30 in integers.

  gcd(4, 6) = 2, and 2 | 30 → solutions exist.
  Divide through by 2:  2x + 3y = 15.

One solution by inspection: x = 3, y = 3
  (since 2·3 + 3·3 = 6 + 9 = 15). ✓

General solution (k any integer):
  x = 3 + 3k,   y = 3 − 2k.
Check k = 1:  2(6) + 3(1) = 12 + 3 = 15. ✓

因为 gcd(4,6)=2 整除 30，故有解；一个特解可生成全部解。

费马小定理

我们的压轴是一颗 17 世纪的明珠。[[fermats-little-theorem|费马小定理]]说：若 p 是素数且 a 不被 p 整除，则 a^(p−1) ≡ 1 (mod p)。把任意数提升到“比素数小 1”的幂，再取模，结果总会回到 1。一个对每个整数 a 都成立的便利形式是 a^p ≡ a (mod p)。

Check with p = 7, a = 3:
  3^(7−1) = 3^6 = 729
  729 = 7 · 104 + 1  →  3^6 ≡ 1 (mod 7) ✓

Now use it to find 3^100 (mod 7) the fast way:
  By Fermat, 3^6 ≡ 1 (mod 7).
  100 = 6·16 + 4, so
  3^100 = (3^6)^16 · 3^4 ≡ 1^16 · 3^4 (mod 7)
  3^4 = 81 = 7·11 + 4 ≡ 4 (mod 7)
  Therefore 3^100 ≡ 4 (mod 7).

费马定理把一个 48 位的幂化为一行余数计算。

请留意一切是如何串联起来的：定理用模运算叙述，其前提（a 不被 p 整除）是一个互素条件，而我们通过带余除法把指数写成 100 = 6·16 + 4 来加以利用。整条学习路径一直在悄悄拼装这些工具。

这些结果为何重要

这些并非博物馆里的陈列品。费马小定理是快速素性检验和保护互联网的 RSA 密码系统的种子；线性丢番图方程则支撑着排程、齿轮传动比和找零。从“一个整数整除另一个整数”这个朴素想法出发，你已抵达现代数学的实用工具。