最簡分數有幾個???

Question

小於33的正整數ｎ中，使ｎ／33為最簡分數的ｎ有幾個？總和是多少？
【此題有比較簡單的算法嗎？】

若是小於45的正整數ｎ中，使ｎ／45為最簡分數的ｎ有幾個？總和是多少？
【這一題又要如何算呢？】

Answer 1

n = p1r1p2r2...pkrk小於n且與n互質的正整數個數=φ(n)=n*(1-1/p1)(1-1/p2)...(1-1/pk)其和=nφ(n)/2所以這題就是33=3*11φ(33) = 33*(1-1/3)(1-1/11) = (3-1)(11-1) = 20Σgcd(k,33)=1 k = 33*20/2 = 33045=32*5φ(45) = 45*(1-1/3)(1-1/5) = (9-6)(5-1) = 12Σgcd(k,45)=1 k = 45*12/2 = 270

Answer 2

33是3和11的倍數
就將3(共11個)
或11(共3個)的倍數消掉就好了
33-33/3-33/11+33/33
=33-11-3+1=20
答20個

附註:因為33被消去2次
所以要補一個回來
所以我最後才加33/33

至於總和
我想不到方法
只好一個個加起來了

Answer 3

小於ab的正整數ｎ中，使ｎ／ab為最簡分數的ｎ有幾個？總和是多少？
其中a,b是質數
n有幾個？(a-1)(b-1)個
n的總和？ab(a-1)(b-1)/2
推了好久才得到的公式，不難，但是蠻囉嗦的。
33=3*11
n有幾個？(3-1)(11-1)=20個
n的總和？3*11*(3-1)*(11-1)=330

2005-08-03 01:03:14 補充：
小風 ~~傲：
你少算到n=4了，所以共20個，總和326+4=330。

2005-08-03 17:14:55 補充：
hwp:
我哪有少除一個2，一開始我就有寫啦！
請大家看一下這題，
http://tw.knowledge.yahoo.com/question/?qid=1205072817615

Answer 4

就只有乖乖算吧
我絕得 沒什麼特殊的方法
而且 也不多阿 1.2.5.7.8.10.13.14.16.17.19.20.23.25.26.28.29.31.32
19個 總何326