作者lockheart (Special Thanks to Eason)
看板Math
標題Re: [數論] Euler function(n)=12, n為?
時間Fri Nov 25 23:06:35 2011
※ 引述《vity (逍遙盃-佛得)》之銘言：
: 題目:
: 給定Euler function(n)=12
: 求三種n?
令 n = Π(P_k)^a_k
則 12 = Π(p_k-1) ×(p_k)^(a_k-1)
因此可以透過 p_k-1|12 找出可能的蒙面人 p_k
候選人有2, 3, 5, 7, 13
還有一點可以注意, 如果a_k>1, 那p_k|12
因此會發現5, 7, 13這三個傢伙出場一次就得領便當了
何不早早送他們上路?
Case 1: n = 5 ×Π(P_k)^a_k
=> 12 = 4 ×Π(p_k-1)*(p_k)^(a_k-1)
=> 3 = Π(p_k-1)*(p_k)^(a_k-1) 這可能嗎?
Case 2: n = 7 ×Π(P_k)^a_k
=> 12 = 6 ×Π(p_k-1)*(p_k)^(a_k-1)
=> 2 = Π(p_k-1)*(p_k)^(a_k-1)
=> p_k-1|2 again => p_k = 2 or 3
到這邊可以注意到一點, 如果2只出現一次, 那他根本就是來亂的
所以到這邊就可以找到 n = 21 or 28 or 42
Case 3: n = 13 ×Π(P_k)^a_k
=> 12 = 12 ×Π(p_k-1)*(p_k)^(a_k-1)
=> 1 = Π(p_k-1)*(p_k)^(a_k-1)
差不多的狀況你會找到 n = 13 or 26
這些一次就上路的都討論完了,
剩下的就是跟閣下剛討論的狀況差不多
所以所有滿足的 n 應該就 13, 21, 26, 28, 36, 42 這樣吧
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.238.230
→ Sfly :how about 28? 11/26 09:20
Thank you so much!
推 vity :水辣 11/26 16:09
推 vity :不好意思 第二行的p_k-1 與a_k-1如何得出呢? 11/26 16:19
φ(n) = Π[1-(p_k)^-1] ×(p_k)^(a_k)
= Π[1-(p_k)^-1] ×(p_k) ×(p_k)^[(a_k)-1]
= Π[(p_k)-1] ×(p_k)^[(a_k)-1]
拿一個p_k給前面的用一下降
推 vity :可惡 我看不懂φ(n)和第二行相同 11/26 17:15
你需要的只是一張紙跟一枝筆而已
這也是我們念數學比較能拿出來說嘴的 (誤
※ 編輯: lockheart 來自: 123.193.238.230 (11/26 17:40)
推 vity :感謝...我有拿筆跟紙寫但弄不出來, 數學比較差 囧 11/26 18:46