閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

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

• 本篇性質：

  • 適合的人：對密碼學、大數處理有興趣的人，因為模數運算（mod）、費馬小定理很常拿來用
  • 本篇是離散數學一題很難的作業，他很好的說明'mod和費馬小定理如何處理超複雜數據`
  • 一定要讀過Day 14:[離散數學]同餘（Mod）是什麼？

▌會用到的性質

一定要至少明白下面mod的性質，不然無法理解本篇內容！！

- 同餘的因數定理：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)
- 費馬小定理：a^(p-1)≡1  mod P  // 如果 gcd(a,p)=1 且 p 為質數

▌超難問題

題目是：23^4800017 除以35餘數是多少？

我覺得這題很難，但是他很好的說明了mod處理大數的優勢。

23^4800017 實在太大了，根本不可能直接算出來

直接使用費馬小定理

沒關係，這時候也可以使用費馬小定理！

23^34≡1 mod 35

這是錯的，因為不是質數，所以不能直接使用費馬小定理。

正確解法

我們只能先把35拆成7,5兩個質數，想辦法用他們處理問題

23^6 ≡1 mod 7  //根據費馬小定理
23^4 ≡1 mod 5  //根據費馬小定理
23^12 ≡1 mod 7  //同餘的相乘性質的次方性質
23^12 ≡1 mod 5  //同餘的相乘性質的次方性質
6X23^12 ≡6X1 mod 7  //這個轉換很精妙，請自行體悟一下
6X23^12 ≡6X1 mod 5  //這個轉換很精妙，請自行體悟一下
6X23^12 ≡-1 mod 7
6X23^12 ≡ 1 mod 5 
7|6X23^12+1 // 同餘的因數定理
5|6X23^12-1  //同餘的因數定理

35|(6X23^12+1)(6X23^12-1)
35|(6^2X23^24)-1
6^2X23^24 ≡ 1 mod 35 //同餘的因數定理
36 X 23^24 ≡1 mod 35 
23^24 ≡1 mod 35  //因為 36 ≡1 mod 35 因此可以消掉
23^4800017  ≡ (23^24)2000000 X 23^17   mod 35
23^17  mod 35  //因為 23^24 ≡1 mod 35 因此(23^24)2000000 可以消掉

太好了，千辛萬苦終於把23^4800017 mod 35 變成 23^17 mod 35 這個較小的問題

23^17 mod 35 
23^2 ≡  4  mod 35  //這條要自己算
(23^2)8 X 23  ≡  4^8 X 23  mod 35 
4^4 ≡  11  mod 35 //這條要自己算
4^8 X 23   ≡ 11^2 X23 mod 35 
11^2 X23 ≡ 18 mod 35 

因此，23^4800017 除以35餘數是18。

在這題當中，就是不斷的代換，把大數變小數，化繁為簡

▌總結

Mod運算、費馬小定理在處理很大的數據有它的妙用所在
這題我算了一個早上ＱＱ