Profile Image of the Author
Blade/磯江
君の手は どうしてこんなにも温かいの？♫/ねぇお願い どうかこのまま 離さないでいて♫
分類
標籤
2180 字
11 分鐘
02 Modular Arithmetics
2025-04-10
大學修課
discrete-math

課程總覽

Congruence#

同餘是數論中很重要的一環。同餘關係的使用，代表我們討論的數學不再僅限整數、實數等無限長的域，而討論一個會「循環」的域。這一點在計算機中尤其重要。現代計算機的本質是位元操作，其在實際上總是只能代表「有限」的數字，這體現在「溢位」這個現象，而同餘關係很適合用來為這樣的系統建模。〔個人心得〕

Compatibilities towards Basic Arithmetic#

模運算適用許多基本運算，如加法、減法、同乘等等。

Proposition

a≡b (mod m),c≡d (mod m)  ⟹  {(a+c)≡(b+d) (mod m)(1)a⋅c≡b⋅d (mod m)(2)a\equiv b \,( \text{mod }m ) , c\equiv d \,( \text{mod }m ) \implies \left\{\begin{aligned} (a+c) & \equiv (b + d) \,( \text{mod }m ) & (1) \\ a \cdot c & \equiv b \cdot d \,( \text{mod }m ) & (2) \end{aligned}\right.

Proof(1) 根據定義，mm整除a−ba-b跟c−dc-d，因此我們可以設任意整數k1,k2k_{1},k_{2}使得

(a−b)=k1m;(c−d)=k2m.(a - b)= k_{1} m ;(c- d) = k_{2} m.

則我們可以將兩式合併，得(a−b)+(c−d)=(k1+k2)m{(a - b) + (c - d) = (k_{1} + k_{2})m}，重新整理得(a+c)−(b+d)=(k1+k2)m{(a + c) - (b + d) = (k_{1} + k_{2})m}，便符合同餘的定義。■\blacksquare

Proof(2) 略，跟Proof(1)操作方式相似。□\square

Other Trivial Cases#

模(c⋅m)(c\cdot m)除以任意因數cc，同餘式仍成立：

a≡b (mod c⋅m)  ⟹  a≡b (mod m)a \equiv b \,( \text{mod } c\cdot m ) \implies a \equiv b \,( \text{mod } m )

Bezout’s Identity#

任意兩個數的線性組合必可以組出他們的最大公因數：

(∀a,b ∃x,y) a⋅x+b⋅y=gcd(a,b),(\forall a, b \ \exists x,y)\ a\cdot x + b \cdot y = \text{gcd}(a, b),

而這個計算可以透過extended Euclidean algorithm求得。

Extended Euclidean Algorithm#

Example 找31, 17的線性組合。即解31x+17y=gcd(31,17){31x + 17y = \text{gcd}(31, 17)}。

首先用輾轉相除法，求得gcd(31,17){\text{gcd}(31, 17)}。其計算過程對於extended Euclidean是有幫助的。

31=17⋅1+1417=14⋅1+314=3⋅4+23=2⋅1+12=1⋅2+0\begin{aligned} 31 & = 17 \cdot 1 + 14 \\ 17 & = 14 \cdot 1 + 3 \\ 14 & = 3 \cdot 4 + 2 \\ 3 & = 2 \cdot 1 + 1 \\ 2 & = 1 \cdot 2 + 0 \end{aligned}

若寫成直式就是：

得到算式與最大公因數後，接著執行extended Euclidean，有點像是「逆推」：

gcd(31,17)=1=3−2⋅1=3−(14−3⋅4)⋅1=−14+3⋅5=−14+(17−14⋅1)⋅5=17⋅5+14⋅(−6)=17⋅5+(31−17⋅1)⋅(−6)=31⋅(−6)+17⋅11\begin{aligned} \text{gcd}(31, 17) & =1 \\ & =3 - 2\cdot 1 \\ & = 3 - (14 - 3 \cdot 4) \cdot 1 & & = -14 + 3 \cdot 5 \\ & = - 14 + (17 - 14 \cdot 1) \cdot 5 & & = 17\cdot 5 + 14 \cdot (-6) \\ & = 17\cdot 5 + (31 - 17 \cdot 1) \cdot (-6) & & = 31 \cdot (-6) + 17 \cdot 11 \end{aligned}

∴\therefore我們得到x=−6,y=11{x = -6, y = 11} ■\blacksquare

Use Cases#

我們可以利用extended Euclidean來求某些「同餘方程式」，比如：

17x=8(mod 31)17 x = 8 ( \text{mod }31 )

透過同餘的定義，我們知道3131整除17x−817x - 8，寫作31∣(17x−8){31 | (17x - 8)}；再根據整除的定義，又可用一任意整數kk，寫作17x−8=31k{17x - 8 = 31k}。 經過整理可得17x+31(−k)=8{17x + 31(-k) = 8}，則此形式已經有點像是extended Euclidean可以處理的對象了。 然而，gcd(17,31)≠8{\text{gcd}(17, 31) \ne 8}，這個式子無法直接求解。此路不通。

根據前一小節舉例所得成果，已知31⋅(−6)+17⋅11=1{31\cdot (-6) + 17\cdot 11 = 1}。重新寫成同餘式，則：

17⋅11≡1(mod 31)17 \cdot 11 \equiv 1( \text{mod } 31 )

根據同餘保持基本運算的特性，我們可以再度重寫同餘方程式（兩邊同乘）：

17⋅8⋅11≡8(mod 31)17\cdot 8\cdot 11 \equiv 8( \text{mod }31 )

故可以解得x≡88{x \equiv 88}，取其最小正整數解x=26{x = 26}。■\blacksquare

Modular Multiplicative Inverse#

對於一數aa，若且唯若aa與mm互質，其模反元素a−1a^{-1}存在。定義如下：

gcd(a,m)=1⟺a−1:a⋅a−1≡1 (mod m).\text{gcd}(a, m) = 1\Longleftrightarrow a^{-1}: a\cdot a^{-1} \equiv 1 \,( \text{mod }m ).

由上可知反元素與所討論的域Zn\mathbb{Z}_{n}有關。

Proof by Bezout’s Identity#

設d=gcd(a,m){d = \text{gcd}(a,m)}。根據Bezout’s identity，若d=1d = 1，則存在x,yx,y使得

a⋅x+m⋅y=1,a\cdot x + m \cdot y = 1,

因為以mm為模，可以重寫為

a⋅x≡1 (mod m).a\cdot x \equiv 1 \,( \text{mod }m ) .

使用extended Euclidean algorithm便可求得xx，而依據定義，xx即為aa的乘法反元素。 若d≠1d\ne 1，該數aa不互質模mm，則Bezout’s identity不成立，a−1a^{-1}不存在。

Fermat’s Little Theorem#

Let pp be a prime. Then

∀a∈Z,gcd(a,p)=1  ⟹  ap−1≡1 (mod p).\forall a \in \mathbb{Z}, \text{gcd}(a, p) = 1 \implies a^{p - 1} \equiv 1 \ ( \text{mod } p ) .

Example p=3,a=5{p= 3, a = 5} 依照費馬小定理，可得53−1=25≡1 (mod 3){5^{3 - 1} = 25 \equiv 1\,( \text{mod } 3 )}。

Explanation with Abstract Algebra#

乘法群Zp∗{\mathbb{Z}_{p}}^{*}的階為p−1p-1，因此任意元素的p−1p-1次方當然會回到單位元1。

A Corollary#

ap≡a (mod p).a^{p} \equiv a \,( \text{mod } p ) .

從費馬小定理的原方程式開始：

  1. 如果aa與pp互質，則代表同餘式兩邊可以相乘aa
  2. 如果不互質，p∣ap|a，則ap≡0≡a (mod p){a^{p} \equiv 0 \equiv a \,( \text{mod } p )}

RSA#

Preprocessing#

  1. Choose 2 big prime numbers pp and qq.
  2. Choose a pair of numbers ee and dd such that
    1. d⋅e=1(mod (p−1)(q−1))d\cdot e = 1(\text{mod}\ (p - 1)(q-1)), when ee is public and dd is private.
  3. Announce (pq,e)(pq, e); keep (p,q,d)(p, q, d).

Encryption and Decryption#

Encrypting message mm as code cc:

c≡me(mod pq), m<pq,c<pq.c \equiv m^{e} (\text{mod}\ pq),\ m< pq, c < pq.

Decrypting cc as mm:

m≡cd(mod pq).m \equiv c^{d} (\text{mod}\ pq).

Verification#

We set a symbol for the modulo:

r:=(p−1)(q−1);r := (p-1)(q - 1);

also, for the product of two big primes:

n:=p⋅q,n:= p\cdot q,

then we can describe the decrypting equations as m≡cd(mod n)m \equiv c^{d}(\text{mod}\ n).

For the convenience of the proof, we set an arbitary number kk such that

e⋅d≡1(mod r)  ⟹  r∣(e⋅d−1)  ⟹  ed=1+kr.e \cdot d \equiv 1 (\text{mod}\ r) \implies r | (e\cdot d - 1) \implies ed = 1 + kr.

So that according to the proccess of encryption and decryption, we can say that

cd≡(me)d≡m(e⋅d)≡m1+kr(mod n),c^{d} \equiv (m^{e})^{d} \equiv m^{(e\cdot d)} \equiv m^{1 + kr} (\text{mod}\ n),

and in order to prove that this process really lead us to transfer the correct message, we need to check if

cd≡med≡m1+kr≡m(mod n).c^{d} \equiv m^{ed} \equiv m^{1+kr} \equiv m (\text{mod}\ n).

將式子重新整理，得：

m⋅mk(p−1)(q−1)≡m (mod pq)m\cdot m^{k(p-1)(q - 1)} \equiv m \,( \text{mod } pq )

根據同餘保持基本運算的特性，兩邊同除mm：

mk(p−1)(q−1)≡1 (mod pq)m^{k(p - 1)(q - 1)} \equiv 1 \,( \text{mod }pq )mk(p−1)(q−1)≡1  (mod pq)m^{k(p - 1)(q - 1)} \equiv 1\ \,( \text{mod } pq )

Verification Practice#

如果縮減模，得(mk(q−1))p−1≡1 (mod p){(m^{k(q - 1)})^{p - 1} \equiv 1 \,( \text{mod } p )}，則依照費馬小定理便可得解。 但是gcd(m,p)=?1{\text{gcd}(m,p) \underset{?}{=} 1}，條件沒有說。此路不通。

分項討論

  • Case 1: gcd(m,p)=1∧gcd(m,q)=1{\text{gcd}(m,p) = 1 \land \text{gcd}(m, q) = 1}
  • Case 2: gcd(m,p)≠1∨‾gcd(m,q)≠1{\text{gcd}(m, p) \ne 1 \underline{\lor} \text{gcd}(m, q) \ne 1}

gcd(m,p)≠1∧gcd(m,q)≠1{\text{gcd}(m,p) \ne 1 \land \text{gcd}(m, q) \ne 1}必然不成立： 如果成立，則pq∣m{pq | m}，存在正整數k′k'使得m=kpq{m = kpq}（因為m>0m > 0）。 但RSA的前提已經表明m<pq{m < pq}，故不成立。

Case 1 根據費馬定理，

mp−1≡1 (mod p)∧mq−1≡1 (mod q)m^{p - 1} \equiv 1 \,( \text{mod } p ) \land m^{q - 1} \equiv 1 \,( \text{mod } q )

則依基本運算可輕易得mk(p−1)(q−1)≡1 (mod pq){m^{k(p-1)(q-1)} \equiv 1 \,( \text{mod } pq )}

Case 2 先以pp討論： 已知m,pm,p不互質，則依照Case 2的假設，gcd(m,q)=1{\text{gcd}(m,q) = 1}（或者m=0m=0，不討論）。

因為mm為pp的倍數，則mm的任意乘冪皆為pp的倍數，即

m1+k(p−1)(q−1)≡m (mod p),m^{1 + k (p - 1)(q - 1)} \equiv m \,( \text{mod } p ),

則兩者同餘，m≡mk(p−1)(q−1) (mod p){m \equiv m^{k(p - 1)(q - 1)} \,( \text{mod } p )}。

又依據費馬定理，

mq−1≡1 (mod q)m^{q - 1} \equiv 1 \,( \text{mod } q )

則可推知

mk(p−1)(q−1)≡1 (mod q).{m^{k(p-1)(q-1)} \equiv 1 \,( \text{mod } q )}.

兩邊相乘mm即得m1+k(p−1)(q−1)≡m (mod q){m^{1 + k(p - 1)(q - 1)} \equiv m\,( \text{mod } q )}。

統整得

{m1+k(p−1)(q−1)≡m (mod p)m1+k(p−1)(q−1)≡m (mod q)  ⟹  m1+k(p−1)(q−1)≡m (mod pq).\left\{\begin{aligned} & m^{1 + k(p - 1)(q - 1)} \equiv m \,( \text{mod } p ) \\ & m^{1 + k(p - 1)(q-1)} \equiv m \,( \text{mod } q ) \end{aligned}\right. \implies m^{1 + k(p - 1)(q - 1)} \equiv m \,( \text{mod } pq ) .

故得證 ■\blacksquare

Chinese Remainder Theorem#

今有比1大且兩兩互質的正整數m1,m2,m3,…mn{m_{1},m_{2},m_{3},\dots m_{n}}與任意整數a1,a2,a3,…,an{a_{1},a_{2},a_{3},\dots,a_{n}}。則聯立同餘方程組

∀i∈Nn x≡ai (mod mi)\forall i \in \mathbb{N}_{n}\ x \equiv a_{i} \,( \text{mod } m_{i} )

模m1⋅m2⋅(… )⋅mn{m_{1}\cdot m_{2}\cdot (\dots) \cdot m_{n}}時有唯一解

x=∑i=1nai⋅yi⋅Mi,x = \sum ^{n}_{i = 1} a_{i} \cdot y_{i} \cdot M_{i},

其中yiy_{i}為Mi=mmi{M_{i} = \frac{m}{m_{i}}}的模反元素(Mi)−1{(M_{i})^{-1}}。 白話翻譯： 該總和式，在模所有同餘模相乘時有唯一解；而y_i則是在該行的模m_i，取M_i的逆元。

Proposition: Modulo Factorization#

對於兩個互質的模m1,m2m_{1}, m_{2}：

  1. 同餘方程{x≡a1 (mod m1)x≡a2 (mod m2)\left\{\begin{aligned}x\equiv a_{1} \,( \text{mod }m_{1} )\\ x\equiv a_{2} \,( \text{mod } m_{2} )\end{aligned}\right.有解
  2. 任兩解都會同餘模m1⋅m2m_{1} \cdot m_{2}。

或者說，對於整數環Zm1⋅m2\mathbb{Z}_{m_{1}\cdot m_{2}}會有唯一解。

Proof#

If t≡m1−1(a2−a1) (mod m2),  then  x=a1+m1t is such a solution. ■\text{If}\ t \equiv m_{1}^{-1}(a_{2} - a_{1}) \,( \text{mod }m_{2} ) ,\ \ \text{then} \ \ x = a_{1} + m_{1} t\ \text{is such a solution.}\ \blacksquare

Uniqueness Proof#

假設有兩數x1,x2x_{1},x_{2}均為同餘方程式之解。則對於所有方程式都存在商數ri,ri′r_{i}, r'_{i}使得

x1=ri⋅mi+ai   and   x2=ri′⋅mi+aix_{1} = r_{i}\cdot m_{i} + a_{i} \ \ \ \text{and}\ \ \ x_{2} = r'_{i} \cdot m_{i} + a_{i}

兩數相減得x1−x2=(ri−ri′)⋅mi{x_{1} - x_{2} = (r_{i} - r'_{i})\cdot m_{i}}，則mi∣(x1−x2){m_{i} | (x_{1} - x_{2})}，即

x1≡x2 (mod m1⋅m2⋅(… )⋅mn),x_{1} \equiv x_{2} \,( \text{mod } m_{1} \cdot m_{2} \cdot (\dots)\cdot m_{n} ),

故知兩數模m1⋅m2⋅(… )⋅mn{m_{1}\cdot m_{2}\cdot (\dots)\cdot m_{n}}時有唯一解 ■\blacksquare

Proof of C.R.T.#

設m=m1⋅m2⋅(… )⋅mn{m = m_{1} \cdot m_{2} \cdot (\dots) \cdot m_{n}}，並設Mi=mmiM_{i} = \frac{m}{m_{i}}。

MiM_{i}的語意為「除了mi{m_{i}}以外的所有模」

因為mim_{i}兩兩互質，對於任意k≠ik \ne i，gcd(mk,mi)=1{\text{gcd}(m_{k}, m_{i}) = 1}，據此得

gcd(Mi,mi)=1.\text{gcd}(M_{i}, m_{i}) = 1.

MiM_{i}與mim_{i}互質

則依模反元素的定義，存在yiy_{i}使得

Mi⋅yi≡1 (mod mi),M_{i} \cdot y_{i} \equiv 1 \,( \text{mod } m_{i} ) ,

或寫作yi=Mi−1{y_{i} = {M_{i}}^{-1}}。 假設x=∑i=1nai⋅yi⋅Mi{x = \sum ^{n}_{i = 1}a_{i}\cdot y_{i} \cdot M_{i}}為解。 根據定義可知，對於任意j≠i{j \ne i}，MjM_{j}均可被mi{m_{i}}整除，即

Mj≡0 (mod mi).M_{j} \equiv 0 \,( \text{mod }m_{i} ).

故對於所有ii，

x≡ai⋅yi⋅Mi≡ai (mod mi)x \equiv a_{i} \cdot y_{i} \cdot M_{i} \equiv a_{i} \,( \text{mod } m_{i} )

均成立，符合方程組之敘述，故假說成立 ■\blacksquare

Mj=0M_{j}=0的說明旨在提示xx的其他所有加法項都會「消去」，只剩下第ii項。

02 Modular Arithmetics
https://blade520.com/posts/discrete-mathematics/ch2-modular-arithmetics/
作者
Blade/磯江
發佈於
2025-04-10
許可協議
CC BY-NC-SA 4.0
05 Counting
03 Mathematical Induction
© 2026 Blade/磯江. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari