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

同餘

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

\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質數,那麼它的簡約餘數系統等於完整餘數系統。

性质[编辑]

整除性[编辑]

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}

除法原理[编辑]

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]
\left. \begin{matrix} ac \equiv bc \pmod{m} \\ (c, m) = 1 \end{matrix} \right\} \Rightarrow a \equiv b \pmod 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]

威尔逊定理[编辑]

(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)

注释[编辑]

  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最小公倍数

參考來源[编辑]

外部链接[编辑]

参见[编辑]