同余 同余（，符号：≡）在数学中是指数论中的一种等价关系。当两个整数除以同一个正整数，若得相同-{zh-hans:余数; zh-hant:余数;}-，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与「≡」符号者为德国数学家高斯。 同余符号. 两个整数formula_1，formula_2，若它们除以正整数formula_3所得的余数相等，则称formula_1，formula_2对于模formula_3同余 记作formula_7 读作formula_1同余于formula_2模formula_3，或读作formula_1与formula_2关于模formula_3同余。 比如formula_14。 同余于的符号是同余相等符号≡。统一码值为codice_1。 同余类. 如同任何同余关系，对于模formula_15同余是一种等价关系，整数formula_1的等价类是一个集合formula_17，标记为formula_18。由对于模formula_15同余的所有整数组成的这个集合称为同余类（-- 或-- ）；假若从上下文知道模formula_15，则也可标记为formula_21。 同余类中的每个元素都可以拿来代表该同余类，称为该同余类的代表数（）。 剩余系. 剩余系（）亦即模formula_15同余类的代表数的集合，通常使用的代表数是最小非负整数，因为它是除法中的应当余数。要注意的是，对于同一个模数formula_15，不同的同余类不等价，亦即，属于不同同余类的整数不同余于模数formula_15，或者说，模formula_15剩余系中的任二元素不同余于模formula_15；而且，整数域中的每个整数只属于模数formula_15的一个同余类，因为模formula_15将整数域划分为互斥区块，每个区块是一个同余类。 一个完全剩余系（）指的是模formula_15的全部同余类的代表数的集合；因为剩余系中的任二元素不同余于模formula_15，所以它也称为非同余余数的完整系统（）。例如，模formula_31有三个同余类formula_32，其完全剩余系可以是formula_33。如果该集合是由每个同余类的最小非负整数所组成，亦即formula_34，则称该集合为模formula_15的最小剩余系（）。 模formula_15完全剩余系中，与模formula_15互质的代表数所构成的集合，称为模formula_15的简约剩余系（），其元素个数记为formula_39，亦即欧拉函数。例如，模formula_40的简约剩余系为formula_41或formula_42。如果模formula_15是质数，那么它的最小简约剩余系是formula_44，只比最小剩余系少一个formula_45。 性质. 整除性. formula_46 （即是说 a 和 b 之差是 m 的倍数）换句话说，formula_47 同余可以用来检验一个数是否可以整除另外一个数，见整除规则。 传递性. formula_48 保持基本运算. formula_49 当formula_50时，则为等量加法、减法：formula_51 这性质更可进一步引申成为这样：formula_52 其中formula_53为任意整系数多项式函数。 放大缩小底数. k为整数，n为正整数，formula_54 放大缩小模数. formula_55为正整数，formula_7，若且唯若formula_57 除法原理一. 若formula_58且formula_59互质，则formula_7 除法原理二. 每个正整数都可以分解为数个因数的乘积，称为整数分解。例如 formula_61，因数 formula_31 与 formula_63 都可以整除 formula_64，记为 formula_65 与 formula_66。如果 formula_64 可以整除某正整数 formula_1，亦即 formula_69，那么 formula_64 就是 formula_1 的因数：formula_72，其中 formula_2 为另一因数。formula_74，因此，formula_64 的因数也可以整除 formula_1：formula_77。 formula_7 等价于 formula_79，也就是 formula_80。亦即，如果 formula_80，那么它可以写成 formula_7，因此有以下除法原理： formula_3 的因数也可以整除 formula_84。亦即，formula_3 是 formula_15 的倍数：formula_87，formula_88。因为 formula_80，所以 formula_90。 formula_91 formula_92 现假设 formula_3 可以整除 formula_84 的倍数 formula_95。如果 formula_3 和 formula_97 互质（记为 formula_98），那么 formula_3 必定可以整除 formula_84：formula_101。 formula_102 如果 formula_103 而且 formula_104，那么 formula_105 与 formula_106 的最小公倍数必定可以整除 formula_84，记为 formula_108。这可以推广成以下性质： formula_109 上面的最后一个性质可以使用算术基本定理与集合来解释。一个大于1的正整数 formula_110 可以分解为一串质数幂的乘积：formula_111（formula_112 两两相异，且formula_113），令 formula_114 为所有能整除 formula_110 的质数幂的集合，即 formula_116。设 formula_117 为正整数，则 formula_117 整除 formula_110，当且仅当 formula_120 是 formula_114 的子集。令 formula_122 且 formula_123，则formula_124 与 formula_125 的联集必定也是 formula_114 的子集。取这个联集中幂次最高的各个元素，它们的乘积就是 formula_105 与 formula_106 的最小公倍数formula_129。事实上，有 formula_130，所以 formula_129 也能够整除 formula_110 。 同余关系式. 威尔逊定理. formula_133 费马小定理. formula_134 欧拉定理. formula_135 卡迈克尔函数. formula_136 阶乘幂. formula_137 卢卡斯定理. formula_138 组合数最小周期. formula_139 设formula_140，则formula_141，其中formula_142 相关概念. 模反元素. formula_143 可用辗转相除法、欧拉定理、卡迈克尔函数求解。 原根. 存在最小的正整数d使得formula_144成立，且formula_145。 同余方程. 线性同余方程. formula_146 考虑最大公约数，有解时用辗转相除法等方法求解。 线性同余方程组. formula_147 先求解每一个线性同余方程，再用中国剩余定理解方程组。 二次剩余. formula_148 勒让德符号、雅可比符号、克罗内克符号、二次互反律用于判别d是否为模n的二次剩余。 高次剩余. formula_149 应用. 模数算术在数论、群论、环论、纽结理论、抽象代数、计算机代数、密码学、计算机科学、化学、视觉和音乐等学科中皆有应用。 它是数论的立基点之一，与其各个面向都相关。 模数算术经常被用于计算标识符中所使用的校验和，比如国际银行账户号码（IBANs）就用到了模97的算术，来捕获用户在输入银行帐户号码时的错误。 于密码学中，模数算术是RSA与迪菲－赫尔曼密钥交换等公钥系统的基础，它同时也提供有限域，应用于 椭圆加密，且用于许多对称密钥加密中，包括高级加密标准、国际资料加密演算法等。 于计算机科学, 同余被应用于位元运算或其他与固定宽度之循环资料结构相关的操作。 于化学中, CAS号（一个对各种化合物皆异之的识别码）的最后一码为校验码，将CAS号首二部分最后的数字乘上一，下一码乘上二，下一码乘上三以此类推，将所有积加起来再取模10。 在音乐领域，模12用于十二平均律系统。 星期的计算中取模7算术极重要。 更广泛而言，同余在法律、经济（见赛局理论）或其他社会科学领域中也有应用。 范例. 以下为快速展示小于63位元无号整数之模数乘法的C程式，且转换过程中不发生溢位。计算 a * b (mod m)之演算法: uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) uint64_t d = 0, mp2 = m » 1; int i; if (a >= m) a %= m; if (b >= m) b %= m; for (i = 0; i mp2) ? (d « 1) - m : d « 1; if (a & 0x8000000000000000ULL) d += b; if (d > m) d -= m; a «= 1; return d%m;