Re: [代數] φ(d)=n

[cuttlefish (無聊ing ><^> .o O)]

※ 引述《IminXD (Encore LaLa)》之銘言：
: 一題子群部分的相關題目..
: Let n € Z+. Then Σ    φ(d)=n .
:       ↑           (d|n)
:      屬於
: 要證明這件事情..
: 題目就不太懂內含了，更不知道該怎麼證...囧
改一下

A={(d,a)| d|n且1<=a<=d, gcd(a,d)=1}

then f: A -> N={1,2,....,n}

f(d,a)=(n/d)*a

對於每個m屬於N f(n/g,m/g)=m , where g=gcd(n,m) 所以f onto

f(d',a')=f(d,a) then d'a=da' 此時因gcd(a,d)=1 所以d|d'

同理 d'|d so d=d' then a=a' 所以f 1-1

so|A|=|N|=n

其中|A|=Σφ(d) 所以得證
        d|n




--
 ^^
('') ~我是可愛的兔子


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.40.219.155
※ 編輯: cuttlefish      來自: 114.40.219.155       (11/08 01:34)
→ cuttlefish  :結果好像跟推文一樣 這樣有點多餘了XD
推 WINDHEAD    :用一句話搞定：將1/n~n/n這n個數唯一寫成最簡分數。