同餘














各种各样的數

基本

N⊆Z⊆Q⊆R⊆C{displaystyle mathbb {N} subseteq mathbb {Z} subseteq mathbb {Q} subseteq mathbb {R} subseteq mathbb {C} }mathbb {N} subseteq mathbb {Z} subseteq mathbb {Q} subseteq mathbb {R} subseteq mathbb {C}
NumberSetinC.svg







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

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


延伸






雙曲複數
雙複數
四元數 H{displaystyle mathbb {H} }{mathbb {H}}
共四元數（英语：Dual quaternion）
八元數 O{displaystyle mathbb {O} }mathbb{O}
超數
上超實數

超复数
十六元數 S{displaystyle mathbb {S} }mathbb {S}
複四元數
大實數
超實數 ∗R{displaystyle ^{*}mathbb {R} }{displaystyle ^{*}mathbb {R} }
超現實數


其他






对偶数
序数
質數 P{displaystyle mathbb {P} }mathbb {P}
同餘
可計算數
整數數列
數學常數

公稱值
超限数
基數
P進數
規矩數
可定義數
阿列夫數

圓周率 π=3.141592653…{displaystyle pi =3.141592653dots }{displaystyle pi =3.141592653dots }
自然對數的底 e=2.718281828…{displaystyle e=2.718281828dots }{displaystyle e=2.718281828dots }
虛數單位 i=−1{displaystyle i={sqrt {-1}}}{displaystyle i={sqrt {-1}}}
無窮大 ∞{displaystyle infty }infty



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




目录






  • 1 同余符号


  • 2 同餘類


  • 3 餘數系統


  • 4 性质


    • 4.1 整除性


    • 4.2 传递性


    • 4.3 保持基本运算


    • 4.4 放大縮小底數


    • 4.5 放大縮小模數


    • 4.6 除法原理一


    • 4.7 除法原理二




  • 5 同余关系式


    • 5.1 威尔逊定理


    • 5.2 费马小定理


    • 5.3 欧拉定理


    • 5.4 卡邁克爾函數


    • 5.5 阶乘幂


    • 5.6 卢卡斯定理


    • 5.7 组合数最小周期




  • 6 相关概念


    • 6.1 模反元素


    • 6.2 原根




  • 7 同余方程


    • 7.1 线性同余方程


    • 7.2 线性同余方程组


    • 7.3 二次剩余


    • 7.4 高次剩餘




  • 8 例子


  • 9 應用


  • 10 範例


  • 11 注释


  • 12 参考文献


  • 13 参见





同余符号


两个整数a{displaystyle a}a，b{displaystyle b}b，若它们除以正整数m{displaystyle m}m所得的余数相等，则称a{displaystyle a}a，b{displaystyle b}b对于模m{displaystyle m}m同余


记作a≡b(modm){displaystyle aequiv b{pmod {m}}}aequiv b{pmod {m}}


读作a{displaystyle a}a同余于b{displaystyle b}b模m{displaystyle m}m，或读作a{displaystyle a}a与b{displaystyle b}b关于模m{displaystyle m}m同余。


比如26≡14(mod12){displaystyle 26equiv 14{pmod {12}}}26equiv 14{pmod {12}}。


同餘於的符號是同餘相等符號≡。統一碼值為U+2261。



同餘類


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


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



餘數系統


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


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


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



性质



整除性


a≡b(modm)⇒c⋅m=a−b,c∈Z{displaystyle aequiv b{pmod {m}}Rightarrow ccdot m=a-b,cin mathbb {Z} }aequiv b{pmod {m}}Rightarrow ccdot m=a-b,cin mathbb {Z} （即是說 a 和 b 之差是 m 的倍數）
換句話說，a≡b(modm)⇒m∣(a−b){displaystyle aequiv b{pmod {m}}Rightarrow mmid (a-b)}aequiv b{pmod {m}}Rightarrow mmid (a-b)[註 1]


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



传递性


a≡b(modm)b≡c(modm)}⇒a≡c(modm){displaystyle left.{begin{matrix}aequiv b{pmod {m}}\bequiv c{pmod {m}}end{matrix}}right}Rightarrow aequiv c{pmod {m}}}left.{begin{matrix}aequiv b{pmod {m}}\bequiv c{pmod {m}}end{matrix}}right}Rightarrow aequiv c{pmod {m}}



保持基本运算


a≡b(modm)c≡d(modm)}⇒{a±c≡b±d(modm)ac≡bd(modm){displaystyle left.{begin{matrix}aequiv b{pmod {m}}\cequiv d{pmod {m}}end{matrix}}right}Rightarrow left{{begin{matrix}apm cequiv bpm d{pmod {m}}\acequiv bd{pmod {m}}end{matrix}}right.}left.{begin{matrix}aequiv b{pmod {m}}\cequiv d{pmod {m}}end{matrix}}right}Rightarrow left{{begin{matrix}apm cequiv bpm d{pmod {m}}\acequiv bd{pmod {m}}end{matrix}}right.
這性質更可進一步引申成為這樣：
a≡b(modm)⇒{an≡bn(modm),∀n∈Zan≡bn(modm),∀n∈N0{displaystyle aequiv b{pmod {m}}Rightarrow {begin{cases}anequiv bn{pmod {m}},forall nin mathbb {Z} \a^{n}equiv b^{n}{pmod {m}},forall nin mathbb {N} ^{0}end{cases}}}aequiv b{pmod {m}}Rightarrow {begin{cases}anequiv bn{pmod {m}},forall nin mathbb {Z} \a^{n}equiv b^{n}{pmod {m}},forall nin mathbb {N} ^{0}end{cases}}[註 2]



放大縮小底數


k為整數，n為正整數，(km±a)n≡(±a)n(modm){displaystyle (kmpm a)^{n}equiv (pm a)^{n}{pmod {m}}}{displaystyle (kmpm a)^{n}equiv (pm a)^{n}{pmod {m}}}



放大縮小模數


k{displaystyle k}k為正整數，a≡b(modm){displaystyle aequiv b{pmod {m}}}aequiv b{pmod {m}}，若且唯若ka≡kb(modkm){displaystyle kaequiv kb{pmod {km}}}{displaystyle kaequiv kb{pmod {km}}}



除法原理一


若ka≡kb(modm){displaystyle kaequiv kb{pmod {m}}}{displaystyle kaequiv kb{pmod {m}}}且k,m{displaystyle k,m}{displaystyle k,m}互質，則a≡b(modm){displaystyle aequiv b{pmod {m}}}aequiv b{pmod {m}}



除法原理二


每個正整數都可以分解為數個因數的乘積，稱為整数分解。例如 15=3×5{displaystyle 15=3times 5}15=3times 5，因數 3{displaystyle 3}3 與 5{displaystyle 5}5 都可以整除 15{displaystyle 15}15，記為 3|15{displaystyle 3|15}3|15 與 5|15{displaystyle 5|15}5|15。如果 15{displaystyle 15}15 可以整除某正整數 a{displaystyle a}a，亦即 15|a{displaystyle 15|a}15|a，那麼 15{displaystyle 15}15 就是 a{displaystyle a}a 的因數：a=15×b{displaystyle a=15times b}a=15times b，其中 b{displaystyle b}b 為另一因數。a=15×b=(3×5)×b{displaystyle a=15times b=(3times 5)times b}a=15times b=(3times 5)times b，因此，15{displaystyle 15}15 的因數也可以整除 a{displaystyle a}a：(3|15)∧(15|a)⇒3|a{displaystyle (3|15)wedge (15|a)Rightarrow 3|a}(3|15)wedge (15|a)Rightarrow 3|a。


a≡b(modm){displaystyle aequiv b{pmod {m}}}aequiv b{pmod {m}} 等價於 (a−b)≡0(modm){displaystyle (a-b)equiv 0{pmod {m}}}(a-b)equiv 0{pmod {m}}，也就是 m|(a−b){displaystyle m|(a-b)}m|(a-b)。亦即，如果 m|(a−b){displaystyle m|(a-b)}m|(a-b)，那麼它可以寫成 a≡b(modm){displaystyle aequiv b{pmod {m}}}aequiv b{pmod {m}}，因此有以下除法原理：



m{displaystyle m}m 的因數也可以整除 (a−b){displaystyle (a-b)}(a-b)。亦即，m{displaystyle m}m 是 n{displaystyle n}n 的倍數：m=c×n{displaystyle m=ctimes n}m=ctimes n，n|m{displaystyle n|m}n|m。因為 m|(a−b){displaystyle m|(a-b)}m|(a-b)，所以 n|(a−b)⇒a≡b(modn){displaystyle n|(a-b)Rightarrow aequiv b{pmod {n}}}n|(a-b)Rightarrow aequiv b{pmod {n}}。


a≡b(modcn)⇒a≡b(modn){displaystyle aequiv b{pmod {cn}}Rightarrow aequiv b{pmod {n}}}aequiv b{pmod {cn}}Rightarrow aequiv b{pmod {n}}



a≡b(modm)n|m}⇒a≡b(modn){displaystyle left.{begin{matrix}aequiv b{pmod {m}}\n|mend{matrix}}right}Rightarrow aequiv b{pmod {n}}}left.{begin{matrix}aequiv b{pmod {m}}\n|mend{matrix}}right}Rightarrow aequiv b{pmod {n}}[註 1]


