[代數] φ(d)=n

[IminXD (Encore LaLa)]

一題子群部分的相關題目..


Let n € Z+. Then Σ    φ(d)=n .
      ↑           (d|n)
     屬於


要證明這件事情..

題目就不太懂內含了，更不知道該怎麼證...囧

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.189.64
推 sophialiege :印象中summation的suffix是d整除n
※ 編輯: IminXD          來自: 220.136.189.64       (11/07 21:40)
→ suhorng     :應該是 "|" 打錯成 "/" (?)
→ IminXD      :恩對；是d|n  感謝提醒=P
→ suhorng     :對於所有 i=1...n, 用 gcd(i, n) 來分類
→ suhorng     :對於與 n 的最大公因數為 k 的類, 也就是對於
→ suhorng     :gcd(i, n) = k 的所有i, 有 gcd(i/k, n/k)=1
→ suhorng     :也就是φ(n/k) 其中 k | n.
→ suhorng     :所有類的總個數是 Σ_(k|n) φ(n/k), 顯然等於 n
→ suhorng     :而 Σ_(k|n) φ(n/k) = Σ_(k|n) φ(k). 這樣.
→ suhorng     :補上上上行...我是指這樣的 i 共有 φ(n/k) 個
→ IminXD      :懂意思了，我在想想怎麼用數學式寫；  謝謝^^
推 jacky7987   :另一種證法 是先定義Euler-phi function
→ jacky7987   :有些書的定義是phi(n)={x|x^n=1, x^d≠1 for 1<=d<n}
→ jacky7987   :接著定義primitive zero of unity
→ jacky7987   :證明手法是 let x=e^{ikπ/n}
→ jacky7987   :證明x is pimitive of degree n <=> gcd(k,n)=1
→ jacky7987   :不對我打錯了= ="
→ jacky7987   :(請直接忽略上面的幾行XD)