查看“︁同餘”︁的源代码

{{NoteTA
|G1 = Math
|1 = zh-hans:余; zh-hant:餘;
}}
'''同余'''（{{lang-en|Congruence modulo}}<ref>{{Cite web |url=https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/congruence-modulo |title=Khan Academy > Congruence Modulo |access-date=2014-10-21 |archive-date=2020-11-04 |archive-url=https://web.archive.org/web/20201104042516/https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/congruence-modulo |dead-url=no }}</ref>，[[符號]]：≡）在[[数学]]中是指[[數論]]中的一種[[等價關係]]<ref>{{Cite web |url=http://books.google.com.tw/books?id=61dOjKZdJM4C&pg=PA57&lpg=PA57&dq=%22congruence+modulo%22#v=onepage&q=%22congruence%20modulo%22&f=false |title=''Abstract algebra'', I. H. Sheth, p.57 |access-date=2014-10-21 |archive-date=2014-10-21 |archive-url=https://web.archive.org/web/20141021143741/http://books.google.com.tw/books?id=61dOjKZdJM4C&pg=PA57&lpg=PA57&dq=%22congruence+modulo%22#v=onepage&q=%22congruence%20modulo%22&f=false |dead-url=no }}</ref>。當两个[[整数]][[带余除法|除]]以同一个[[正整数]]，若得相同[[余数|-{zh-hans:余数; zh-hant:餘數;}-]]，则二整数'''同余'''。同餘是[[抽象代數]]中的[[同餘關係]]的原型<ref>{{Cite web |url=http://books.google.com.tw/books?id=bdNcAGctmaoC&pg=PT174&lpg=PT174&dq=%22congruence+relation%22#v=onepage&q=%22congruence%20relation%22&f=false |title=e-Study Guide for: Handbook of Mathematics: Mathematics, Mathematics, p.174 |accessdate=2014-10-21 |archive-date=2014-10-21 |archive-url=https://web.archive.org/web/20141021154507/http://books.google.com.tw/books?id=bdNcAGctmaoC&pg=PT174&lpg=PT174&dq=%22congruence+relation%22#v=onepage&q=%22congruence%20relation%22&f=false |dead-url=no }}</ref>。最先引用同余的[[概念]]与「≡」[[符号]]者为[[德國]][[数学家]][[高斯]]。
{{Numbers}}

== 定義 ==
對某兩個整数<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]]碼為<code>U+2261</code>。

