標題: 標準分解式的題目，求1~720中與720互質的數的個數，及其和 [打印本頁]

---

作者: hank930502    時間: 2007-9-9 21:07     標題: 標準分解式的題目，求1~720中與720互質的數的個數，及其和

1到720的自然數中,求
(1)與720互質者共有?個
(2)承(1),其和為?

---

作者: weiye    時間: 2007-9-9 23:38

第一小題：

∵ 720=2^4 × 3^2 × 5

∴ 與720互質者，就是要求不能是 2,3,5 的倍數

1~720 裡面共 720 數，

不過要扣掉 2的倍數的個數，扣掉 3 的倍數的個數，扣掉 5 的倍數的個數，

再加上重複扣的 2×3 的倍數的個數，加上重複扣的 2×5 的倍數的個數，加上重複扣的 3×5 的倍數的個數，

最後發現只要是 2×3×5 的倍數，會因為扣三次加三次，所以根本沒有扣到，故要再扣掉 2×3×5 的倍數的個數，

所以 1~720裡面與720互質者個數

　  = 720 - [720/2] - [720/3] - [720/5] + [720/(2×3)]+ [720/(2×5)] + [720/(3×5)] - [720/(2×3×5)]
　　（上面的中括弧表是高斯符號，不過因為 720 可以被 2×3×5 整除，所以其實有沒有寫高斯符號都一樣，所以如下）


　 =  720 - 720/2 - 720/3 - 720/5 + 720/(2×3)+ 720/(2×5) + 720/(3×5) - 720/(2×3×5)

　 = 720(1 - 1/2)(1 - 1/3)(1 - 1/5) （把這三個括弧乘開，就會發現跟上面是一樣的）

　 = 192

結論公式：若 n = p1^k1 × p2^k2 × p3^k3 × .... ×pr^kr 為標準分解式，

　　　　　則，在 1 到 n 的自然數中，與 n 互質的數有 n × (1 - 1/p1) × (1 - 1/p2) × ...... × (1 - 1/pr) 個




第二小題，

先來個觀念就是　(a, 720) = 1 與  (720-a, 720)=1 互為充要條件 (就是可以互推啦。)

∵ (a, 720) = 1 與  (720-a, 720)=1 可以互相推導到對方

∴ 若 a 是所有與 720 互質的數之中最小的，則 720-a 就是所有與 720 互質的數之中最大的；

　 若 a 是所有與 720 互質的數之中第二小的，則 720-a 就是所有與 720 互質的數之中第二大的；

　 若 a 是所有與 720 互質的數之中第三小的，則 720-a 就是所有與 720 互質的數之中第三大的；





若所有與 720 互質的數由小排到到是 a1 < a2 < a3 < ... < a192 (第一小題剛剛算過共有192個數)

假設所有與 720 互質的數之和為 S, 則

S = a1 + a2 +  ... + a191 + a192

也可以這樣由大加到小

S = a192 + a191 + ... + a2 + a1

上兩式相加，

可得 2 S = (a1+a192) + (a2+a191) + ......+ (a191+a2) + (a192+a1)
　　　　= 720 + 720 + ...... + 720 + 720
　　　　= 720 × 192

S = 720 × 192 / 2 = 69120







結論公式：若 n = p1^k1 × p2^k2 × p3^k3 × .... ×pr^kr 為標準分解式，

　　　　　且在 1 到 n 的自然數中，與 n 互質的數有 m 個(就是上一小題的結論公式)，

　　　　　則，此 m 個數的和為 n × m / 2.

---

歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)

論壇程式使用 Discuz! 6.1.0