9.1 整除、同余与 Euclid 算法：整数的基本结构
循环缓冲区、周期任务和分片索引都会把整数折回有限范围。要正确处理负数、约分和模逆，先要从整除与带余除法开始，而不是把语言的 % 当成全部数学定义。
整除
对整数 a,b，若存在整数 k：
b=ak则 a 整除 b，记作 a|b。通常讨论除数时要求 a≠0。
基本性质：
a|b 且 a|c → a|(xb+yc)，对任意 x,y∈ℤ
a|b 且 b|c → a|c
a|b 且 b|a → |a|=|b|整除关系在正整数上满足反对称性，因此构成偏序。在全体整数上，2|-2 与 -2|2 同时成立，而 2≠-2，所以不反对称；把 a 与 -a 视为同一类后，才得到类之间的偏序。这里没有“近似成立”的余地。
带余除法
给定整数 a 和正整数 m，存在唯一整数对 (q,r)：
a=qm+r
0≤r<mr 是数学上常用的非负最小剩余。
例如：
-1=(-1)·5+4所以 -1 mod 5=4。
语言的余数运算可能使用向零截断商。Java 中 -1 % 5 == -1；若需要与正模数对应的 floor modulus，可使用：
public class RemainderDemo {
public static void main(String[] args) {
System.out.println(-1 % 5); // -1
System.out.println(Math.floorMod(-1, 5)); // 4
int x = Integer.MAX_VALUE - 1;
int m = Integer.MAX_VALUE;
System.out.println(((x % m) + m) % m); // -3: addition overflow
System.out.println(Math.floorMod(x, m)); // 2147483646
}
}通用的 ((x % m)+m)%m 在部分语言和固定宽整数中还要考虑加法溢出，优先使用标准库的明确 API。
保存为 RemainderDemo.java，用 Java 21 编译运行。floorMod 的结果与除数同号或为零；本课只使用正模数。除数为零会抛出 ArithmeticException。
同余是等价关系
a≡b (mod m) ⇔ m|(a-b)等价地，a,b 除以正整数 m 的非负余数相同。
同余满足自反、对称、传递，因此把整数分成 m 个剩余类：
[0],[1],...,[m-1]模 m 整数常记作 ℤ/mℤ。元素不是某个单独整数，而是同余类；计算时通常选 0...m-1 为代表。
最大公约数
当 (a,b)≠(0,0) 时，gcd(a,b) 是同时整除 a,b 的最大正整数；约定：
gcd(a,0)=|a|
gcd(0,0)=0 // 常见约定，具体 API 应确认若 gcd(a,b)=1，称 a,b 互质。互质不要求二者都是质数，例如 8 与 15。
Euclid 算法
若：
a=qb+r则：
gcd(a,b)=gcd(b,r)因为同时整除 a,b 的数也整除 a-qb=r；反方向同理。
算法：
gcd(a,b):
a=|a|, b=|b|
while b≠0:
(a,b)=(b,a mod b)
return a余数严格小于正除数，过程终止。对 a≥b>0，取余次数为 O(1+log b)，相邻 Fibonacci 数给出最坏增长量级。这是在数取余次数，不是说任意长度的大整数除法只花常数时间；固定宽类型取绝对值时也要处理最小负数。
例：
gcd(252,105)
=gcd(105,42)
=gcd(42,21)
=gcd(21,0)
=21Bézout 恒等式
若 d=gcd(a,b)，存在整数 x,y：
ax+by=d扩展 Euclid 算法在求 gcd 的同时求出系数。
对上例回代：
21=105-2·42
=105-2·(252-2·105)
=5·105-2·252所以一组系数是 x=-2,y=5。
下面使用 Python 3 的任意精度整数。循环始终把两个当前余数写成原始绝对值输入的线性组合，结束后再恢复输入符号：
def extended_gcd(a, b):
r0, r1 = abs(a), abs(b)
x0, x1, y0, y1 = 1, 0, 0, 1
while r1:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return r0, x0 if a >= 0 else -x0, y0 if b >= 0 else -y0
for a, b in [(252, 105), (-252, 105), (0, 0)]:
d, x, y = extended_gcd(a, b)
assert a * x + b * y == d
print((d, x, y))
# (21, -2, 5)
# (21, 2, 5)
# (0, 1, 0)Bézout 还给出线性不定方程：
ax+by=c在 (a,b)≠(0,0) 时，有整数解当且仅当 gcd(a,b)|c。若 a=b=0，方程有解恰好当 c=0。例如 gcd(18,30)=6 不整除 7，所以 18x+30y=7 无整数解。
最小公倍数
对非零整数：
lcm(a,b)=|ab|/gcd(a,b)程序实现应先除后乘：
|a/gcd(a,b) · b|以降低中间乘积溢出的风险，但最终结果仍可能超出类型范围。
若任一输入为零，通常定义 lcm 为零；实现应先处理这条分支，避免在两个输入均为零时计算 0/gcd(0,0)。
两个正周期任务每 a、b 时间触发一次，若从同一起点开始，它们再次同时触发的最短正周期是 lcm(a,b)。若起始相位不同，则要解同余方程，下一课继续。
完成检查
- 计算
gcd(123456,789012)并写出 Euclid 步骤； - 用扩展算法求一组 Bézout 系数；
- 判断
18x+30y=7是否有整数解； - 比较 Java
%与Math.floorMod在负数上的结果； - 证明同余关系的传递性；
- 为两个不同相位的周期任务写出同余条件。