Re: [中學] 方程式有根求範圍與函數問題
※ 引述《satanky (太陽下的雨水)》之銘言：
: (2)
: 設不大於n，且與n互質之自然數個數，以f(n)表示，設為p、q相異質數。
: f(pq)=_____
: 1 1
: ANS:f(pq)=pq(1- ─)(1- ─)
: p q
: 這兩題想了好久
: 希望高手可以幫忙解答
: 謝謝～
把 1 ... pq 的數字這樣寫下來：
0p+1 0p+2 0p+3 ... 0p+(p-1) 0p+p
1p+1 1p+2 1p+3 ... 1p+(p-1) 1p+p
2p+1 2p+2 2p+3 ... 2p+(p-1) 2p+p
...
(q-2)p+1 (q-2)p+2 (q-2)p+3 ... (q-2)p+(p-1) (q-2)p+p
(q-1)p+1 (q-1)p+2 (q-1)p+3 ... (q-1)p+(p-1) (q-1)p+p
同一行的數除以p的餘數都一樣，而我們知道 (x+by, y) = (x, y)
因此 (ap+r, p) = (p, r)，p是質數，所以每一列剛好 p-1 個數與 p 互質。
接下來看行。因為 p 與 q 互質，所以我們知道 0, p, 2p, 3p, ..., (q-1)p
恰巧構成模 q 的一個完全剩餘系，而無論全部的數同時加幾，所得仍然是一個
模 q 的完全剩餘系。依據剛才 "洽有 p-1 個數與 p 互質" 相同的理由，這 q
個數中洽有 q-1 個數與 q 互質，所以與 pq 互質的數總數就是 (p-1)(q-1)。
得到 f(pq) = (p-1)(q-1) = pq * (1 - 1/p)(1 - 1/q)。但這個函數這樣寫是
有理由的，定義歐拉函數φ(n)的值為不超過 n 而與 n 互質的正整數個數，透過
推導，我們知道它是個積性函數。也就是說，對於任意互質正整數 m, n，
φ(mn) = φ(m)φ(n)，而對於任一個質數的次方 p^α，我們可以算出來
φ(p^α) = p^α - p^{α-1} = p^α(1 - 1/p)，這是因為在 1, 2, ..., p^α
的數當中，與 p^α 不互質的數一定是 p 的倍數，而在這幾個數中 p 的個數
總共有 p^{α-1}個。
透過這兩點，我們可以算出對任意的 n = p_1^e_1 * p_2^e_2 * ... * p_r^e_r
而言，φ(n) = p_1^e_1(1 - 1/p_1) * p_2^e_2(1 - 1/p_2) ... * p_r^e_r(1 - 1/p_r)
= n(1 - 1/p_1)(1 - 1/p_2)...(1 - p_r)。
所以你的 f(pq) 帶進去就是 pq(1 - 1/p)(1 - 1/q)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.33.98
→
08/28 14:23, , 1F
08/28 14:23, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 5 篇)：