同余

Template:NoteTA 同余（Template:Langx，符号：≡）在数学中是指数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与“≡”符号者为德国数学家高斯。

定义

对某两个整数<math>a</math>，<math>b</math>，若它们除以正整数<math>m</math>所得的余数相等，则称<math>a</math>，<math>b</math>对于模<math>m</math>同余，也就是严格来说，存在整数<math>k</math>使得

<math> a-b = km </math>

则称<math>a,\,b</math>对于除数<math>m</math>是同余的。一般记做

<math>a \equiv b \pmod{m}</math>

比如

<math>26 - 14 = 12 = 1 \times 12</math>

故可以记为

<math>26 \equiv 14 \pmod{12}</math>

但另一方面，从<math> a-b = km </math>有<math> b-a = (-k)\times m </math>，故<math>a \equiv b \pmod{m}</math>等价于

<math>b \equiv a \pmod{m}</math>

同余符号“≡”其UTF-8码为U+2261。

同余类

可以证明所有对于模<math>m</math>同余的整数对构成一个（整数系<math>\Z</math>上的）等价关系，换句话说，对于任意两个整数<math>a</math>，<math>b</math>：

(1) <math>a \equiv a \pmod{m}</math>

(2) <math>[a \equiv b \pmod{m}] \Rightarrow [b \equiv a \pmod{m}]</math>

(3) <math>\big\{[a \equiv b \pmod{m}] \wedge [b \equiv c \pmod{m}]\big\}

\Rightarrow [a \equiv c \pmod{m}]</math>

故以下的集合

<math>{[a]}_m

=

\left\{z \in \Z \,\big|\, (\exists k \in \Z)(z = a + km)\right\}</math>

<math>\;\;\;\;\;\,=\left\{\ldots, a - 2m, a - m, a, a + m, a + 2m, \ldots \right\}</math>

可称为<math>a</math>对于模<math>m</math>的同余类（或），也可标记为<math>\overline{a}_m</math>；模<math>m</math>在上下文很清楚时，也可简记为<math>\displaystyle [a]</math>。<math>a</math>会被称为该同余类的代表数（）。

剩余系

剩余系（Template:Langx）亦即模<math>n</math>同余类的代表数的集合，通常使用的代表数是最小非负整数，因为它是除法中的应当余数。要注意的是，对于同一个模数<math>n</math>，不同的同余类不等价，亦即，属于不同同余类的整数不同余于模数<math>n</math>，或者说，模<math>n</math>剩余系中的任二元素不同余于模<math>n</math>；而且，整数域中的每个整数只属于模数<math>n</math>的一个同余类，因为模<math>n</math>将整数域划分为互斥区块，每个区块是一个同余类。

一个完全剩余系（Template:Langx）指的是模<math>n</math>的全部同余类的代表数的集合；因为剩余系中的任二元素不同余于模<math>n</math>，所以它也称为非同余余数的完整系统（Template:Langx）。例如，模<math>3</math>有三个同余类<math>[0], [1], [2]</math>，其完全剩余系可以是<math>\{9, 12+1, 15+2\}</math>。如果该集合是由每个同余类的最小非负整数所组成，亦即<math>\{ 0, 1, 2, ..., n-1\}</math>，则称该集合为模<math>n</math>的最小剩余系（Template:Langx）。

模<math>n</math>完全剩余系中，与模<math>n</math>互质的代表数所构成的集合，称为模<math>n</math>的简约剩余系（Template:Langx），其元素个数记为<math>\phi(n)</math>，亦即欧拉函数。例如，模<math>6</math>的简约剩余系为<math>\{1, 5\}</math>或<math>\{7, 11\}</math>。如果模<math>n</math>是质数，那么它的最小简约剩余系是<math>\{1, 2, ..., n-1\}</math>，只比最小剩余系少一个<math>0</math>。

性质

整除性

<math style="vertical-align: top;">a \equiv b \pmod{m} \Rightarrow c\cdot m=a-b, c \in \mathbb{Z}</math> （即是说 a 和 b 之差是 m 的倍数）
换句话说，<math>a \equiv b \pmod{m} \Rightarrow m \mid(a-b)</math>

同余可以用来检验一个数是否可以整除另外一个数，见整除规则。

传递性

<math style="vertical-align:top;">\left. \begin{matrix} a \equiv b \pmod{m} \\ b \equiv c \pmod{m} \end{matrix} \right\} \Rightarrow a \equiv c \pmod{m}</math>

