本页使用了标题或全文手工转换

同餘

维基百科,自由的百科全书
跳转至: 导航搜索
各种各样的
基本

\mathbb{N}\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}\subseteq\mathbb{C}

正數 \begin{smallmatrix} \mathbb{R}^+ \end{smallmatrix}
自然数 \begin{smallmatrix} \mathbb{N} \end{smallmatrix}
正整數 \begin{smallmatrix} \mathbb{Z}^+ \end{smallmatrix}
小数
有限小数
无限小数
循环小数
有理数 \begin{smallmatrix} \mathbb{Q} \end{smallmatrix}
代數數 \begin{smallmatrix} \mathbb{A} \end{smallmatrix}
实数 \begin{smallmatrix} \mathbb{R} \end{smallmatrix}
複數 \begin{smallmatrix} \mathbb{C} \end{smallmatrix}
高斯整數 \begin{smallmatrix} \mathbb{Z}[i] \end{smallmatrix}

负数 \begin{smallmatrix} \mathbb{R}^- \end{smallmatrix}
整数 \begin{smallmatrix} \mathbb{Z} \end{smallmatrix}
负整數 \begin{smallmatrix} \mathbb{Z}^- \end{smallmatrix}
分數
單位分數
二进分数
規矩數
無理數
超越數
虚数
二次无理数
艾森斯坦整数 \begin{smallmatrix} \mathbb{Z}[\omega] \end{smallmatrix}

延伸

雙複數
四元數 \begin{smallmatrix} \mathbb{H} \end{smallmatrix}
共四元數
八元數 \begin{smallmatrix} \mathbb{O} \end{smallmatrix}
超數
上超實數

超复数
十六元數 \begin{smallmatrix} \mathbb{S} \end{smallmatrix}
複四元數
大實數
超實數 \begin{smallmatrix} {}^\star\mathbb{R} \end{smallmatrix}
超現實數

其他

对偶数
雙曲複數
序数
質數
同餘
可計算數
阿列夫数

公稱值
超限数
基數
P進數
規矩數
整數數列
數學常數

圓周率 \begin{smallmatrix} \pi \end{smallmatrix}
 = 3.141592653…
自然對數的底 \begin{smallmatrix} e \end{smallmatrix}
 = 2.718281828…
虛數單位 \begin{smallmatrix} i \end{smallmatrix}
 = \begin{smallmatrix} +\sqrt{-1} \end{smallmatrix}
無窮大 \begin{smallmatrix} \infty \end{smallmatrix}

数学上,同余英语congruence modulo[1]符號:≡)是數論中的一種等價關係[2]。當两个整数以同一个整数,若得相同余数,则二整数同余。同餘是抽象代數中的同餘關係的原型[3]。最先引用同余的概念与「≡」符号者为德國数学家高斯

同余符号[编辑]

两个整数ab,若它们除以正整数m所得的余数相等,则称ab对于模m同余

记作a \equiv b \pmod{m}

读作a同余于bm,或读作ab关于模m同余。

比如26 \equiv 14 \pmod{12}

同餘於的符號是同餘相等符號 。統一碼值為 U+2261。但因為方便理由,人們有時會把它(誤)寫為普通等號 (=)。

同餘類[编辑]

如同任何同餘關係,對於模n同餘是一種等價關係,整數a等價類是一個集合\left\{\ldots, a - 2n, a - n, a, a + n, a + 2n, \ldots \right\},標記為\overline{a}_n。由對於模n同餘的所有整數組成的這個集合稱為同餘類congruence classresidue class);假若從上下文知道模n,則也可標記為\displaystyle [a]

同餘類中的每個元素都可以拿來代表該同餘類,稱為該同餘類的代表數英语representative[4]

餘數系統[编辑]

餘數系統英语residue system)亦即模n同餘類的代表數的集合,通常使用的代表數是最小非負整數,因為它是除法中的應當餘數。要注意的是,對於同一個模數n,不同的同餘類不等價,亦即,屬於不同同餘類的整數不同餘於模數n,或者說,模n餘數系統中的任二元素不同餘於模n;而且,整數域中的每個整數只屬於模數n的一個同餘類,因為模n將整數域划分為互斥區塊,每個區塊是一個同餘類。

一個完整餘數系統英语complete residue system)指的是模n的全部同餘類的代表數的集合;因為餘數系統中的任二元素不同餘於模n,所以它也稱為非同餘餘數的完整系統英语complete system of incongruent residues)。例如,模3有三個同餘類[0], [1], [2],其完整餘數系統可以是\{9, 12+1, 15+2\}。如果該集合是由每個同餘類的最小非負整數所組成,亦即\{ 0, 1, 2, ..., n-1\},則稱該集合為模n最小餘數系統英语least residue system)。

