iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 14
2
自我挑戰組

計算機概論X30天系列 第 14

Day 14:[離散數學]同餘(Mod)是什麼?

閱讀前,建議可以參考Day1:閱讀指南&為何選擇這個題目?

▌挑戰簡介

  • 題目:計算機概論X30天

  • 挑戰內容:連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程,還有自己學習程式的心得體悟。

  • 本篇性質:

    • 適合的人:對密碼學有興趣的人,因為模數運算(mod)是加密算法、密碼學很常用的東西
    • 說明:對於只是單純想寫程式的人(像是寫網頁),不懂mode真的沒關係,不要被嚇到了XD

▌心得

最近學校離散數學課程,上到「同餘」(Mod)的概念,我內心覺得很矇逼。心想「學這個到底要做什麼?」「我知道A數跟那個B同餘可以幹嘛?」

原來,Mod的概念很常用在密碼學上(像是RSA加密、公鑰匙、私鑰匙),感覺就很酷是吧!
而要理解這些東西,會需要有基礎mod的概念。
因此本篇我要來介紹Mod,期望在之後章節能介紹——費馬小定理、中國餘式定理,還有RSA加密。

▌什麼是Mod

  • mod簡單來說,就是指「同餘」

比如說:

4 除以 3 餘 1
10 除以 3 餘 1
我們就可以會說 4≡10 (mod 3) ,意思是「4和10在除以3的情況下是「同餘的」」

其他例子:

5 除以 2 餘 1
7 除以 2 餘 1

因此 5≡7 (mod 2)

▌為什麼需要Mod?

「你沒事求餘數做什麼?」、「知道同餘可以幹嘛啦?」

我完全明白,因為這完全就是我剛學mod的心聲!

Mod的究竟可以幹什麼?

Mod的存在的最重要意義,其實是幫——數據做分類

比如說,如果把所有自然數都除以7,你可以想像只會有7種可能

  • 要麼被7整除 N ≡ 0 (mod 7)
  • 要麼被7除,餘1 N ≡ 1 (mod 7)
  • 要麼被7除,餘2 N ≡ 2 (mod 7)
  • 要麼被7除,餘3 N ≡ 3 (mod 7)
  • 要麼被7除,餘4 N ≡ 4 (mod 7)
  • 要麼被7除,餘5 N ≡ 5 (mod 7)
  • 要麼被7除,餘6 N ≡ 6 (mod 7)

所有的自然數在mod 7的情況下,就可以被分成了七組

這有什麼好處?

這意味著,不管是遇到一個多怪數字,像是131231312313131,你都可以把他進行分類(因此你對這個數字不是全然陌生的)

因為至少你知道,在mod7的情況下,他肯定可以被表示為七種之一

實際上 131231312313131 ≡ 2 mod 7

我們可以把一個複雜的大數,用一個較小的數字替換,這整個就簡化了運算的複雜性。

Mod的存在就是為了做分類,讓我們可以用「較小的數字」處理一些平時「很難處理」的數字

▌Mod 的性質

了解Mod的基礎後,還要來在認識3個Mod的性質,之後才能看到mod的妙處

1.因數定理(我自己發明的)

假設

a ≡ b (mod k)

k | a-b (意思是k是a-b的因數,k可以整除a-b)

有人可以告訴我這個定理有什麼名字嗎?

為什麼呢?

a ≡ b (mod k)

對於a,b,我們可以把a b改寫如下

a = kq+r
b = kp+r

q、p是什麼不重要,不要管他,反正就是某個整數
重點是:因為a、b同餘,所以我們知道a b一定會有一個共同的餘數r。

那麼

a = kq+r
b = kp+r
a-b = k(q-p)+(r-r)
a-b = k(q-p) 有沒有發現,r就被消掉了!

因此 k | a-b

我們推論出:

a ≡ b (mod k) <=> k | a-b

這個性質之後會用到

2.同餘的相加性質

如果
a = b (mod k)
c = d (mod k)

a+c = b+d (mod k)

為什麼呢?

a = b (mod k)可以寫成 根據上面證明的因數定理(這名字我發明的)a ≡ b (mod k) <=> k | a-b
(1)k|a-b

c = d (mod k)可以寫成 根據上面證明的因數定理(這名字我發明的)a ≡ b (mod k) <=> k | a-b
(2)k|c-d

那麼(1)(2)相加,可以得到(因為a-b可以被k整除,c-d也可以被k整除,他們相加當然也可以被k整除)
k|(a-b)+(c-d)

整理一下,就變成
k|(a+c)-(b+d)
那又可以寫成 根據上面證明的因數定理(這名字我發明的)a ≡ b (mod k) <=> k | a-b

a+c = b+d (mod k)

3.同餘的相乘性質

如果
a = b (mod k)
c = d (mod k)

aXc = bXd (mod k)

為什麼呢?

a = b (mod k)可以寫成 根據上面(1)證明的因數定理a ≡ b (mod k) <=> k | a-b
k|a-b
則乘上c也成立,變成
K|c(a-b) ---- (1)

c = d (mod k)可以寫成 根據上面(1)證明的因數定理a ≡ b (mod k) <=> k | a-b
k|c-d
則乘上b也成立,變成
K|b(c-d) ---- (2)

