# 何謂尤拉函數與尤拉定理? 請證明之。

### 前言
1.何謂mod?
>- mod簡單來說，就是指「同餘」
>- 如:
>5除以3餘1
11除以3餘1
我們就會說 5≡11 (mod 3)，意思是「5和11在除以3的情況下是「同餘的」」
>- Mod的存在的最重要意義是==數據分類==
>- mod 的性質
>>1.同餘的因數定理：a ≡ b (mod k) <=> k | a-b
>>pf:設a=ck+r, b=dk+r, 兩式相減得a-b=(c-d)k, 故a-b為k的倍數
>>
>>2.同餘的加法性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> a+c = b+d (mod k)
>>pf:由1知k | a-b , k | c-d , 而k | (a-b)+(c-d) = k|(a+c)-(b+d), 故由因數定理可知 ==(a+c) ≡ (b+d)==
>>
>>3.同餘的相乘性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> ac = bd (mod k)
pf: k | (a-b)c ; k | (c-d)b => k | (a-b)c + (c-d)b, k | ac-bc+bc-bd, k | ac-bd, 故==ac ≡ bd==

2.何謂費馬小定理?
>- IF gcd(a,p)=1，{ a∈N & ==p∈質數== }
>==a^(p-1)≡1== (mod p)
>左右兩邊同時乘以 a可得
>==a^p≡a== (mod p)

### 正文
- [ ] 何謂尤拉函數 Euler φ function?

>- 定義φ(n)：
>==n∈N==，φ(n)為==不大於n==且==與n互質==的自然數的個數
- [ ] 應用(1) 尤拉定理 :
>
> 尤拉定理實際上是費馬小定理的推廣
>
> 假若a與n互質，則(a^φ(n))-1可被n整除，即 ==a^φ(n)≡1== (mod n)
- [ ] 應用(2) 歐拉函數的值
> 設一數p可分解為p=a1^x1*a2^x2*a3^x3,其中a1,a2,a3為相異質因數，x1,x2,x3∈N,則
>>> φ( p )= p-(不與p互質的個數) = p - (p/a1 + p/a2 + p/a3) + p/a1a2 + p/a2a3 + p/a1a3 - p/a1a2a3 = ==p(1-1/a1)(p-1/a2)(p-1/a3)==
>>>