n完整餘數系統中,與模n互質的代表數所構成的集合,稱為模n簡約餘數系統英语reduced residue system),其元素個數記為\phi(n),亦即欧拉函数。例如,模6的簡約餘數系統為\{1, 5\}\{7, 11\}。如果模n質數,那麼它的最小簡約餘數系統是\{1, 2, ..., n-1\},只比最小餘數系統少一個0

性质[编辑]

整除性[编辑]

a \equiv b \pmod{m} \Rightarrow c\cdot m=a-b, c \in \mathbb{Z} (即是說 a 和 b 之差是 m 的倍數)
換句話說,a \equiv b \pmod{m} \Rightarrow m \mid(a-b)[註 1]

传递性[编辑]

\left. \begin{matrix}
a \equiv b \pmod{m} \\
b \equiv c \pmod{m}
\end{matrix} \right\} \Rightarrow a \equiv c \pmod{m}

保持基本运算[编辑]

\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.
這性質更可進一步引申成為這樣:
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}^0
\end{cases}

除法原理[编辑]

每個正整數都可以分解為數個因數的乘積,稱為整数分解。例如 15 = 3 \times 5,因數 35 都可以整除 15,記為 3|155|15。如果 15 可以整除某正整數 a,亦即 15|a,那麼 15 就是 a 的因數:a = 15 \times b,其中 b 為另一因數。a = 15 \times b = (3 \times 5) \times b,因此,15 的因數也可以整除 a(3|15) \wedge (15|a) \Rightarrow 3|a

a \equiv b \pmod{m} 等價於 (a-b) \equiv 0 \pmod{m},也就是 m | (a-b)。亦即,如果 m | (a-b),那麼它可以寫成 a \equiv b \pmod{m},因此有以下除法原理:

m 的因數也可以整除 (a-b)。亦即,mn倍數m = c \times nn|m。因為 m | (a-b),所以 n | (a-b) \Rightarrow a \equiv b \pmod{n}

a \equiv b \pmod{cn} \Rightarrow a \equiv b \pmod n
\left. \begin{matrix} a \equiv b \pmod{m} \\ n|m \end{matrix} \right\} \Rightarrow a \equiv b \pmod n[註 1]
現假設 m 可以整除 (a-b) 的倍數 c(a-b)。如果 mc 互質(記為 (m, c) = 1),那麼 m 必定可以整除 (a-b)m|(a-b) \Rightarrow a \equiv b \pmod{m}
\left. \begin{matrix} ac \equiv bc \pmod{m} \\ (c, m) = 1 \end{matrix} \right\} \Rightarrow a \equiv b \pmod m[註 2]
如果 m_1|(a-b) 而且 m_2|(a-b),那麼 m_1m_2最小公倍数必定可以整除 (a-b),記為 a \equiv b \pmod{[m_1, m_2]}。這可以推廣成以下性質:
\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]}[註 3]
上面的最後一個性質可以使用算术基本定理集合來解釋。一個大於1的正整數 q 可以分解為一串質數冪的乘積:q = p_1^{c_1} \times p_2^{c_2} \times ... \times p_n^{c_n}p_i 兩兩相異,且c_i>0),令 S_q 為所有能整除 q 的質數冪的集合,即 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}\}。設 r 為正整數,則 r 整除 q,當且僅當 S_rS_q子集。令 m_1 | qm_2 | q,則S_{m_1}S_{m_2}聯集必定也是 S_q 的子集。取這個聯集中冪次最高的各個元素,它們的乘積就是 m_1m_2最小公倍数[m_1,m_2]。事實上,有 S_{[m_1,m_2]}=S_{m_1}\cup S_{m_2},所以 [m_1,m_2] 也能夠整除 q

威尔逊定理[编辑]

(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)

费马小定理[编辑]

(x^p-x)^k \equiv 0 \pmod {p^k}

阶乘幂[编辑]

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

欧拉定理[编辑]

a^{\varphi (n)} \equiv 1 \pmod{n}

例子[编辑]

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

應用[编辑]

模數算術在數論群論環論紐結理論抽象代數計算機代數密碼學計算機科學化學視覺音樂等學科中皆有應用。

它是數論的立基點之一,與其各個面向都相關。

模數算術經常被用於計算標識符中所使用的校验和,比如国际银行账户号码(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;
}


注释[编辑]

  1. ^ 1.0 1.1 m \mid x 表示 m 能整除 x,或者说 x 能被 m 整除。
  2. ^ (m_1,m_2,\cdots,m_n)表示m_1,m_2,\cdots,m_n最大公约数
  3. ^ [m_1,m_2,\cdots,m_n]表示m_1,m_2,\cdots,m_n最小公倍数

參考來源[编辑]

参见[编辑]