抽象代数 I · 同态、同构与直积

两个坐标,一起回到零

一个状态是有序对。第一坐标按模 m 加 u,第二坐标按模 n 加 v。要让整个状态回来,两个坐标都得回来。

比较:

整个直积,和走过的那一部分

当前坐标
已走步数
已遇到不同状态

横向读第一坐标,纵向读第二坐标。点内数字是第一次到达的步数;点按一个位置,可以查看完整坐标与它是否可达。

已经走到当前状态虚线框:正在查看

要等两个周期同时结束

保留实际经过的顺序

第 0 步是初始状态,不能把它当成一次正周期。末尾再次出现的 (0,0) 用棕色下划线标出。

CRT:从两份余数找回整数

这一段固定研究 x ↦ (x mod m, x mod n),即每当 x 增加 1,两坐标都加 1。上方选择的步长 (u,v) 不会改变这里的查询规则。

计算里用到了什么

Bézout 系数记为大写 U,V,与上面的步长 u,v 区分。

    有限网格帮助核对具体状态。元素阶公式来自两个坐标的整除条件,CRT 的完整结论来自兼容性、Bézout 等式和解的差;这些一般论证不能由几次模拟代替。