<style> .note{ color:green } .red{ color:red } </style> ## :speech_balloon: 介紹 --- 由於餘數題目在台聯大與台綜大考古題出現過，對於餘數不熟悉的同學常以暴力破解法的方式算餘數，即使知道考題相關概念卻得花費大量時間進行計算，此篇將引入一些離散數學計算技巧節省計算時間。 * 適合閱讀的人 * 計算機概論有一定基礎 * 想了解mod題型運算 * 文章分類 (參考) * 難度：★★ * 重要程度：★★★ * 出現時機：RSA加密演算法 ## :book: 內容 --- #### **1. Mod (同餘)** \begin{align} &(a \equiv b\mod{k})\;{\small \color{green}{//\;(a\mod{k})\;與\;(b\mod{k}) 有相同餘數}}\\\\ \end{align} >**example:** >>( 11 mod 5 ) = 1 <span class="note">// 11÷5=2...</span><span class="red">1</span> >>( 1 mod 5 ) = 1 <span class="note">// 1÷5=0...</span><span class="red">1</span> >>故表示為 11 ≡ 1 mod 5 #### **2. Mod 運算性質** * **相減因數性質** \begin{align} if\;\;(a\equiv b\mod{k})\;\Rightarrow\;k\;|\;a-b\;\;{\small \color{green}{//k為(a-b)因數}} \end{align} :::spoiler 原理(參考) \begin{align} &{\large let\;a=kq+\color{red}{r},\;b=kp+\color{red}{r}}\;\\ &{\large then\;a-b=kq-kp=k(q-p)} \color{green}{//餘數r消除，故k可以整除(a-b)} \end{align} ::: <br> * **同餘相加性質** \begin{align} &if\;(a \equiv b\mod{k})\;and\;(c\equiv d\mod{k})\;\\ &then\;(a+c \equiv b+d\mod{k}) \end{align} :::spoiler 原理(參考) \begin{align} &if\;(a \equiv b\mod{k})\;and\;(c\equiv d\mod{k})\;\\ &then\left\{ \begin{matrix} k | (a-b)\\ k | (c-d) \end{matrix} \right.\\ &\because\;(a-b)=n_1k\;and\;(c-d)=n_2k\Rightarrow(a-b)+(c-d)=(n_1+n_2)k\\ &\therefore\;k\;|\;(a-b)+(c-d)\Rightarrow k\;|\;(a+c)-(b+d) {\normalsize \color{green}{\;//交換bc的位置}} \end{align} ::: <br> * **同餘相乘性質** \begin{align} &if\;(a\equiv b\mod{k})\;and\;(c\equiv d\mod{k})\;\\ &then\;(ac \equiv bd\mod{k}) \end{align} :::spoiler 原理(參考) \begin{align} &if\;(a\equiv b\mod{k})\;and\;(c\equiv d\mod{k})\;\\ &then\left\{ \begin{matrix} k | (a-b)\;\textbf{--}(1)\\ k | (c-d)\;\textbf{--}(2) \end{matrix} \right. (\;(1)\;multiply\;by\;\textbf{c}\;and\;(2)\;multiply\;by\;\textbf{b})\\ &\Rightarrow\left\{ \begin{matrix} k | c(a-b)\;\textbf{--}(1)\\ k | b(c-d)\;\textbf{--}(2) \end{matrix} \right. {\normalsize \color{green}{\;//k已經是(a-b)、(c-d)因數，所以乘上任意整數因數結論不變}}\\ &\Rightarrow k\;|\;c(a-b)+b(c-d){\normalsize \color{green}{\;//兩數相加依舊是k的倍數}}\\ &\Rightarrow k\;|\;ac-bc+bc-bd\\ &\Rightarrow k\;|\;ac-bd{\normalsize \color{green}{\;//相減因數性質可知}}\\ &\Rightarrow (ac \equiv bd\mod{k}) \end{align} ::: <br> * **平方同餘性質** \begin{align} &if\;(a\equiv b\mod{k})\Rightarrow (a^n \equiv b^n\mod{k}) \end{align} * **倍數同餘性質** \begin{align} &if\;(a\equiv b\mod{k})\Rightarrow (ma \equiv mb\mod{k}) \end{align} :::success 恭喜到這裡你已經了解大概的餘數性質 現在請先思考為什麼**平方同餘性質**與**倍數同餘性質**會**成立**呢? 是運用什麼性質推理? :::spoiler 解答 ***同餘相乘性質*** ::: #### **3. ==費馬小定理(Fermat's Little Theorem)==<span class="red">(重要)</span>** \begin{align} &if\;\textbf{a}\in \mathbb Z\;and\;\textbf{p}\;is\;a\;prime \;number\;{\small \color{green}{\;//若a是整數且p是質數}}\\ &and\;a,p\;coprime\;{\small \color{green}{\;//a、p互質}}\\ &\Rightarrow\;(a^{p-1} \equiv 1\mod{p}) \end{align} #### **4. ==中國剩餘定理(Chinese Remainder Theorem)(最小正整數解)==<span class="red">(重要)</span>** \begin{align} &Given\;\left\{ \begin{matrix} x \equiv a_1\mod{m_1}\\ x \equiv a_2\mod{m_2}\\ ...\\ x \equiv a_n\mod{m_n} \end{matrix} \right.\;and\;x \in \mathbb Z\\ &if\;m_1,m_2,...,m_n\;are\;pairwise\;coprime{\small \color{green}{\;//若m_1,m_2,...,m_n兩兩互質}}\\ &then\;m=m_1×m_2×...×m_n\;,\;\exists! x\in\;{[0,m)}{\small \color{green}{\;//則x 有唯一解在(0,1,....m-1中）}} \end{align} <br> :::warning :bulb: 建議可以從例題去理解定義，這樣比較好理解 ::: >**example:** >>我們知道(34 mod 5) = 4與(34 mod 7) = 6，假設我們不知道34該怎麼求得呢?我們來看以下例題。 >> >>**<span style="color:blue"><偷吃步法(不用複雜數學技巧，因考試通常不會用到太多方程組)></span>** >>\begin{align} >>&已知\;\left\{ \begin{matrix} x \equiv 4\mod{5}\\ x \equiv 6\mod{7} \end{matrix} \right.\\ &依中國剩餘定理可知\\ &\;m=5×7=35,\exists! x\in\;[0,35)\\ &{\small \color{red}{注意：x有無限多的可能，但我們限制在[0,35)中找符合方程式的解，所以x在這個範圍內只有一個，\\也就是說找x最小正整數解}}\\ &{\small \color{red}{想法：既然我們知道一定有唯一的x在[0,35)，那我們就挑最大質數7開始猜}}\\ &符合(x \equiv 6\mod{7})的數字有13、20、27、34，其中\color{red}{13、20、27不符合}(x \equiv 4\mod{5})\\ &所以x=34 >>\end{align} :::warning :bulb: 解題技巧就是"猜數字"，利用最大的質數縮小猜的範圍 ::: ## Question 1 --- \begin{split} &Find\;\;(23^{4800017}\mod{35})\;=?\\\\ <sol>\\ &\because 35=5*7\;and\;5,7\;coprime\;{\small \color {green}{//拆成兩個質數取mod}}\\ &\Rightarrow \left\{ \begin{matrix} 23 \equiv 2\mod{7}\\ 23 \equiv 3\mod{5} \end{matrix} \right.\\ &\Rightarrow\left\{ \begin{matrix} 23^{4800017} \equiv 2^{4800017}\mod{7}\\ 23^{4800017} \equiv 3^{4800017}\mod{5} \end{matrix} \right.{\small \color {green}{//平方同餘性質}}\\\\ &By\;Fermat's\;little\;theorem\\ &\left\{ \begin{matrix} 2^{6} \equiv 1\mod{7}\\ 3^4 \equiv 1\mod{5} \end{matrix} \right.\\ &\therefore \left\{ \begin{matrix} 23^{4800017} \equiv 2^{4800017} \equiv 2^{6(800002)}*2^{5} \equiv 2^5 \equiv 4\mod{7} \;{\small \color {green}{//相乘同餘性質}}\\ 23^{4800017} \equiv 3^{4800017} \equiv 3^{4(1200004)}*3 \equiv 3\mod{5} \;{\small \color {green}{//相乘同餘性質}} \end{matrix} \right.\\\\ &By\;Chinese\;Remainder\;Theorem\\ &\left\{ \begin{matrix} 23^{4800017} \equiv x \equiv 4\mod{7}\\ 23^{4800017} \equiv x \equiv 3\mod{5} \end{matrix} \right.\;,\exists!\;x\in[0,35)\;and\;x\in\mathbb Z\\ &\Rightarrow \left\{ \begin{matrix} 7\;|\;x-4\;\textbf{--(1)}\\ 5\;|\;x-3\;\textbf{--(2)} \end{matrix} \right.\\ & Select\;7\;and\;\;Guess\;11,18,25,32\;By(1)\\ & \because\;11,25,32\;not\;satisfy\;equation\;(2)\\ &\therefore x = 18_\color{red}{\#} \end{split} ## 考古題 --- ### **台聯大107第15題** ![台聯大107第15題](https://hackmd.io/_uploads/rkPHWgNjh.png) ![](https://hackmd.io/_uploads/HyVWeQUsh.jpg) ### **台綜大108第15題(mod基本運用)** $(15)\;What\;is\;the\;result\;of\;1234567^{890}\;taking\;modulo\;7\;?$ ![解法](https://hackmd.io/_uploads/ByScc54in.png) <br> ## :link: 參考 --- * [台大-計算機概論OCW-Networking and the Internet](https://www.youtube.com/watch?v=MoumhXZP0gA&list=PLil-R4o6jmGiDc1CC8PyBbasl8kR9r8Wr&index=9) * [中國餘式定理](https://ithelp.ithome.com.tw/articles/10205772) >[name=Sky] ###### tags: `考古題觀念補充`