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

▌挑戰簡介

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

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

• 本篇性質：要有基礎的mod（同餘）概念，請參考Day 14:[離散數學]同餘（Mod）是什麼？

▌歐拉定理

歐拉定理定理是說

ab是二整數，且互質，也就是qcd(a,b)=1
則a^φ(b)≡1 (mod b)
其中φ(b)表示所有比b小且與b互質的正整數個數

比如說

3,5互質
3^φ(5)≡1 (mod 5) //φ(5)=4（比5小並互質的數包含1 2 3 4 ）
因此
3^4≡1 (mod 5)

▌歐拉定理可以幹嘛？

可以處理很大的數字！

比如說求7^222次方的個位數（當然不可能乘出來）

由於7^222個位數相當於 7^222 mod 10，且7和10互質

7^φ(10)≡1 (mod 10)  //φ(10)=4  （包含1,3,7,9）
7^4≡1 (mod 10) 
7^222≡(7^4)55X 7^2 ≡49 (mod10)
49 ≡ 9(mod10)

因此答案是9

▌其實這題也可以用費馬小定理來做

複習

費馬小定理：如果qcd(a,b)=1且b是質數
則a^(b-1)≡1 (mod b)

qcd(2,5)=1且5是質數
則2^(5-1)≡1 (mod 5) 

費馬小定理

對於7^222 (mod 10)
因為10不是質數，所以可以先拆成5,2得到下面

7^(5-1)≡1 (mod 5) 
7^(2-1)≡1 (mod 2) 

想辦法變成mod 10

7^(5-1)≡1 (mod 5)  => 7^4≡1 (mod 5)=> 5|7^4-1
7^(2-1)≡-1 (mod 2) => 7^1≡1 (mod 5)=> 7^4≡1^4 (mod 2)=> 7^4≡ -1 (mod 2)=>  2|7^4+1
得到
5|7^4-1
2|7^4+1
得到
10|7^8-1 => 7^8≡1 (mod 10)

因為7^222≡(7^8)27 X (7^6)

7^222≡(7^8)27 X (7^6) ≡ 1 X 7^6  (mod 10)
因為 7^2 ≡ 9 ≡ -1  (mod 10)
而7^6≡(7^2)3≡(-1)^3≡ -1≡ 9(mod 10)

因此答案是9 （累死我了）

▌總結

• 歐拉定理、費馬小定理兩者都可以處理大數字
• 歐拉定理：如果ab二整數互質，則a^φ(b)≡1 (mod b)
• 費馬小定理：如果ab二整數互質，且b是質數，則a^(b-1)≡1 (mod b)
• 感覺費馬小定理要求比較多，還是歐拉定理好用多了