同余 (英語:Congruence modulo [1] ,符號 :≡)在数学 中是指數論 中的一種等價關係 [2] 。當两个整数 除 以同一个正整数 ,若得相同余数 ,则二整数同余 。同餘是抽象代數 中的同餘關係 的原型[3] 。最先引用同余的概念 与「≡」符号 者为德國 数学家 高斯 。
各种各样的数 基本 N ⊆ Z ⊆ Q ⊆ R ⊆ C {\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} }
延伸
其他
圓周率 π = 3.14159265 {\displaystyle \pi =3.14159265} …自然對數的底 e = 2.718281828 {\displaystyle e=2.718281828} …虛數單位 i = − 1 {\displaystyle i={\sqrt {-{1}}}} 無限大 ∞ {\displaystyle \infty }
同余符号 编辑 同餘類 编辑
如同任何同余關係 ,對於模 n {\displaystyle n} 同余是一種等價關係 ,整數 a {\displaystyle a} 的等價類 是一個集合 { … , a − 2 n , a − n , a , a + n , a + 2 n , … } {\displaystyle \left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}} ,標記為 a ¯ n {\displaystyle {\overline {a}}_{n}} 。由對於模 n {\displaystyle n} 同餘的所有整數組成的這個集合稱為同余類 (congruence class 或residue class );假若從上下文知道模 n {\displaystyle n} ,則也可標記為 [ a ] {\displaystyle \displaystyle [a]} 。
同余類中的每個元素都可以拿來代表該同余類,稱為該同余類的代表數 (英語:representative )[4] 。
剩餘系 编辑
剩餘系 [5] [6] (英語:residue system )亦即模 n {\displaystyle n} 同餘類的代表數的集合,通常使用的代表數是最小非負整數,因為它是除法中的應當餘數。要注意的是,對於同一個模數 n {\displaystyle n} ,不同的同餘類不等價,亦即,屬於不同同餘類的整數不同餘於模數 n {\displaystyle n} ,或者說,模 n {\displaystyle n} 剩餘系中的任二元素不同餘於模 n {\displaystyle n} ;而且,整數域中的每個整數只屬於模數 n {\displaystyle n} 的一個同餘類,因為模 n {\displaystyle n} 將整數域划分 為互斥區塊,每個區塊是一個同餘類。
一個完全剩餘系 (英語:complete residue system )指的是模 n {\displaystyle n} 的全部同餘類的代表數的集合;因為剩餘系中的任二元素不同餘於模 n {\displaystyle n} ,所以它也稱為非同餘餘數的完整系統 (英語:complete system of incongruent residues )。例如,模 3 {\displaystyle 3} 有三個同餘類 [ 0 ] , [ 1 ] , [ 2 ] {\displaystyle [0],[1],[2]} ,其完全剩餘系可以是 { 9 , 12 + 1 , 15 + 2 } {\displaystyle \{9,12+1,15+2\}} 。如果該集合是由每個同餘類的最小非負整數所組成,亦即 { 0 , 1 , 2 , . . . , n − 1 } {\displaystyle \{0,1,2,...,n-1\}} ,則稱該集合為模 n {\displaystyle n} 的最小剩餘系 (英語:least residue system )。
模 n {\displaystyle n} 完全剩餘系中,與模 n {\displaystyle n} 互質的代表數所構成的集合,稱為模 n {\displaystyle n} 的簡約剩餘系 (英語:reduced residue system ),其元素個數記為 ϕ ( n ) {\displaystyle \phi (n)} ,亦即欧拉函数 。例如,模 6 {\displaystyle 6} 的簡約剩餘系為 { 1 , 5 } {\displaystyle \{1,5\}} 或 { 7 , 11 } {\displaystyle \{7,11\}} 。如果模 n {\displaystyle n} 是質數 ,那麼它的最小簡約剩餘系是 { 1 , 2 , . . . , n − 1 } {\displaystyle \{1,2,...,n-1\}} ,只比最小剩餘系少一個 0 {\displaystyle 0} 。
性质 编辑
整除性 编辑 a ≡ b ( mod m ) ⇒ c ⋅ m = a − b , c ∈ Z {\displaystyle a\equiv b{\pmod {m}}\Rightarrow c\cdot m=a-b,c\in \mathbb {Z} } (即是說 a 和 b 之差是 m 的倍數) 換句話說, a ≡ b ( mod m ) ⇒ m ∣ ( a − b ) {\displaystyle a\equiv b{\pmod {m}}\Rightarrow m\mid (a-b)} [註 1]
同余可以用来检验一个数是否可以整除 另外一个数,见整除规则 。
传递性 编辑 a ≡ b ( mod m ) b ≡ c ( mod m ) } ⇒ a ≡ c ( mod m ) {\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\b\equiv c{\pmod {m}}\end{matrix}}\right\}\Rightarrow a\equiv c{\pmod {m}}}
保持基本运算 编辑 a ≡ b ( mod m ) c ≡ d ( mod m ) } ⇒ { a ± c ≡ b ± d ( mod m ) a c ≡ b d ( mod m ) {\displaystyle \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.} 當 c = d {\displaystyle c=d} 時,則為等量加法、減法: a ± c ≡ b ± c ( mod m ) {\displaystyle a\pm c\equiv b\pm c{\pmod {m}}} 這性質更可進一步引申成為這樣: a ≡ b ( mod m ) ⇒ { a n ≡ b n ( mod m ) , ∀ n ∈ Z a n ≡ b n ( mod m ) , ∀ n ∈ N ∗ P ( a ) ≡ P ( b ) ( mod m ) {\displaystyle 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}}} [註 2] 其中 P ( x ) {\displaystyle P(x)} 为任意整系数多项式函数。
放大縮小底數 编辑 k為整數,n為正整數, ( k m ± a ) n ≡ ( ± a ) n ( mod m ) {\displaystyle (km\pm a)^{n}\equiv (\pm a)^{n}{\pmod {m}}}
放大縮小模數 编辑 k {\displaystyle k} 為正整數, a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} ,若且唯若 k a ≡ k b ( mod k m ) {\displaystyle ka\equiv kb{\pmod {km}}}
除法原理一 编辑 若 k a ≡ k b ( mod m ) {\displaystyle ka\equiv kb{\pmod {m}}} 且 k , m {\displaystyle k,m} 互質 ,則 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}}
除法原理二 编辑 每個正整數都可以分解為數個因數 的乘積,稱為整数分解 。例如 15 = 3 × 5 {\displaystyle 15=3\times 5} ,因數 3 {\displaystyle 3} 與 5 {\displaystyle 5} 都可以整除 15 {\displaystyle 15} ,記為 3 | 15 {\displaystyle 3|15} 與 5 | 15 {\displaystyle 5|15} 。如果 15 {\displaystyle 15} 可以整除某正整數 a {\displaystyle a} ,亦即 15 | a {\displaystyle 15|a} ,那麼 15 {\displaystyle 15} 就是 a {\displaystyle a} 的因數: a = 15 × b {\displaystyle a=15\times b} ,其中 b {\displaystyle b} 為另一因數。 a = 15 × b = ( 3 × 5 ) × b {\displaystyle a=15\times b=(3\times 5)\times b} ,因此, 15 {\displaystyle 15} 的因數也可以整除 a {\displaystyle a} : ( 3 | 15 ) ∧ ( 15 | a ) ⇒ 3 | a {\displaystyle (3|15)\wedge (15|a)\Rightarrow 3|a} 。
a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} 等價於 ( a − b ) ≡ 0 ( mod m ) {\displaystyle (a-b)\equiv 0{\pmod {m}}} ,也就是 m | ( a − b ) {\displaystyle m|(a-b)} 。亦即,如果 m | ( a − b ) {\displaystyle m|(a-b)} ,那麼它可以寫成 a ≡ b ( mod m ) {\displaystyle a\equiv b{\pmod {m}}} ,因此有以下除法原理:
m {\displaystyle m} 的因數也可以整除 ( a − b ) {\displaystyle (a-b)} 。亦即, m {\displaystyle m} 是 n {\displaystyle n} 的倍數 : m = c × n {\displaystyle m=c\times n} , n | m {\displaystyle n|m} 。因為 m | ( a − b ) {\displaystyle m|(a-b)} ,所以 n | ( a − b ) ⇒ a ≡ b ( mod n ) {\displaystyle n|(a-b)\Rightarrow a\equiv b{\pmod {n}}} 。 a ≡ b ( mod c n ) ⇒ a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {cn}}\Rightarrow a\equiv b{\pmod {n}}} a ≡ b ( mod m ) n | m } ⇒ a ≡ b ( mod n ) {\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\n|m\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {n}}} [註 1] 現假設 m {\displaystyle m} 可以整除 ( a − b ) {\displaystyle (a-b)} 的倍數 c ( a − b ) {\displaystyle c(a-b)} 。如果 m {\displaystyle m} 和 c {\displaystyle c} 互質(記為 ( m , c ) = 1 {\displaystyle (m,c)=1} ),那麼 m {\displaystyle m} 必定可以整除 ( a − b ) {\displaystyle (a-b)} : m | ( a − b ) ⇒ a ≡ b ( mod m ) {\displaystyle m|(a-b)\Rightarrow a\equiv b{\pmod {m}}} 。 a c ≡ b c ( mod m ) ( c , m ) = 1 } ⇒ a ≡ b ( mod m ) {\displaystyle \left.{\begin{matrix}ac\equiv bc{\pmod {m}}\\(c,m)=1\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {m}}} [註 3] 如果 m 1 | ( a − b ) {\displaystyle m_{1}|(a-b)} 而且 m 2 | ( a − b ) {\displaystyle m_{2}|(a-b)} ,那麼 m 1 {\displaystyle m_{1}} 與 m 2 {\displaystyle m_{2}} 的最小公倍数 必定可以整除 ( a − b ) {\displaystyle (a-b)} ,記為 a ≡ b ( mod [ m 1 , m 2 ] ) {\displaystyle a\equiv b{\pmod {[m_{1},m_{2}]}}} 。這可以推廣成以下性質: a ≡ b ( mod m 1 ) a ≡ b ( mod m 2 ) ⋮ a ≡ b ( mod m n ) ( n ≥ 2 ) } ⇒ a ≡ b ( mod [ m 1 , m 2 , ⋯ , m n ] ) {\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m_{1}}}\\a\equiv b{\pmod {m_{2}}}\\\vdots \\a\equiv b{\pmod {m_{n}}}\\(n\geq 2)\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {[m_{1},m_{2},\cdots ,m_{n}]}}} [註 4] 上面的最後一個性質可以使用算术基本定理 與集合 來解釋。一個大於1的正整數 q {\displaystyle q} 可以分解為一串質數 冪的乘積: q = p 1 c 1 × p 2 c 2 × . . . × p n c n {\displaystyle q=p_{1}^{c_{1}}\times p_{2}^{c_{2}}\times ...\times p_{n}^{c_{n}}} ( p i {\displaystyle p_{i}} 兩兩相異,且 c i > 0 {\displaystyle c_{i}>0} ),令 S q {\displaystyle S_{q}} 為所有能整除 q {\displaystyle q} 的質數冪的集合,即 S q = { p 1 , p 1 2 , ⋯ , p 1 c 1 , p 2 , p 2 2 , ⋯ , p 2 c 2 , ⋯ , p n , p n 2 , ⋯ , p n c n } {\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}}\}} 。設 r {\displaystyle r} 為正整數,則 r {\displaystyle r} 整除 q {\displaystyle q} ,當且僅當 S r {\displaystyle S_{r}} 是 S q {\displaystyle S_{q}} 的子集 。令 m 1 | q {\displaystyle m_{1}|q} 且 m 2 | q {\displaystyle m_{2}|q} ,則 S m 1 {\displaystyle S_{m_{1}}} 與 S m 2 {\displaystyle S_{m_{2}}} 的聯集 必定也是 S q {\displaystyle S_{q}} 的子集。取這個聯集中冪次最高的各個元素 ,它們的乘積就是 m 1 {\displaystyle m_{1}} 與 m 2 {\displaystyle m_{2}} 的最小公倍数 [ m 1 , m 2 ] {\displaystyle [m_{1},m_{2}]} 。事實上,有 S [ m 1 , m 2 ] = S m 1 ∪ S m 2 {\displaystyle S_{[m_{1},m_{2}]}=S_{m_{1}}\cup S_{m_{2}}} ,所以 [ m 1 , m 2 ] {\displaystyle [m_{1},m_{2}]} 也能夠整除 q {\displaystyle q} 。 同余关系式 编辑 相关概念 编辑
模反元素 编辑 a − 1 a ˙ ≡ 1 ( mod n ) {\displaystyle a^{-1}{\dot {a}}\equiv 1{\pmod {n}}}
可用輾轉相除法 、歐拉定理 、卡邁克爾函數 求解。
原根 编辑 存在最小的正整数d使得 a d ≡ 1 ( mod n ) {\displaystyle a^{d}\equiv 1{\pmod {n}}} 成立,且 d = φ ( n ) {\displaystyle d=\varphi (n)} 。
同余方程 编辑 线性同余方程 编辑 a x ≡ b ( mod n ) {\displaystyle ax\equiv b{\pmod {n}}}
考虑最大公约数 ,有解时用輾轉相除法 等方法求解。
线性同余方程组 编辑 { a 1 x ≡ b 1 ( mod m 1 ) a 2 x ≡ b 2 ( mod m 2 ) ⋮ a n x ≡ b n ( mod m n ) {\displaystyle {\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}}}
先求解每一个线性同余方程,再用中国剩余定理 解方程组。
二次剩余 编辑 x 2 ≡ d ( mod p ) {\displaystyle x^{2}\equiv d{\pmod {p}}}
勒让德符号 、雅可比符号 、克罗内克符号 、二次互反律 用于判别d是否为模n的二次剩余。
高次剩餘 编辑 x n ≡ d ( mod p ) {\displaystyle x^{n}\equiv d{\pmod {p}}}
例子 编辑 求自然数 a的个位数字,就是求a与哪一个数对于模10同余。 10 ≡ 1 ( mod 3 ) , 10 n ≡ 1 ( mod 3 ) , 10001 ≡ 10 4 + 1 ≡ 1 + 1 ( mod 3 ) {\displaystyle 10\equiv 1({\textrm {mod}}\ 3),10^{n}\equiv 1({\textrm {mod}}\ 3),10001\equiv 10^{4}+1\equiv 1+1({\textrm {mod}}\ 3)} 。應用 编辑 範例 编辑 以下為快速展示小於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 ; }
注释 编辑 参考文献 编辑 参见 编辑