同余与模算术

模算术研究整数在固定模数下的可除性，将整数转化为有限环 Z/nZ，并为数论提供了最灵活的计算工具。

Definition

如果两个整数的差可以被 n 整除，则称它们模 n 同余。模算术是所得剩余类的算术，这些剩余类构成了交换环 Z/nZ。

Scope

本主题涵盖同余关系和剩余类、Z/nZ 中的算术、线性和多项式同余、中国剩余定理、费马小定理和欧拉定理、单位群的结构、原根以及元素的阶。它是表达大多数初等数论和计算数论的语言。

Core questions

• 线性同余 ax ≡ b (mod n) 何时有解，有多少解？
• 中国剩余定理如何将 Z/nZ 分解为素数幂模的乘积？
• 费马小定理和欧拉定理为何成立，它们对单位的阶有何说明？
• 对于哪些模数存在原根，使得单位群是循环群？

Key theories

中国剩余定理

如果模数两两互质，则同余方程组在模乘积的意义下有唯一解；等价地，Z/nZ 同构于其素数幂因子的 Z 乘积。

费马小定理和欧拉定理

对于与 n 互质的 a，a 的 n 的欧拉函数次幂模 n 同余于一；素数情况（费马小定理）是素性检验的基础，一般情况（欧拉定理）是 RSA 的基础。

原根和群结构

模 n 的乘法单位群是循环群当且仅当 n 是一、二、四、奇素数的幂或奇素数幂的两倍；生成元是原根，它提供了离散对数。

Clinical relevance

模算术是密码学（RSA、Diffie-Hellman、椭圆曲线方案）、校验和与错误检测（ISBN、哈希函数）以及伪随机数生成的计算引擎，使其成为数论中应用最广泛的部分。

History

尽管特殊情况出现在古代中国和印度的数学中（以中国命名的剩余问题），但同余的系统理论是由高斯在《算术研究》（Disquisitiones Arithmeticae, 1801）中引入的，他在其中建立了符号并证明了核心结构结果。

Key figures

• Carl Friedrich Gauss
• Pierre de Fermat
• Leonhard Euler

Seminal works

• irelandRosen1990

Frequently asked questions

符号 a ≡ b (mod n) 是什么意思？

它表示 n 整除 a 减 b 的差，等价地，a 和 b 除以 n 留下相同的余数。

为什么 RSA 依赖于欧拉定理？

RSA 加密和解密是模幂运算，它们的组合返回原始消息，正是因为欧拉定理保证了相关的指数在模密钥的意义下起到恒等作用。