保持基本运算

<math style="vertical-align:top;">\left. \begin{matrix} a \equiv b \pmod{m} \\ c \equiv d\pmod{m} \end{matrix} \right\} \Rightarrow \left\{ \begin{matrix} a \pm c \equiv b \pm d \pmod{m} \\ ac \equiv bd \pmod{m} \end{matrix} \right.</math>
当<math>c=d</math>时，则为等量加法、减法：<math>a \pm c \equiv b \pm c \pmod{m} </math>
这性质更可进一步引申成为这样：
<math>a \equiv b \pmod{m} \Rightarrow \begin{cases}

an \equiv bn \pmod{m}, \forall n \in \mathbb{Z} \\
a^n \equiv b^n \pmod{m}, \forall n \in \mathbb{N}^* \\
P(a)\equiv P(b) \pmod{m}

\end{cases}</math>
其中<math>P(x)</math>为任意整系数多项式函数。

放大缩小底数

k为整数，n为正整数，<math>(km \pm a)^n \equiv (\pm a)^n \pmod{m}</math>

放大缩小模数

<math>k</math>为正整数，<math>a \equiv b \pmod{m}</math>，当且仅当<math>ka \equiv kb \pmod{km}</math>

除法原理一

若<math>ka \equiv kb \pmod{m}</math>且<math>k,m</math>互质，则<math>a \equiv b \pmod{m}</math>

除法原理二

每个正整数都可以分解为数个因数的乘积，称为整数分解。例如 <math>15 = 3 \times 5</math>，因数 <math>3</math> 与 <math>5</math> 都可以整除 <math>15</math>，记为 <math>3|15</math> 与 <math>5|15</math>。如果 <math>15</math> 可以整除某正整数 <math>a</math>，亦即 <math>15|a</math>，那么 <math>15</math> 就是 <math>a</math> 的因数：<math>a = 15 \times b</math>，其中 <math>b</math> 为另一因数。<math>a = 15 \times b = (3 \times 5) \times b</math>，因此，<math>15</math> 的因数也可以整除 <math>a</math>：<math>(3|15) \wedge (15|a) \Rightarrow 3|a</math>。

<math>a \equiv b \pmod{m}</math> 等价于 <math>(a-b) \equiv 0 \pmod{m}</math>，也就是 <math>m | (a-b)</math>。亦即，如果 <math>m | (a-b)</math>，那么它可以写成 <math>a \equiv b \pmod{m}</math>，因此有以下除法原理：

<math>m</math> 的因数也可以整除 <math>(a-b)</math>。亦即，<math>m</math> 是 <math>n</math> 的倍数：<math>m = c \times n</math>，<math>n|m</math>。因为 <math>m | (a-b)</math>，所以 <math>n | (a-b) \Rightarrow a \equiv b \pmod{n}</math>。

<math style="vertical-align: top;">

a \equiv b \pmod{cn} \Rightarrow a \equiv b \pmod n</math>

<math>\left. \begin{matrix} a \equiv b \pmod{m} \\ n|m \end{matrix} \right\} \Rightarrow a \equiv b \pmod n</math>

现假设 <math>m</math> 可以整除 <math>(a-b)</math> 的倍数 <math>c(a-b)</math>。如果 <math>m</math> 和 <math>c</math> 互质（记为 <math>(m, c) = 1</math>），那么 <math>m</math> 必定可以整除 <math>(a-b)</math>：<math>m|(a-b) \Rightarrow a \equiv b \pmod{m}</math>。

<math>\left. \begin{matrix} ac \equiv bc \pmod{m} \\ (c, m) = 1 \end{matrix} \right\} \Rightarrow a \equiv b \pmod m</math>

如果 <math>m_1|(a-b)</math> 而且 <math>m_2|(a-b)</math>，那么 <math>m_1</math> 与 <math>m_2</math> 的最小公倍数必定可以整除 <math>(a-b)</math>，记为 <math>a \equiv b \pmod{[m_1, m_2]}</math>。这可以推广成以下性质：

<math style="vertical-align: top;">\left. \begin{matrix} a \equiv b \pmod{m_1} \\ a \equiv b \pmod{m_2} \\ \vdots \\ a \equiv b \pmod{m_n} \\ (n \ge 2) \end{matrix} \right\} \Rightarrow a \equiv b \pmod{[m_1,m_2,\cdots,m_n]}</math>