現假設 m{displaystyle m}m 可以整除 (a−b){displaystyle (a-b)}(a-b) 的倍數 c(a−b){displaystyle c(a-b)}c(a-b)。如果 m{displaystyle m}m 和 c{displaystyle c}c 互質（記為 (m,c)=1{displaystyle (m,c)=1}(m,c)=1），那麼 m{displaystyle m}m 必定可以整除 (a−b){displaystyle (a-b)}(a-b)：m|(a−b)⇒a≡b(modm){displaystyle m|(a-b)Rightarrow aequiv b{pmod {m}}}m|(a-b)Rightarrow aequiv b{pmod {m}}。


ac≡bc(modm)(c,m)=1}⇒a≡b(modm){displaystyle left.{begin{matrix}acequiv bc{pmod {m}}\(c,m)=1end{matrix}}right}Rightarrow aequiv b{pmod {m}}}left.{begin{matrix}acequiv bc{pmod {m}}\(c,m)=1end{matrix}}right}Rightarrow aequiv b{pmod {m}}[註 3]

如果 m1|(a−b){displaystyle m_{1}|(a-b)}m_{1}|(a-b) 而且 m2|(a−b){displaystyle m_{2}|(a-b)}m_{2}|(a-b)，那麼 m1{displaystyle m_{1}}m_{1} 與 m2{displaystyle m_{2}}m_{2} 的最小公倍数必定可以整除 (a−b){displaystyle (a-b)}(a-b)，記為 a≡b(mod[m1,m2]){displaystyle aequiv b{pmod {[m_{1},m_{2}]}}}aequiv b{pmod {[m_{1},m_{2}]}}。這可以推廣成以下性質：


a≡b(modm1)a≡b(modm2)⋮a≡b(modmn)(n≥2)}⇒a≡b(mod[m1,m2,⋯,mn]){displaystyle left.{begin{matrix}aequiv b{pmod {m_{1}}}\aequiv b{pmod {m_{2}}}\vdots \aequiv b{pmod {m_{n}}}\(ngeq 2)end{matrix}}right}Rightarrow aequiv b{pmod {[m_{1},m_{2},cdots ,m_{n}]}}}left.{begin{matrix}aequiv b{pmod {m_{1}}}\aequiv b{pmod {m_{2}}}\vdots \aequiv b{pmod {m_{n}}}\(ngeq 2)end{matrix}}right}Rightarrow aequiv b{pmod {[m_{1},m_{2},cdots ,m_{n}]}}[註 4]

