[代數] φ(d)=n

看板Math作者 (Encore LaLa)時間14年前 (2011/11/07 21:35), 編輯推噓2(2推 0噓 16→)
留言18則, 4人參與, 最新討論串1/6 (看更多)
一題子群部分的相關題目.. Let n € Z+. Then Σ φ(d)=n . ↑ (d|n) 屬於 要證明這件事情.. 題目就不太懂內含了，更不知道該怎麼證...囧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.189.64
推
11/07 21:39, , 1F
印象中summation的suffix是d整除n
11/07 21:39, 1F
※ 編輯: IminXD 來自: 220.136.189.64 (11/07 21:40)
→
11/07 21:40, , 2F
應該是 "|" 打錯成 "/" (?)
11/07 21:40, 2F
→
11/07 21:40, , 3F
恩對；是d|n 感謝提醒=P
11/07 21:40, 3F
→
11/07 21:40, , 4F
對於所有 i=1...n, 用 gcd(i, n) 來分類
11/07 21:40, 4F
→
11/07 21:41, , 5F
對於與 n 的最大公因數為 k 的類, 也就是對於
11/07 21:41, 5F
→
11/07 21:41, , 6F
gcd(i, n) = k 的所有i, 有 gcd(i/k, n/k)=1
11/07 21:41, 6F
→
11/07 21:41, , 7F
也就是φ(n/k) 其中 k | n.
11/07 21:41, 7F
→
11/07 21:42, , 8F
所有類的總個數是 Σ_(k|n) φ(n/k), 顯然等於 n
11/07 21:42, 8F
→
11/07 21:42, , 9F
而 Σ_(k|n) φ(n/k) = Σ_(k|n) φ(k). 這樣.
11/07 21:42, 9F
→
11/07 21:43, , 10F
補上上上行...我是指這樣的 i 共有 φ(n/k) 個
11/07 21:43, 10F
→
11/07 21:52, , 11F
懂意思了，我在想想怎麼用數學式寫； 謝謝^^
11/07 21:52, 11F
推
11/07 21:54, , 12F
另一種證法 是先定義Euler-phi function
11/07 21:54, 12F
→
11/07 21:55, , 13F
有些書的定義是phi(n)={x|x^n=1, x^d≠1 for 1<=d<n}
11/07 21:55, 13F
→
11/07 21:56, , 14F
接著定義primitive zero of unity
11/07 21:56, 14F
→
11/07 21:58, , 15F
證明手法是 let x=e^{ikπ/n}
11/07 21:58, 15F
→
11/07 21:58, , 16F
證明x is pimitive of degree n <=> gcd(k,n)=1
11/07 21:58, 16F
→
11/07 22:00, , 17F
不對我打錯了= ="
11/07 22:00, 17F
→
11/07 22:00, , 18F
(請直接忽略上面的幾行XD)
11/07 22:00, 18F
‣ 更多 IminXD 的文章
文章代碼(AID): #1EjzwDzs (Math)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
代數
1
2
Re: [代數] φ(d)=n Re: φ(d)=n
yusd24
14年前, 11/07
完整討論串 (本文為第 1 之 6 篇)：
排序： 最新先 | 最舊先 | 留言數
代數
1
2
Re: [代數] φ(d)=n Re: φ(d)=n
yusd24
14年前, 11/07
代數
2
18
[代數] φ(d)=n φ(d)=n
IminXD
14年前, 11/07
在新視窗開啟完整討論串 (共6篇)
‣ 更多 IminXD 的文章
文章代碼(AID): #1EjzwDzs (Math)