OI-wiki
OI-wiki copied to clipboard
OI-wiki
refactor(math/algebra): 重写抽象代数部分
- [x] 我已认真阅读贡献指南 (contributing guidelines) 和社区公约 (code of conduct)，并遵循了如何参与页及格式手册页的相应规范。
10.17 UPDATE: 本 PR 主体内容基本完成，接下来将会将所有更改分成多个 PR 提交，以便审核。
本 PR 尚在草稿阶段，仍需大量修改和内容的添加，欢迎大家的批评建议！
本 PR 考虑解决 #5356 的问题。具体修改如下：
- [x] 重命名 群论 文件夹为 抽象代数
- [x] 将群、环、域的介绍放到基本概念部分，并添加实例帮助理解
- [x] 群论部分修改如下：
- [x] 在开头分析 $D_6$ 的结构，作为全文帮助概念理解的例子
- [x] 基础概念组织在 子群、群同态、群作用 三个章节
- [x] 最后给出有限生成 Abel 群的分类定理
- [x] 环论部分增加如下内容：
- [x] 环同态、理想、素理想与极大理想
- [x] 整环、Euclid 整环、PID、UFD、例子：二次整数环
- [x] 中国剩余定理、应用：模 $n$ 整数乘法群的结构
- [x] 多项式环
- [x] 改写 置换和排列 页面
- [x] 重组 置换 和 排列 的现有内容，删去了无意义的重复内容
- [x] 增加轮换的相关内容
- [x] 补充逆序数的算法
- [x] 合并康托展开页面
- [x] 改写 Polya 计数章节：
- [x] 将它移动到 组合数学 章节，因为它主要是用于计数，而不是群结构的分析
- [x] 重写，让内容更强调定理在解决实际计数问题中的应用，并减少它对群论知识的依赖
- [x] 增加带权版本的 Polya 计数定理
- [x] 增加了常见空间对称群的置换表示的讨论
- [x] 增加了若干例子，增加了习题
- [x] 合并计算群论的 Schreier–Sims 算法，这个完全不懂，但是似乎应该合进来
- [x] 修正了波及到的文件内链接和 redirects 文件
Q: 为什么按照上面方式选取内容？
A: 以上内容的编排很大程度上参考了 Dummit & Foote，但是删去了有限群结构理论（比如 Sylow 定理）[update: 还是得加 Sylow 定理，不然应用的时候太掣肘了，但是什么 N/C 定理、自同构群、幂零群之类的就算了吧] 等无关内容，并且做了部分调整，尽量使得知识结构是线性推进的。文中尽量增加了解释定义和定理的动机的语句，便于不熟悉严格数学语言的读者阅读。
Q: 尚无意向增加域的内容？ A: 因为群论和环论多多少少都和 OI 中的概念相关，但是域论（包括 Galois 理论）似乎没有很明晰的联系。尽管数论中有二次域章节，但是即使是二次域章节，我也没有遇到需要这一理论的实际应用，且二次整数和 Pell 方程的相关内容可能会在环论中简单讨论。
Q: 为什么采用这个记号而不是那个记号？ A: 记号的处理也很大程度上参考了 Dummit & Foote。抽代的记号和命名经常很混乱，所以考虑在相关位置增加附注的方式解释可能的记号差异。
Q: 为什么没有证明？ A: 为了行文流畅（可能并没有），还没写，以及并不确定要不要写。
Q: 有必要写抽象代数部分吗？ A: 说句实在的，其实没有必要。就是不会抽象代数，也不耽误写代码。但是，很多 OI 选手的博客，也包括 OI Wiki 自己，有时候会使用抽象代数的语言，Polya 计数等内容也似乎基于抽象代数。所以，增加抽象代数的内容可能有助于理解其他具体的知识。但是正如 issue 中指出的，现有章节组织并不合理，所以进行了部分改进，算是抛砖引玉，欢迎大家进一步改进。
一点建议，可以考虑简单介绍一下 Commutative diagram，然后用它简单说明一下定理的证明思路来加深理解。不必非要用范畴论的语言介绍，直接简化成集合论的就行 🤔
能具体说一下在什么证明里用交换图表吗，还没想好要不要给结论都补上证明。那如果加交换图表之后，还要介绍商环之类的万有性质吗？
能具体说一下在什么证明里用交换图表吗，还没想好要不要给结论都补上证明。
主要应该就是涉及到同态/同构的定理，比如你可以参考下 https://note.shad0wash.cc/math/AbstractAlgebra/ChapterI/Lec2/
那如果加交换图表之后，还要介绍商环之类的万有性质吗？
可以
shad0wash 的笔记本
一些想法：
在“阶”一节增加费马小定理的内链，并在费马小定理处增加至此的内链。 在“形式幂级数环”处加上通往多项式与生成函数目录下相应位置的内链，并在该位置增加回指的内链。
目录安排的很好。置换与排列改写的很好。
“### 应用：整数剩余系的乘法群
相关阅读：原根
作为中国剩余定理和群论相关内容的一个应用，这里讨论整数模 $n$ 乘法群的结构。本节略去剩余系的横线记号。”
这大概不是应用，而是一个完整的节，因为这东西确实非常常用，而数论部分并没有写。去掉“应用”二字，提为“##”二级标题，并在p=2与为奇素数处增设两个“###”三级标题。
（北大潘承洞版《初等数论》用了“指标组”概念刻画此类结构，它事实上就是离散对数）
“### 应用：整数剩余系的乘法群
相关阅读：原根
作为中国剩余定理和群论相关内容的一个应用，这里讨论整数模 n 乘法群的结构。本节略去剩余系的横线记号。”
这大概不是应用，而是一个完整的节，因为这东西确实非常常用，而数论部分并没有写。去掉“应用”二字，提为“##”二级标题，并在p=2与为奇素数处增设两个“###”三级标题。
（北大潘承洞版《初等数论》用了“指标组”概念刻画此类结构，它事实上就是离散对数）
感谢您的关注。别的意见正在逐步修改中，但是对于这一条恕我不能同意。
如果相关内容在数论中有重要的应用，应当放在数论的栏目下开设页面讨论。但是就本次修改而言，这些只是抽象代数理论的应用（或例子）而已。抽象代数的理论不会关心它所能导出的结论在数论中的作用，因此，这一部分在本页面不应该成为独立的小节。
正在考虑在中国剩余定理栏目增设 应用：Lagrange 插值，介绍 Lagrange 插值是如何作为中国剩余定理在多项式环上的简单推论导出的。同样的理由，它不应当成为本页面的独立小节，尽管可能 OI Wiki 现有页面的确没有关于 Lagrange 插值的专门介绍（但是有复杂度更低的快速插值）。
这些例子或是应用的引入，只是为了让读者不会觉得抽象代数的理论过于无用，仅此而已。本页面对于这些内容在其专门领域的作用不甚关心。希望您能理解这一想法。
正在考虑在中国剩余定理栏目增设 应用：Lagrange 插值，介绍 Lagrange 插值是如何作为中国剩余定理在多项式环上的简单推论导出的。同样的理由，它不应当成为本页面的独立小节，尽管可能 OI Wiki 现有页面的确没有关于 Lagrange 插值的专门介绍（但是有复杂度更低的快速插值）。
印象里“Lagrange 插值”这个好像是线性代数部分的，在李尚志版的《线性代数》里面搞了一章装下了Lagrange 插值、中国剩余定理等
正在考虑在中国剩余定理栏目增设 应用：Lagrange 插值，介绍 Lagrange 插值是如何作为中国剩余定理在多项式环上的简单推论导出的。同样的理由，它不应当成为本页面的独立小节，尽管可能 OI Wiki 现有页面的确没有关于 Lagrange 插值的专门介绍（但是有复杂度更低的快速插值）。
印象里“Lagrange 插值”这个好像是线性代数部分的，在李尚志版的《线性代数》里面搞了一章装下了Lagrange 插值、中国剩余定理等
我无法认同您的“Lagrange 插值 是线性代数理论的内容”这一说法。提起 Lagrange 插值公式，大家想到的可能更多地还是多项式理论（或者一些分析中的结论）。但是，作为线性代数理论的一个应用，Lagrange 插值公式确实可以从多项式的线性方程组中求解得出（如果这么说，所有反演都是线性代数理论，因为它们都是某个矩阵的逆）。所以，如果您有兴趣在线性代数部分补充它作为应用之一，我也是支持的。
不过，将某项结论分成不同的领域本就是意义不大的。深刻的结果，可能同多个领域的理论都可以建立联系。仅从书写 OI Wiki 的角度出发，如果想专门地添加某个条目（而不是作为副产品），应当将它们放在更符合应用需求、更便于大家查找的位置。这也是为什么本 PR 希望能将 Polya 计数放入排列组合而不是群论（而且顶着置换群的名字）。同样地，如果将数论的结论和多项式的结论藏在抽象代数的章节下，可能也无法满足大家按照目录查找的需求。
（不过确实很想吐槽现在的目录已经很臃肿了，如果开一个重新调整（数学部分的）目录的 issue 或者 pr 会被喷吗……）
（不过确实很想吐槽现在的目录已经很臃肿了，如果开一个重新调整（数学部分的）目录的 issue 或者 pr 会被喷吗……）
既然您总在说一些“我无法认同”等，那我觉得目前这个样子确实已经很好了。希望早日能尽快完成更新。
至于诸如“目录臃肿”等，提出的诸多缺陷啥的，我相信未来的强手还是层出不穷、后浪推前浪的。即使你不写、我不写，也有的是人写。所以我是不怕缺陷的。即使当下有再多的缺陷，迟早也会有更正的一天。
不过，如果您愿意写，那当然是多多益善了。不仅不会被喷，还应当鼓励。如果有一天真的彻底没人写了，那才是可怕的事情。如果不写，就永远不会进步，只会意味着圈子彻底地冷掉。没有活人的领域还能叫领域吗？还是希望大家勇敢的去写。
（不过确实很想吐槽现在的目录已经很臃肿了，如果开一个重新调整（数学部分的）目录的 issue 或者 pr 会被喷吗……）
既然您总在说一些“我无法认同”等，那我觉得目前这个样子确实已经很好了。希望早日能尽快完成更新。
至于诸如“目录臃肿”等，提出的诸多缺陷啥的，我相信未来的强手还是层出不穷、后浪推前浪的。即使你不写、我不写，也有的是人写。所以我是不怕缺陷的。即使当下有再多的缺陷，迟早也会有更正的一天。
不过，如果您愿意写，那当然是多多益善了。不仅不会被喷，还应当鼓励。如果有一天真的彻底没人写了，那才是可怕的事情。如果不写，就永远不会进步，只会意味着圈子彻底地冷掉。没有活人的领域还能叫领域吗？还是希望大家勇敢的去写。
所以您的建议是在线性代数部分增加中国剩余定理和 lagrange 插值？
kind reminder: @Great-designer 不是oiwiki的编辑，相关建议和讨论不会被enforce，不会影响pr的审核和合并。（你可以认为是一个random的爱好者在和你讨论，如果感到困扰的话可以忽略）
kind reminder: Great-designer 不是oiwiki的编辑，相关建议和讨论不会被enforce，不会影响pr的审核和合并。（你可以认为是一个random的爱好者在和你讨论，如果感到困扰的话可以忽略）
如果真的不是编辑，只是爱好者的话，不需要at。at之后又加粗高亮显示，显得像个编辑一样。我只是之前在这里编辑过。
所以您的建议是在线性代数部分增加中国剩余定理和 lagrange 插值？
我建议早日合并。至于哪里增加啥，不重要。
我有个问题，就是为啥这个 pr 要整这么大而不是拆成很多个部分🧐因为修改内容会环环相扣吗 现在这个太大了不是很利于 review。
现在的目录已经很臃肿了，如果开一个重新调整（数学部分的）目录的 issue 或者 pr
确实存在这样的现象。我正在规划一个整体而彻底的修整（但近日事务繁多导致一直没动）
我建议早日合并。至于哪里增加啥，不重要。
这样的态度是对 contributor （以及任何花费心思参与此课题的人）的极大不尊重。我建议您最好不要再在本 wiki 相关的讨论中使用此种态度。如果您真的如此漠不关心内容，请不要再试图参与此类讨论。
我有个问题，就是为啥这个 pr 要整这么大而不是拆成很多个部分🧐因为修改内容会环环相扣吗 现在这个太大了不是很利于 review。
这个有点计划赶不上变化了，确实是我经验不足的锅。
因为抽象代数部分本身只有一个文件，然后需要裂成三个文件（基本概念、群论、环论），然后原本的群论文件夹中还有名为置换群实为 Polya 计数的文件，我寻思拖出去但是原封不动也不好，就也顺手改了，但是这又牵涉到置换和排列那部分内容不完善，不能适应别的部分的需求，我也顺手改了。结果就是现在这样。
现在问题是，本 pr 已经既成事实，有什么办法能分离这些 commitment 吗？比如说，可以分成三个 pr：
- 置换和排列
- Polya 计数
- 抽象代数部分
还是我只要把文件 copy 到别的 batch 重新开 pr 就可以了？
这样的态度是对 contributor （以及任何花费心思参与此课题的人）的极大不尊重。我建议您最好不要再在本 wiki 相关的讨论中使用此种态度。如果您真的如此漠不关心内容，请不要再试图参与此类讨论。
试问，您见过“漠不关心的人”，写过这多东西，经常给项目点赞，很少反对什么事，总被批评与点踩，还需要总乐呵呵的这样的人？
此项目是一个课题吗？如果确实有一个老师带着课题组，而非正在运营的网站，这课题可能有一些久远了。
我到这里留言，还得专门挂梯子，还得遭受邮件轰炸，并非容易之事。梯子钱都花了好几百了。
现在问题是，本 pr 已经既成事实，有什么办法能分离这些 commitment 吗？比如说，可以分成三个 pr：
- 置换和排列
- Polya 计数
- 抽象代数部分
还是我只要把文件 copy 到别的 batch 重新开 pr 就可以了？
我觉得都可以。辛苦了
这样的态度是对 contributor （以及任何花费心思参与此课题的人）的极大不尊重。我建议您最好不要再在本 wiki 相关的讨论中使用此种态度。如果您真的如此漠不关心内容，请不要再试图参与此类讨论。
试问，您见过“漠不关心的人”，写过这多东西，经常给项目点赞，很少反对什么事，总被批评与点踩，还需要总乐呵呵的这样的人？
此项目是一个课题吗？如果确实有一个老师带着课题组，而非正在运营的网站，这课题可能有一些久远了。
我到这里留言，还得专门挂梯子，还得遭受邮件轰炸，并非容易之事。梯子钱都花了好几百了。
有话请好好说，有观点请明确陈明出来。拐弯抹角阴阳怪气暗戳戳地指点是破坏社区交流环境的行为，如果你继续如此发言，我认为有必要对此进行处理。
不论你自述你是怎样的人，「至于哪里增加啥，不重要。」这句话已经足够佐证我的陈述，这就是在否定别人的努力并表达你的漠不关心。
大家都是成年人，该知道自己做的选择自己负责。你自陈所谓的「被邮件轰炸」，我们参与讨论的这些人都一样被轰炸。我们或许可以理解你的不便之处，但这绝不能为你的冒犯行为背书。
不论你自述你是怎样的人，「至于哪里增加啥，不重要。」这句话已经足够佐证我的陈述，这就是在否定别人的努力并表达你的漠不关心。
那么我明确陈明：这只是“欲加之罪何患无辞”罢了。既然我是爱好者，并非编辑，那么我的上述叙述已经尽了我的本分。站在该视角，我并没有否定任何人的努力，相反，很显然我一直在被别人予以否定。
如果您确实是此课题的主管老师，那么您也确实允许拥有该主见。我对此并没有办法。
尽管可能 OI Wiki 现有页面的确没有关于 Lagrange 插值的专门介绍（但是有复杂度更低的快速插值）。
实际上是有的，不仅有 Lagrange 插值还有 Newton 插值，只不过内容比较少而已。
https://oi-wiki.org/math/numerical/interp/
OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛
尽管可能 OI Wiki 现有页面的确没有关于 Lagrange 插值的专门介绍（但是有复杂度更低的快速插值）。
实际上是有的，不仅有 Lagrange 插值还有 Newton 插值，只不过内容比较少而已。
https://oi-wiki.org/math/numerical/interp/
**插值 - OI Wiki**OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛
谢谢提醒，最近翻目录也翻到了这个。会在中国剩余定理的相关位置加一个它的内链的。
OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛
本页面的域论内容已经写好了，欢迎大家 review！
本 PR 做了如下修改：
- 增加了域论内容
- 域的扩张理论
- 分圆域、分圆多项式
- 有限域，附参考实现
- 域扩张的应用
- 在抽象代数其他页面增加向域论页面的内链
- 修改了目录文件
- 感覺完美域的定義和特徵不如反過來寫：定義寫成「如果域 $F$ 上的代数扩张都是可分扩张则称域 $F$ 为 完美域（perfect field）。」 ，然後後面證明域 $F$ 是完美域當且僅當特徵為0，或者特徵為 $p$ 且所有元素都有 $p$ 次根。
- 要不要提一下有限群本原元和模 $q$ 原根的關係呢？感覺有人會弄混。
- 「推广到环上的扩张」這個是說integral extension吧，但是感覺完全沒有必要這麼理解。有兩個建議：
- 「计算余数 $(1-x)^n-x^n \mod x^2-x-1$ 的常数项即可」可否解釋一下為什麼分母的 $1-2x$ 沒了？
- 這裏我感覺有個更好的理解方式，只用群的知識就可以。我寫在下面了
=============
令 $\varphi: \mathbb{Z}[x]\to \mathbb{Z}$ 為滿足 $\varphi(x^n) = f(n)$ 的群同態。顯然有 $\varphi(x^2-x-1) = 0$ ，所以 $\forall P\in\mathbb{Z}[x], \varphi(P) = \varphi(P\mod x^2-x-1)$ 。對任意 $m\in\mathbb{Z}$ ，同樣定義 $\varphi_m: (\mathbb{Z}/m)[x]\to (\mathbb{Z}/m)$ 為滿足 $\varphi_m(x^n) = f(n)\mod m$ 的群同態（顯然存在且唯一），則同樣有 $\varphi_m(x^2-x-1) = 0$ ，所以類比處理就可以知道 $f(n)\mod m = \varphi_m(x^n) = \varphi_m(x^n \mod x^2-x-1)$ 。
@zjkmxy 您好，谢谢您的建议。
对于前两条，我很赞同您的意见，会尽快修改。
对于第三条，分母的 $1-2x$ 没有消失，只是在计算了余式（remainder）之后只保留了常数项。因为此处的推理说明余式是 $f(n)(1-2x)$，所以只要考虑常数项就可以了。
对于您的新的理解方式，我想请教一下，您的这种思路对于更广泛的情形是否也是成立的？比如说，在问题 CF1103E 中，标答需要在 $\mathbf Z_{2^{58}}$ 上对 $\Phi_5(x)$ 做「扩张」，并利用得到的原根进行快速 Hadamard-Walsh 变换。
我写这个小节的本意并不是仅讨论斐波那契数列的计算，而是希望借此讨论一种方法，能够对任意模数做类似扩域的处理。但是我不想引入诸如 CF1103E 这种看起来就很复杂的问题，所以还是借着斐波那契数列的计算做了一些讨论。我主要是觉得，我所给出的讨论，从扩域的想法上看是自然的，操作在数学上也是合法的（OI Wiki 在 此处 有这个例题的讲解，但是用的语言很粗糙，在数学上并不严格），而且清晰地给出了这类方法的适用范围，即需要一个不依赖于除法或者除法造成的影响在当前模数下可控的计算过程。
不知道您对这类一般性的问题有没有更好的想法？
另外，我觉得您给的思路中，要把每个步骤展开说明，可能也不是容易的。例如，\varphi(P) = \varphi(P mod x^2-x-1) 这一步，在不引入环的结构的情况下，应该不能从 \varphi(x^2-x-1) 直接推出，可能需要从 \varphi(x^{k+1}-x^k-x^{k-1)) 入手做一个归纳的证明。或者是我没有想通，如果是这样，还请您指教。
相反，虽然我没有明说，但是本质上我只是说明了环同构 Z[x]/(m) \cong (Z/(m))[x]。这个可能更显然一些？
谢谢！
对于第三条，分母的 1 − 2 x 没有消失，只是在计算了余式（remainder）之后只保留了常数项。因为此处的推理说明余式是 f ( n ) ( 1 − 2 x ) ，所以只要考虑常数项就可以了。
原來如此，多謝指教。
对于您的新的理解方式，我想请教一下，您的这种思路对于更广泛的情形是否也是成立的？
是可以的。我多寫一點廢話好了。
例如，\varphi(P) = \varphi(P mod x^2-x-1) 这一步，在不引入环的结构的情况下，应该不能从 \varphi(x^2-x-1) 直接推出
可以的，這個是商群的等價定義：對於交換群 $G$ 和子群 $N\subseteq G, i:N\hookrightarrow G$ ($i$ 是恒等映射)，群 $Q$ 稱為 商群 $G/N$ 當且僅當以下兩個條件滿足：
- 存在投影映射 $\pi: G\to Q$ 使得 $\pi\circ i = 0$
- 「普遍性(universality)」如果有另一個 $Q'$ 和 $\pi':G\to Q'$ 同樣滿足條件1： $\pi'\circ i = 0$ 。那麼 $Q'$ 一定「經過」 $Q$，即存在同態 $f: Q\to Q'$ 使得 $\pi' = f\circ\pi$ 。注意條件2確保這樣的群在同構下必然是唯一的。
證明原來的 $G/N$ 滿足新的定義
因為是交換群，這裏用記號 $G/N = {g+N: g\in G}$, $(g_1+N)+(g_2+N) = (g_1+g_2)+N$ 。 定義 $\pi: G\to G/N$ 為 $\pi(g) = g+N$ ，則條件1滿足。以下只需要證明條件2。
假設有 $Q'$ 和 $\pi':G\to Q'$ 使 $\pi'\circ i = 0$。我們定義 $f:G/N\to Q'$ 為 $f(g+N) := \pi'(g)$ 。 這個定義是合法群同態，因為 $\forall n\in N,\pi'(n) = 0$，所以陪集 $g+N$ 可以取其中任何一個代表元素來計算 $f(g+N)$ 。然後 $f((g_1+N)+(g_2+N)) = f(g_1+N) + f(g_2+N)$ 顯然。
對任意 $g\in G$，假設 $g+N$ 的代表元是 $g+n$ ， $n\in N$ 。那麼
$f(\pi(g)) = f(g+N) = \pi'(g+n) = \pi'(g) + \pi'(n) = \pi'(g)$
現在回到Fibonacci的例子：令 $N$ 為 $x^2-x-1$ 生成的理想， $G:=\mathbb{Z}[x]$ ， $Q':= \mathbb{Z}$ ， $\pi' := \phi$ 為多項式環到整數的群同態。直接代入上面的條件2就可以得出 $\phi(p) = f(\pi(p)) = \phi(p\mod (x^2-x-1))$ 。
本质上我只是说明了环同构 Z[x]/(m) \cong (Z/(m))[x]。这个可能更显然一些？
我的思路對取模的話其實原本是模(module)上的幾個小命題。因為所有的交換群都自動是 $\mathbb{Z}$-模，所以就把模相關的東西隱去了。這裏正式地列一下好了。
- 假設 $A$ 為交換幺環。一個交換群 $M$ 如果有如下 $A$ 的環作用，則 $M$ 稱為 $A$-模(module)。對所有 $a,b\in A, x,y\in M$
- 左右分配率： $(a+b)x = ax+bx, a(x+y)=ax+ay$
- 乘法和作用的結合率： $(ab)x = a(bx)$
- 環單位元也是作用的單位元： $1x=x$
對於理想 $I\subsetneq A$ ， $A/I$ 也是交換幺環。
- （命題1） $M/IM$ 是 $A/I$-模。
證明：因為 $\forall a,b\in A, aI = I, aIM = IM$ ，所以顯然。
記 $M$ 對取 $I$ 模對投影群同構為 $\pi_I: M\to M/IM, \pi_I(x):=x+IM$ 。
- （命題2）對 $A$-模 $M,N$ 和模同態 $f:M\to N$ ，可以定義 $f_I: M/IM\to N/IN$ 為 $\forall a+IM\in M/IM, f_I(a+IM) = f(a)+IN$ 。則 $f$ 與 $\pi_I$ 「交換」： $f_I\circ\pi_I = \pi_I\circ f$ 。
證明
$f_I$ 是模同態：
- $f_I(ax+IM) = f(ax)+IN = af(x)+IN = af(x+IM)$
- $f_I(x+y+IM) = f(x+y)+IN = f(x)+f(y)+IN = f(x+IM)+f(y+IM)$
$f$ 與 $\pi_I$ 「交換」：
$f_I\circ\pi_I (x) = f_I(x+IM) = f(x)+IN = \pi_I(f(x))$
- （命題3） $\pi_I$ 是 $A$-模範疇到 $A/I$-模範疇的函子(functor)，換言之映射$\pi_I$ 和相配的同態映射 $f\mapsto f_I$ 在命題2的基礎上，保持函數的組合和恆等同態。
證明
$f_I$ 保持恆等同態：令 $1_M: M\to M$ 定義為 $1_M(x) = x$ ，則顯然 $(1_M)I = 1{M/I}$
$f_I$ 保持函數的組合：設 $f:L\to M$ 和 $g:M\to N$ ， $l\in L$ 。則
$(f\circ g)_I(l+IL) = (f\circ g)(l) + IN = f_I(g(l) + IM) = f_I(g_I(l+IL))$
有令命題3，我們知道 $\pi_I$ 保持所有的交換圖。這就是為什麼對m取模幾乎不改變任何事情。
對Fibonacci數列，取 $g:\mathbb{Z}[x]\to \mathbb{Z}$ 為包括 $g(x^n)=f(n)$ 的唯一群同態， $P=(x^2-x-1)\mathbb{Z}[x]$ ，則有交換圖 $P\hookrightarrow \mathbb{Z}[x]\to \mathbb{Z}$ 和 $P\to 0 \to \mathbb{Z}$ 交換，說明 $\forall p\in \mathbb{Z}[x], f(p) = f(p \mod (x^2-x-1))$ 。直接在圖上應用 $\pi_{\mathbb{Z}/m\mathbb{Z}}$ 即得到模 $m$ 下的一個類似的交換圖，所以 $f(p)\mod m = f(p\mod (x^2-x-1)) \mod m$ 。這樣我們就把上面對整數用的公式拉到模 $m$ 下了。
如果要再引申的話，實際上還有個定理：短正合序列 $0\to L\to M \to N\to 0$ 在 $\pi_I$ 後變成正合序列 $L/IL\to M/IM \to N/IN\to 0$ ，即唯一的變化是最左邊的單射不必然維持單射了。
比如说，在问题 CF1103E 中标答需要在 $Z_{2^{58}}$ 上对 $\Phi_5(x)$ 做「扩张」，并利用得到的原根进行快速 Hadamard-Walsh 变换。
這個問題跟Fibonacci的問題我感覺不太一樣，我環需要想一想。 我的理解是，FFT/FWT的部份和除法取模的部份根本是分開的，如果把UFWT理解成先做一個不帶除法的東西，再去除分母。 FWT的部份感覺可以直接理解成他在 $\mathbb{C}$ 上做的，只是用 $x$ 來表示 $1$ 的10次根，並且輸入和輸出都碰巧是整數。做完再回頭算除法和取模。
@zjkmxy 您好，多谢您的回复，十分受教。
我之前提到的问题还是存在的：是否可以不依赖于环的结构简单说明 $\pi' \circ i = 0$？这个和后续的推演都没有关系，而且看起来十分显然。但是它在引入了环的结构之后看起来比单纯在群里做证明，要简单得多？
我觉得您的想法对于解决斐波那契数列的问题是很好的，但是有些过于深刻了。在原 issue 的讨论中，有 评论 提及到没有必要引入模论，这也是为什么在写的时候直接从环论跳到了域论。
说起来写这个抽代的简介，内心一直就是十分矛盾的：既觉得算法竞赛中没有考这玩意的，根本就没有必要写，又觉得很多东西放在这个背景下可能会更清晰一些。所以，在内容上一直在选取可能会和算法竞赛更相关的部分，也希望通过更方便没有受到严格代数训练的选手阅读的方式来表达，哪怕牺牲一些数学上的深刻。这也是为什么没有引入商群的万有性质，也没有写 Galois 理论（尽管我都写完了可分正规扩张）。希望您能理解这种权衡。
这也是我为什么觉得直接讲对环做「扩张」会更好一些的原因，尽管它在数学上可能不是好的思路。本质上只是想说，这些域扩张的思路如果不需要做过多除法，也可以在很多环上成立。当然您指出，这个可能和取模视作函子的性质有关。但是我的原意是，你尽可以做这样环上的扩张，只要你写出一个不依赖于除法的表达式，再取模就可以了。这个想法尽管在数学的角度走了很多弯路，但是直接理解上没有难度？而且对于斐波那契数列、CF1103E，甚至更广泛的情景都适用？
谢谢！
我之前提到的问题还是存在的：是否可以不依赖于环的结构简单说明 π ′ ∘ i = 0 ？这个和后续的推演都没有关系，而且看起来十分显然。但是它在引入了环的结构之后看起来比单纯在群里做证明，要简单得多？
好吧，可能是認知習慣問題吧。我上過的唯一的代數課是從範疇開始講的，所以感覺「萬有性質」就是最自然而本質的東西：畢竟數學上名字裏帶個「商」字的總是會有類似的性質……
我觉得您的想法对于解决斐波那契数列的问题是很好的，但是有些过于深刻了。在原 issue 的讨论中，有 评论 提及到没有必要引入模论，这也是为什么在写的时候直接从环论跳到了域论。
確實有道理，模那裏挺難的，而且計算機的人應該多半都不會碰到。所以我也儘量不提模這個詞，只提交換群。
说起来写这个抽代的简介，内心一直就是十分矛盾的：既觉得算法竞赛中没有考这玩意的，根本就没有必要写，又觉得很多东西放在这个背景下可能会更清晰一些。所以，在内容上一直在选取可能会和算法竞赛更相关的部分，也希望通过更方便没有受到严格代数训练的选手阅读的方式来表达，哪怕牺牲一些数学上的深刻。这也是为什么没有引入商群的万有性质，也没有写 Galois 理论（尽管我都写完了可分正规扩张）。希望您能理解这种权衡。
这也是我为什么觉得直接讲对环做「扩张」会更好一些的原因，尽管它在数学上可能不是好的思路。本质上只是想说，这些域扩张的思路如果不需要做过多除法，也可以在很多环上成立。当然您指出，这个可能和取模视作函子的性质有关。但是我的原意是，你尽可以做这样环上的扩张，只要你写出一个不依赖于除法的表达式，再取模就可以了。这个想法尽管在数学的角度走了很多弯路，但是直接理解上没有难度？而且对于斐波那契数列、CF1103E，甚至更广泛的情景都适用？
可以是可以的，因為的確存在環擴張這個東西。相關定義是這樣的：
- 整擴張(integral extension)： 對交換幺環 $A\subset B$，如果 $b\in B$ 是 $A[x]$ 中某個首一多項式的根，則稱 $b$ 在 $A$ 上整。如果 $B$ 的所有元素在 $A$ 上都整，則稱 $A\subset B$ 為整擴張。（該概念對應域的代數擴張）
- 整閉包(integral closure)： 對交換幺環 $A\subset B$ ， $\overline{A}^B = \{ b\in B: b \text{ is integral over } A \}$ 稱為 $A$ 在 $B$ 中的整閉包。 $A$ 在它的分式域中的整閉包稱為 $A$ 的整閉包。
我覺得你的幾個例子可以直接用這個概念，這樣就不用發明新詞了。雖然整擴張的性質基本都超綱，不過只是介紹概念的話應該還可以。
@zjkmxy 谢谢您的回复！
我的第一点可能没有表述清楚。我的意思是检查 $\pi'\circ i=0$ 这个事实可能还是需要依赖于环的结构，我没有提及后面的万有性质的那部分。
不过确实您的代数课程的观点还是很高的。假想一下，如果我的第一本代数课本是范畴写起的，我可能就弃疗代数了。感觉对于我这种脑子没那么灵光的，范畴还是适合掌握一些基本的具体的结构之后再理解起来会更容易些。所以可能是在学习模和代数拓扑的时候，才遇到了比较多的范畴的概念。
至于环扩张的概念，我在 脚注 中其实给了个 维基页面 中的定义，这可能是域扩张的概念在环中最直接的推广。当然我承认，可能实际可以处理的情形，都是整扩张的类型，因为多项式不是首一的可能会引起很多麻烦。如果您觉得合适，我在同一个脚注里也提一下整扩张的概念？
我的第一点可能没有表述清楚。我的意思是检查 π ′ ∘ i = 0 这个事实可能还是需要依赖于环的结构，我没有提及后面的万有性质的那部分。
哦，抱歉會錯意。這個我看來是遞推數列本來的性質： $\pi'(x^{n+2}-x^{n+1}-x^n)= f(n+2)-f(n+1)-f(n) =0$ ，所以對任何 $(a_nx^n+\cdots+a_1x+a_0)(x^2-x-1)$ 直接用加法分配開，然後對每個項 $a_ix^{i+2}-a_ix^{i+1}-a_i$ 單獨處理就可以知道 $\pi'\circ i = 0$ 。這裏不用環上的定義的乘法也是很容易説明的。
至于环扩张的概念，我在 脚注 中其实给了个 维基页面 中的定义，这可能是域扩张的概念在环中最直接的推广。当然我承认，可能实际可以处理的情形，都是整扩张的类型，因为多项式不是首一的可能会引起很多麻烦。如果您觉得合适，我在同一个脚注里也提一下整扩张的概念？
我的認知是，整擴張是類比域的代數擴張的，所以它的對立面是超越擴張： $\mathbb{Z}\subset \mathbb{Z}[x]$ 的例子。
至於為甚麼要求首一，是因為如果不要求的話會出現 $2x-1=0$ 的「擴張」 $\mathbb{Z}[x]/(2x-1)\cong 2^{-1}\mathbb{Z}$ 。但是這個操作沒有帶來任何「新東西」，它就是個局部化（localization），擴張完的素理想也還是原來的那堆，環的結構也沒甚麼實質改變。為了把這種局部化的情況排掉，就多了個首一的要求。這樣認知上就可以説，局部化和商環的操作還是在「處理老東西」，而整擴張是「加入了新東西」（比如往整數裏面塞入了代數數）。