上面的最後一個性質可以使用算术基本定理與集合來解釋。一個大於1的正整數 q{displaystyle q}q 可以分解為一串質數冪的乘積：q=p1c1×p2c2×...×pncn{displaystyle q=p_{1}^{c_{1}}times p_{2}^{c_{2}}times ...times p_{n}^{c_{n}}}q=p_{1}^{c_{1}}times p_{2}^{c_{2}}times ...times p_{n}^{c_{n}}（pi{displaystyle p_{i}}p_{i} 兩兩相異，且ci>0{displaystyle c_{i}>0}c_{i}>0），令 Sq{displaystyle S_{q}}S_{q} 為所有能整除 q{displaystyle q}q 的質數冪的集合，即 Sq={p1,p12,⋯,p1c1,p2,p22,⋯,p2c2,⋯,pn,pn2,⋯,pncn}{displaystyle 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}}}}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{displaystyle r}r 為正整數，則 r{displaystyle r}r 整除 q{displaystyle q}q，當且僅當 Sr{displaystyle S_{r}}S_{r} 是 Sq{displaystyle S_{q}}S_{q} 的子集。令 m1|q{displaystyle m_{1}|q}m_{1}|q 且 m2|q{displaystyle m_{2}|q}m_{2}|q，則Sm1{displaystyle S_{m_{1}}}S_{m_{1}} 與 Sm2{displaystyle S_{m_{2}}}S_{m_{2}} 的聯集必定也是 Sq{displaystyle S_{q}}S_{q} 的子集。取這個聯集中冪次最高的各個元素，它們的乘積就是 m1{displaystyle m_{1}}m_{1} 與 m2{displaystyle m_{2}}m_{2} 的最小公倍数[m1,m2]{displaystyle [m_{1},m_{2}]}[m_{1},m_{2}]。事實上，有 S[m1,m2]=Sm1∪Sm2{displaystyle S_{[m_{1},m_{2}]}=S_{m_{1}}cup S_{m_{2}}}S_{[m_{1},m_{2}]}=S_{m_{1}}cup S_{m_{2}}，所以 [m1,m2]{displaystyle [m_{1},m_{2}]}[m_{1},m_{2}] 也能夠整除 q{displaystyle q}q 。


同余关系式



威尔逊定理


主条目：威爾遜定理

(p−1)! ≡ −1 (mod p){displaystyle (p-1)! equiv -1 ({mbox{mod}} p)}(p-1)! equiv -1 ({mbox{mod}} p)



费马小定理


主条目：费马小定理

ap≡a(modp){displaystyle a^{p}equiv a{pmod {p}}}{displaystyle a^{p}equiv a{pmod {p}}}



欧拉定理


主条目：歐拉定理 (數論)

aφ(n)≡1(modn){displaystyle a^{varphi (n)}equiv 1{pmod {n}}}a^{varphi (n)}equiv 1{pmod {n}}



卡邁克爾函數


主条目：卡邁克爾函數

aλ(n)≡1(modn){displaystyle a^{lambda (n)}equiv 1{pmod {n}}}a^{lambda (n)}equiv 1{pmod {n}}



阶乘幂


主条目：阶乘幂

(x)k≡x(x−1)(x−2)⋯(x−k+1)≡0(modk!){displaystyle (x)_{k}equiv x(x-1)(x-2)cdots (x-k+1)equiv 0{pmod {k!}}}(x)_{k}equiv x(x-1)(x-2)cdots (x-k+1)equiv 0{pmod {k!}}



卢卡斯定理


主条目：卢卡斯定理

