Modular Arithmetic 模算術(shù)

我們都見過時鐘，在時鐘上有12個刻度。假設(shè)某天晚上時針指向6的位置，那么它表示的是晚上六點鐘，可是到了第二天早上，當時針再次指向6時，它表示的又是早上六點鐘。

在上述例子中，我們實際上是用同一個刻度來表示兩個不同的“六點鐘”，這就是模算術(shù)的基本思路–用同一個刻度表示不同的值（也可以用輪回來理解）。

模算術(shù)的定義
令$a$，$b$和$n$為整數(shù)且$n>0$，那么當且僅當$n$可以整除$(a?b)$時，$a$和$b$是模$n$同余的，寫作：

$$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)?n|(a?b)$$

這里的 $n|(a?b)$ 表示 $kn=(a?b),k$為整數(shù)。

什么是同余 Congruence Modulo
當$kn=(a?b)$時，$a$和$b$可寫為：
$$\begin{array}{rl}a& =pn+r\\ b& =qn+r\end{array}$$
$r$是他們共同的余數(shù)，$n$為同余的模數(shù)（也就是除數(shù)）。

例如：$7(=1\times 6+1)$和$13(=2\times 6+1)$對模數(shù)6同余。 類似的數(shù)還有19，25，31，$\dots$，$(n\times 6+1)$。將這些數(shù)畫在數(shù)軸上，我們可以發(fā)現(xiàn)在每一個長度為6的區(qū)間上，都只有一個這樣的數(shù)存在，并且他們都出現(xiàn)在各自區(qū)間內(nèi)“相同的位置”上。因此我們可以在不同區(qū)間內(nèi)用同一個刻度表示不同的值。

由對于模$n$同余的所有整數(shù)組成的集合稱為同余類。

同余類 Congruence Class

給定任意整數(shù)$b>0$，我們可以將數(shù)軸上的整數(shù)劃分到長度為$b$的區(qū)間內(nèi)。對于$a\in [0,b?1]$，集合$\{a+kb\}$的所有數(shù)對于模$b$同余，余數(shù)為$a$，構(gòu)成一個同余類，記作：
$$[a{]}_b=\{a+kb|k\in \mathbb{Z}\}$$

模算術(shù)的規(guī)則

• 加法：如果有$a\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$和$b\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}n)$，那么$a+b\equiv c+d(\mathrm{m}\mathrm{o}\mathrm{d}n)$

• 乘法：如果有$a\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$和$b\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}n)$，那么$ab\equiv cd(\mathrm{m}\mathrm{o}\mathrm{d}n)$

• $?a,a\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}n)$

• 如果有$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$，那么$b\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}n)$

• 如果有$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$和$b\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$，那么$a\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}n)$

• 如果有$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$和$n\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)$，那么$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}m)$

• 如果有$a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$，那么$am\equiv bm(\mathrm{m}\mathrm{o}\mathrm{d}n)$和$a^m\equiv b^m(\mathrm{m}\mathrm{o}\mathrm{d}n)$

模的倒數(shù) Multiplicative Inverse
對于$a\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$，若有整數(shù)$a^{\prime }$滿足$a{a}^{\prime }\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$，則稱$a^{\prime }$為$a$的倒數(shù)。例如：$2\times 5\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)$，所以$a^{\prime }=5$是整數(shù)$2(\mathrm{m}\mathrm{o}\mathrm{d}3)$的倒數(shù)（反之亦然）。

并不是所有的整數(shù)對于任意模數(shù)都有倒數(shù)。對于$a(\mathrm{m}\mathrm{o}\mathrm{d}n)$，如果整數(shù)$a$和$n$不互質(zhì)，那么$a$就沒有對于模數(shù)$n$的倒數(shù)。

中國余數(shù)定理

古時有一位將軍統(tǒng)領(lǐng)著一支1500人的軍隊，一場大戰(zhàn)過后，大約400~500人死亡。為了統(tǒng)計剩下的人數(shù)，將軍讓士兵們站成方陣。當剩下的人3個站成一行時，多余2個人。當剩下的人5個站成一行時，多余4個人。當剩下的人7個站成一行時，多余6個人。那么這支軍隊總共還有多少士兵？

這個問題實際上就是求解同余方程組
$$?\begin{array}{r}{c}_{1}x\equiv d_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ c_{2}x\equiv d_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\\ \dots \\ c_{k}x\equiv d_k(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k)\end{array}$$

先來思考如何求解 $ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$，

當$\mathrm{g}\mathrm{c}\mathrm{d}(a,n)=1$時：$a$和$n$互質(zhì)，因此存在$a^{\prime }$使得$a{a}^{\prime }\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$。我們對式子兩邊同乘$a^{\prime }$，得
$$x\equiv a^{\prime }b(\mathrm{m}\mathrm{o}\mathrm{d}n)$$

當 $\mathrm{g}\mathrm{c}\mathrm{d}(a,n)=c>1$時：
2.1. 如果$c$可以整除$b$：對于$ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$可得
$$\begin{array}{rl}& ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)\\ ?& ax=b+nk\\ ?& a_{1}cx=b_{1}c+n_{1}ck\\ ?& a_{1}x=b_{1}x+n_{1}k\end{array}$$
此時$a_1,n_1$互質(zhì)，因此可以歸為$a,n$互質(zhì)一類。
2.2. 如果$c$不能整除$b$：
$$\begin{array}{rl}& ax\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)\\ ?& ax=b+nk\\ ?& a_{1}cx=b+n_{1}ck\\ ?& b=c(a_{1}x?n_{1}k)\end{array}$$
與假設(shè)矛盾，無解。

經(jīng)過化簡（當然，也存在無法化簡的情況）以后，方程組可寫為
$$?\begin{array}{r}x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{n}_1)\\ x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{n}_2)\\ \dots \\ x\equiv a_k(\mathrm{m}\mathrm{o}\mathrm{d}{n}_k)\end{array}$$
假設(shè)$n_1,n_2,\dots ,n_k$之間兩兩互質(zhì)，則該方程組對于模$N=n_1{n}_2\dots n_k$有唯一解，解為
$$x\equiv (N_1{N}_1^{\prime }{a}_1+N_2{N}_2^{\prime }{a}_2+?+N_k{N}_k^{\prime }{a}_k)(\mathrm{m}\mathrm{o}\mathrm{d}N)$$
其中$N_i=\frac{N}{n_i}$，$N_i^{\prime }$為$N_i$對于模$n_i$的倒數(shù)。

取模運算
在計算機中，給定整數(shù)$a$，$b$，取模運算就是求$a$除以$b$的余數(shù)：$a$%$b$
關(guān)于取余運算的實現(xiàn)邏輯可參考匯編除法原理

總結(jié)

以上是生活随笔為你收集整理的Modular Arithmetic 模算术的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。