上面(1)(2)相加

K|c(a-b)+b(c-d)
k|ac-bc+bc-bd
k|ac-bd
因此,根據根據上面(1)證明的因數定理
ac = bd (mod k)

同餘相乘的性質延伸

上面的相乘同餘定理,可以在繼續延伸兩個性質

(1)平方同餘定理

如果
a = b (mod k)

a^n=b^n (mod k)

因為
a = b (mod k)
a = b (mod k)
可以相乘
那麼a^2=b^2 (mod k)
繼續推演,就可以得到 a^n=b^n (mod k)

(2)倍數同餘定理

如果
a = b (mod k)

ma=mb (mod k)

因為當 m = m (mod k) 一定成立
那麼ma=mb (mod k) 也是理所當然的
繼續推演,就可以得到 ma=mb (mod k)

現在我們有三個武器,終於可以來做點事了

  • 同餘的因數定理:a ≡ b (mod k) <=> k | a-b
  • 同餘的加法性質:a ≡ b (mod k) & c ≡ d (mod k) <=> a+c = b+d (mod k)
  • 同餘的相乘性質:a ≡ b (mod k) & c ≡ d (mod k) <=> ac = bd (mod k)
    • 次方公式 a ≡ b (mod k) <=> a^n ≡ b^n (mod k)
    • 倍方公式 a ≡ b (mod k) <=> am ≡ bm (mod k)

例題(1)

15^8001 X 22^4781 X 11^3 除以7的餘數為多少

.....這鬼知道喔,這大到連電腦都算不出來好嗎

沒關係,我們可以用mod

首先,我們知道
15 ≡ 1 (mod 7) 我用大腦想出來的
22 ≡ 1 (mod 7) 我用大腦想出來的
11 ≡ 4 (mod 7) 這我用大腦想出來的

15^8001 ≡ 1^8001 (mod 7) 根據上面同餘的相乘性質的次方公式
22^4781 ≡ 1^4781 (mod 7) 根據上面同餘的相乘性質的次方公式
11^3 ≡ 4^3 (mod 7) 根據上面同餘的相乘性質的次方公式

然後上面三條可以相乘 (根據上面同餘的相乘性質)

15^8001 X 22^4781 X 11^11 ≡ 1^8001 X 1^4781 X 4^3 (mod 7)
15^8001 X 22^4781 X 11^11 ≡ 64 (mod 7)
然後因為 64 ≡ 1 (mod 7)

好...好累,對,所以...
15^8001 X 22^4781 X 11^3 ≡ 1 (mod 7)

所以餘1

有沒有很厲害!我竟然算得出來
還有我竟然可以把 15^8001 這種鬼數字
化解成
15^8001 ≡ 1 (mod 7) 的形式!

這就是 數學的力量!

mod的意義,就是把複雜的數字,用簡單的方式表達

例題(2)

4793316+7890323 除以7 會餘多少?(夭壽喔,不想算4793316+7890323)

假設我們知道下面

4793316 ≡ 3 (mod 7)
7890323 ≡ 0 (mod 7)

那根據同餘的加法性質,可以得出

4793316+7890323 ≡ 3(mod 7)

我們根本不用知道4793316+7890323是多少,也可以算出它會餘3

mod的意義,就是即使你根本不知道那複雜的數字是多少,也可以用簡單的方式算出答案

總結

  • Mod的存在就是為了幫數字做分類,讓我能更好的處理大數問題

  • Mod的好處是讓我們可以用「簡單的數字」方便處理「很難處理」的大數

  • 希望之後的章節我有機會用mod解釋一些實用性的算法wow

  • 同餘的因數定理:a ≡ b (mod k) <=> k | a-b

  • 同餘的加法性質:a ≡ b (mod k) & c ≡ d (mod k) <=> a+c = b+d (mod k)

  • 同餘的相乘性質:a ≡ b (mod k) & c ≡ d (mod k) <=> ac = bd (mod k)

    • a ≡ b (mod k) <=> a^n ≡ b^n (mod k)
    • a ≡ b (mod k) <=> am ≡ bm (mod k)

上一篇
Day13:[計算機概論]Toy Machine:用組合語言寫加法
下一篇
Day 15:[離散數學] 中國餘式定理
系列文
計算機概論X30天30
0
wssun
iT邦見習生 ‧ 2018-10-30 09:42:04

寫得好清楚,讓人一目瞭然,感謝您

Nissen iT邦新手 5 級 ‧ 2018-10-30 13:50:47 檢舉

謝謝你的鼓勵!!很開心:)

0
jeffchou11
iT邦見習生 ‧ 2019-08-09 12:33:02

寫的太好了,你可以來教離散數學啦

0
jeffchou11
iT邦見習生 ‧ 2019-08-09 12:33:03

寫的太好了,你可以來教離散數學啦

0
kenlo29
iT邦新手 5 級 ‧ 2020-05-07 09:59:53

感謝分享!十分實用,簡潔易懂!
Google 了半天都沒找到能看懂的文章, 現在明白了!謝謝~
/images/emoticon/emoticon07.gif

我要留言

立即登入留言