(mn)≡∏i=0k(mini)(modp),{displaystyle {binom {m}{n}}equiv prod _{i=0}^{k}{binom {m_{i}}{n_{i}}}{pmod {p}},}{displaystyle {binom {m}{n}}equiv prod _{i=0}^{k}{binom {m_{i}}{n_{i}}}{pmod {p}},}



组合数最小周期


(m+pk+[logpn]n)≡(mn)(modpk){displaystyle {binom {m+p^{k+[log_{p}n]}}{n}}equiv {binom {m}{n}}{pmod {p^{k}}}}{displaystyle {binom {m+p^{k+[log_{p}n]}}{n}}equiv {binom {m}{n}}{pmod {p^{k}}}}


设N=∏ipiki{displaystyle N=prod _{i}p_{i}^{k_{i}}}{displaystyle N=prod _{i}p_{i}^{k_{i}}}，则(m+L(n,N)n)≡(mn)(modN){displaystyle {binom {m+L(n,N)}{n}}equiv {binom {m}{n}}{pmod {N}}}{displaystyle {binom {m+L(n,N)}{n}}equiv {binom {m}{n}}{pmod {N}}}，其中L(n,N)=∏ipiki+[logpn]=N∏ipi[logpn]{displaystyle L(n,N)=prod _{i}p_{i}^{k_{i}+[log_{p}n]}=Nprod _{i}p_{i}^{[log_{p}n]}}{displaystyle L(n,N)=prod _{i}p_{i}^{k_{i}+[log_{p}n]}=Nprod _{i}p_{i}^{[log_{p}n]}}[5]



相关概念



模反元素


主条目：模反元素

a−1a˙≡1(modn){displaystyle a^{-1}{dot {a}}equiv 1{pmod {n}}}a^{-1}{dot {a}}equiv 1{pmod {n}}


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



原根


主条目：原根

存在最小的正整数d使得ad≡1(modn){displaystyle a^{d}equiv 1{pmod {n}}}a^{d}equiv 1{pmod {n}}成立，且d=φ(n){displaystyle d=varphi (n)}d=varphi (n)。



同余方程



线性同余方程


主条目：线性同余方程

ax≡b(modn){displaystyle axequiv b{pmod {n}}}axequiv b{pmod {n}}


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



线性同余方程组


主条目：中国剩余定理