上面的最后一个性质可以使用算术基本定理与集合来解释。一个大于1的正整数 <math>q</math> 可以分解为一串质数幂的乘积：<math>q = p_1^{c_1} \times p_2^{c_2} \times ... \times p_n^{c_n}</math>（<math>p_i</math> 两两相异，且<math>c_i>0</math>），令 <math>S_q</math> 为所有能整除 <math>q</math> 的质数幂的集合，即 <math>S_q = \{p_1, p_1^2,\cdots,p_1^{c_1}, p_2,p_2^2,\cdots,p_2^{c_2},\cdots, p_n, p_n^2,\cdots,p_n^{c_n}\}</math>。设 <math>r</math> 为正整数，则 <math>r</math> 整除 <math>q</math>，当且仅当 <math>S_r</math> 是 <math>S_q</math> 的子集。令 <math>m_1 | q</math> 且 <math>m_2 | q</math>，则<math>S_{m_1}</math> 与 <math>S_{m_2}</math> 的联集必定也是 <math>S_q</math> 的子集。取这个联集中幂次最高的各个元素，它们的乘积就是 <math>m_1</math> 与 <math>m_2</math> 的最小公倍数<math>[m_1,m_2]</math>。事实上，有 <math>S_{[m_1,m_2]}=S_{m_1}\cup S_{m_2}</math>，所以 <math>[m_1,m_2]</math> 也能够整除 <math>q</math> 。

同余关系式

威尔逊定理

<math>(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)</math>

费马小定理

<math>a^{p-1} \equiv 1 \pmod p</math>

欧拉定理

<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>

卡迈克尔函数

<math>a^{\lambda (n)} \equiv 1 \pmod{n}</math>

阶乘幂

<math>(x)_k \equiv x(x-1)(x-2)\cdots(x-k+1) \equiv 0 \pmod{k!}</math>

卢卡斯定理

<math>\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,</math>

组合数最小周期

<math>\binom{m+p^{k+[log_p n]}}{n}\equiv \binom{m}{n}\pmod{p^k}</math>

设<math>N=\prod_i p_i^{k_i}</math>，则<math>\binom{m+L(n,N)}{n}\equiv \binom{m}{n}\pmod{N}</math>，其中<math>L(n,N)=\prod_i p_i^{k_i+[log_p n]}=N\prod_i p_i^{[log_p n]}</math>

相关概念

模反元素

<math>a^{-1}\dot a\equiv 1\pmod{n}</math>

可用辗转相除法、欧拉定理、卡迈克尔函数求解。

原根

存在最小的正整数d使得<math>a^d\equiv 1\pmod{n}</math>成立，且<math>d=\varphi(n)</math>。

同余方程

线性同余方程

<math>ax\equiv b\pmod{n}</math>

考虑最大公约数，有解时用辗转相除法等方法求解。

线性同余方程组

<math>\begin{cases} a_1 x \equiv b_1 \pmod{m_1} \\ a_2 x \equiv b_2 \pmod{m_2} \\ \qquad\qquad\vdots \\ a_n x \equiv b_n \pmod{m_n} \\ \end{cases}</math>

先求解每一个线性同余方程，再用中国剩余定理解方程组。

二次剩余

<math>x^2\equiv d\pmod{p}</math>

勒让德符号、雅可比符号、克罗内克符号、二次互反律用于判别d是否为模n的二次剩余。

高次剩余

<math>x^n\equiv d\pmod{p}</math>

例子

• 求自然数a的个位数字，就是求a与哪一个数对于模10同余。
• <math>10\equiv 1 (\textrm{mod }\ 3), 10^{n}\equiv 1 (\textrm{mod }\ 3), 10001\equiv 10^{4}+1\equiv 1+1 (\textrm{mod }\ 3)</math>。

应用

模数算术在数论、群论、环论、纽结理论、抽象代数、计算机代数、密码学、计算机科学、化学、视觉和音乐等学科中皆有应用。

它是数论的立基点之一，与其各个面向都相关。

模数算术经常被用于计算标识符中所使用的校验和，比如国际银行账户号码（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 < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d > m) d -= m;
       a <<= 1;
   }
   return d%m;
}

参见

• 合同 (数学)
• 等价关系
• 模除
• 不定方程