== 同餘類 ==
可以證明所有对于模<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>的'''同余類'''（{{lang|en|congruence class}}或{{lang|en|residue class}}），也可標記為<math>\overline{a}_m</math>；模'''<math>m</math>'''在上下文很清楚時，也可簡記為<math>\displaystyle [a]</math>。'''<math>a</math>'''會被稱為該同余類的'''代表數'''（{{lang|en|representative}}）<ref>{{Cite web|title=''A Computational Introduction to Number Theory and Algebra'', Victor Shoup, p.25|url=http://books.google.com.tw/books?id=pWFdMf5hb5oC&pg=PA25&lpg=PA25&dq=representative#v=onepage&q=representative&f=false|archive-url=https://web.archive.org/web/20141105101249/http://books.google.com.tw/books?id=pWFdMf5hb5oC&pg=PA25&lpg=PA25&dq=representative#v=onepage&q=representative&f=false|archive-date=2014-11-05|access-date=2014-11-05|dead-url=no}}</ref>。

== 剩餘系 ==
'''剩餘系'''<ref>{{cite web|author = 國家教育研究院|url = https://terms.naer.edu.tw/detail/3186504/|title = 完全剩餘系 complete system of residues|website = 雙語詞彙、學術名詞暨辭書資訊網|access-date = 2022-05-21|archive-date = 2022-05-21|archive-url = https://web.archive.org/web/20220521112535/https://terms.naer.edu.tw/detail/3186504/}}</ref><ref>{{cite book|url = https://www.google.co.uk/books/edition/%E8%8B%B1%E6%B1%89%E6%95%B0%E5%AD%A6%E8%AF%8D%E6%B1%87/nduYtmyywcUC?hl=en&gbpv=1&printsec=frontcover&bsq=residue%20system|editor1= 张鸿林|editor2 = 葛显良|publisher = 清华大学出版社|year = 2005|title = 英汉数学词汇
|page = 119, 617}}</ref>（{{lang-en|residue system}}）亦即模<math>n</math>同餘類的代表數的集合，通常使用的代表數是最小非負整數，因為它是除法中的應當餘數。要注意的是，對於同一個模數<math>n</math>，不同的同餘類不等價，亦即，屬於不同同餘類的整數不同餘於模數<math>n</math>，或者說，模<math>n</math>剩餘系中的任二元素不同餘於模<math>n</math>；而且，整數域中的每個整數只屬於模數<math>n</math>的一個同餘類，因為模<math>n</math>將整數域[[集合划分|划分]]為互斥區塊，每個區塊是一個同餘類。

一個'''完全剩餘系'''（{{lang-en|complete residue system}}）指的是模<math>n</math>的全部同餘類的代表數的集合；因為剩餘系中的任二元素不同餘於模<math>n</math>，所以它也稱為'''非同餘餘數的完整系統'''（{{lang-en|complete system of incongruent residues}}）。例如，模<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>的'''最小剩餘系'''（{{lang-en|least residue system}}）。

模<math>n</math>完全剩餘系中，與模<math>n</math>互質的代表數所構成的集合，稱為模<math>n</math>的'''簡約剩餘系'''（{{lang-en|reduced residue system}}），其元素個數記為<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 的倍數）<br />換句話說，<math>a \equiv b \pmod{m} \Rightarrow m \mid(a-b)</math>{{NoteTag|<math>m \mid x</math> 表示 m 能[[整除]] x，或者说 x 能被 m 整除。|name="div"}}

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

===传递性===
<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><br />
當<math>c=d</math>時，則為等量加法、減法：<math>a \pm c \equiv b \pm c \pmod{m} </math><br>
這性質更可進一步引申成為這樣：<br /><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>{{NoteTag|但是，<math>a^n \equiv b^n \pmod{m}</math>不能推論<math>a \equiv b \pmod{m}</math>.}}
<br>其中<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><br />

:: <math>\left. \begin{matrix} a \equiv b \pmod{m} \\ n|m \end{matrix} \right\} \Rightarrow a \equiv b \pmod n</math>{{NoteTag|name="div"}}<br />

: 現假設 <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>{{NoteTag|<math>(m_1,m_2,\cdots,m_n)</math>表示<math>m_1,m_2,\cdots,m_n</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>{{NoteTag|<math>[m_1,m_2,\cdots,m_n]</math>表示<math>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> 。

==同余关系式==
===威尔逊定理===
{{main|威爾遜定理}}
<math>(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)</math>

===费马小定理===
{{main|费马小定理}}
<math>a^{p-1} \equiv 1 \pmod p</math>

===欧拉定理===
{{main|歐拉定理 (數論)}}
<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>

===卡邁克爾函數===
{{main|卡邁克爾函數}}
<math>a^{\lambda (n)} \equiv 1 \pmod{n}</math>

===阶乘幂===
{{main|阶乘幂}}
<math>(x)_k \equiv x(x-1)(x-2)\cdots(x-k+1) \equiv 0 \pmod{k!}</math>

===卢卡斯定理===
{{main|卢卡斯定理}}
<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><ref>{{Cite journal|author=Chi-Jen Lu|author2=Shi-Chun Tsaiy|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.7833&rep=rep1&type=pdf|title=The Periodic Property of Binomial Coefficients Modulo m and Its Applications|journal=10th SIAM Conference on Discrete Mathematics|year=2000|access-date=2018-09-13|archive-date=2018-09-14|archive-url=https://web.archive.org/web/20180914022313/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.7833&rep=rep1&type=pdf|dead-url=no}}</ref>

==相关概念==
===模反元素===
{{main|模反元素}}
<math>a^{-1}\dot a\equiv 1\pmod{n}</math>

可用[[輾轉相除法]]、[[歐拉定理]]、[[卡邁克爾函數]]求解。

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

==同余方程==
===线性同余方程===
{{main|线性同余方程}}
<math>ax\equiv b\pmod{n}</math>

考虑[[最大公约数]]，有解时用[[輾轉相除法]]等方法求解。

===线性同余方程组===
{{main|中国剩余定理}}
<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>

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

===二次剩余===
{{main|二次剩余}}
<math>x^2\equiv d\pmod{p}</math>

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

===高次剩餘===
{{main|高次剩餘}}
<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加密演算法|RSA]]與[[迪菲－赫尔曼密钥交换]]等[[公鑰加密|公鑰]]系統的基礎，它同時也提供[[有限域]]，應用於 [[橢圓曲線密碼學|橢圓加密]]，且用於許多[[對稱密鑰加密]]中，包括[[高级加密标准]]、[[國際資料加密演算法]]等。

於計算機科學, 同餘被應用於[[位元運算]]或其他與固定寬度之循環[[資料結構]]相關的操作。

於化學中, [[CAS號]]（一個對各種化合物皆異之的識別碼）的最後一碼為[[校驗碼]]，將[[CAS號]]首二部分最後的數字乘上一，下一碼乘上二，下一碼乘上三以此類推，將所有積加起來再取模10。

在音樂領域，模12用於[[十二平均律]]系統。

[[星期的計算]]中取模7算術極重要。

更廣泛而言，同餘在[[法律]]、[[經濟]]（見[[賽局理論]]）或其他[[社會科學]]領域中也有應用。

==範例==
以下為快速展示小於63位元無號整數之模數乘法的C程式，且轉換過程中不發生溢位。計算 a * b (mod m)之演算法:
<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>


== 注释 ==
{{NoteFoot}}

== 参考文献 ==
{{Reflist|30em}}

== 参见 ==
{{Portal box|数学|信息技术}}
* [[合同_(數學)]]
* [[等價關係]]
* [[模除]]
* [[不定方程]]

[[Category:同余| ]]
[[Category:群论|T]]
[[Category:除法|T]]