{a1x≡b1(modm1)a2x≡b2(modm2)⋮anx≡bn(modmn){displaystyle {begin{cases}a_{1}xequiv b_{1}{pmod {m_{1}}}\a_{2}xequiv b_{2}{pmod {m_{2}}}\qquad qquad vdots \a_{n}xequiv b_{n}{pmod {m_{n}}}\end{cases}}}{begin{cases}a_{1}xequiv b_{1}{pmod {m_{1}}}\a_{2}xequiv b_{2}{pmod {m_{2}}}\qquad qquad vdots \a_{n}xequiv b_{n}{pmod {m_{n}}}\end{cases}}


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



二次剩余


主条目：二次剩余

x2≡d(modp){displaystyle x^{2}equiv d{pmod {p}}}x^{2}equiv d{pmod {p}}


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



高次剩餘


主条目：高次剩餘

xn≡d(modp){displaystyle x^{n}equiv d{pmod {p}}}x^{n}equiv d{pmod {p}}



例子


  • 求自然数a的个位数字，就是求a与哪一个数对于模10同余。


  • 10≡1(mod 3),10n≡1(mod 3),10001≡104+1≡1+1(mod 3){displaystyle 10equiv 1({textrm {mod}} 3),10^{n}equiv 1({textrm {mod}} 3),10001equiv 10^{4}+1equiv 1+1({textrm {mod}} 3)}10equiv 1({textrm {mod}} 3),10^{n}equiv 1({textrm {mod}} 3),10001equiv 10^{4}+1equiv 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.01.1 m∣x{displaystyle mmid x}mmid x 表示 m 能整除 x，或者说 x 能被 m 整除。


  2. ^ 但是，an≡bn(modm){displaystyle a^{n}equiv b^{n}{pmod {m}}}{displaystyle a^{n}equiv b^{n}{pmod {m}}}不能推論a≡b(modm){displaystyle aequiv b{pmod {m}}}aequiv b{pmod {m}}.


  3. ^ (m1,m2,⋯,mn){displaystyle (m_{1},m_{2},cdots ,m_{n})}(m_{1},m_{2},cdots ,m_{n})表示m1,m2,⋯,mn{displaystyle m_{1},m_{2},cdots ,m_{n}}m_{1},m_{2},cdots ,m_{n}的最大公约数。


  4. ^ [m1,m2,⋯,mn]{displaystyle [m_{1},m_{2},cdots ,m_{n}]}[m_{1},m_{2},cdots ,m_{n}]表示m1,m2,⋯,mn{displaystyle m_{1},m_{2},cdots ,m_{n}}m_{1},m_{2},cdots ,m_{n}的最小公倍数。



参考文献





  1. ^ Khan Academy > Congruence Modulo


  2. ^ Abstract algebra, I. H. Sheth, p.57


  3. ^ e-Study Guide for: Handbook of Mathematics: Mathematics, Mathematics, p.174


  4. ^ A Computational Introduction to Number Theory and Algebra, Victor Shoup, p.25


  5. ^ Chi-Jen Lu; Shi-Chun Tsaiy. The Periodic Property of Binomial Coefficients Modulo m and Its Applications. 10th SIAM Conference on Discrete Mathematics. 2000. 




参见




  • 合同_(數學)

  • 等價關係

  • 模除

  • 不定方程




-

Popular posts from this blog

Guess what letter conforming each word

Image
6 $begingroup$ This is an entry in the Fortnightly Topic Challenge #41: Short and Sweet. 1 letter only could be mean anything . With an additional letter in front , could be used as medicine component and something you definitely learn or at least heard once. Add another letter in front , you would possibly hear that many times . Add an additional letter in front , you would found an independent country . With an additional letter, in the end , you would found something related to apple . Add another letter in the end , you would found something bad . Hint: Each letter is unique . word knowledge letters chemistry share | improve this question ...
Read more

Port of Spain

Image
For ports in the country of Spain, see List of ports in Spain. City in City of Port of Spain, Trinidad and Tobago Port of Spain City City of Port of Spain Top to bottom (left to right): Skyline of Port of Spain from Gulf of Paria; National Academy for the Performing Arts, Independence Square, Eric Williams Plaza; MovieTowne, Port of Port of Spain Motto(s):  "We Gather Strength As We Go Along" Port of Spain Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Coordinates: 10°40′N 61°31′W  /  10.667°N 61.517°W  / 10.667; -61.517 Country   Trinidad and Tobago Jurisdiction City of Port of Spain Settled 1560 Incorporated (town) 1853 Incorporated (city) 1914 Government  • Mayor Joel Martinez  • Governing body City Corporation Area [1]  • City 12 km 2 (5 sq mi) Elevation [2] 66 m (217 ft) Population (2011) [1]  • City 37,074  • Rank 3rd  • Density 3,090/km 2 (8,000/sq mi)...
Read more

Run scheduled task as local user group (not BUILTIN)

Image
0 I am trying to run a scheduled task with User Group (not a single user). This is working fine when I in the field "when running a task, use the following user account:" insert BUILTIN User Group (for example: Administrators or Users). But when I try it with the created Local User Group (example: TestGroup) it is not working. The Users in the TestGroup are the same as in the Administrators group. What could be the problem? Are there some restrictions to the Created User Group compared to BUILTINUsers? scheduled-tasks taskscheduler windowstaskschedule share | improve this question asked Nov 15 '18 at 15:36 Far...
Read more