標準分解式的題目，求1~720中與720互質的數的個數，及其和
1到720的自然數中,求(1)與720互質者共有?個
(2)承(1),其和為? 第一小題：
∵ 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)]
[color=DimGray]（上面的中括弧表是高斯符號，不過因為 720 可以被 2×3×5 整除，所以其實有沒有寫高斯符號都一樣，所以如下）[/color]
= 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) [color=Gray]（把這三個括弧乘開，就會發現跟上面是一樣的）[/color]
= 192
[color=Blue]結論公式：若 n = p1^k1 × p2^k2 × p3^k3 × .... ×pr^kr 為標準分解式，[/color]
[color=Blue] 則，在 1 到 n 的自然數中，與 n 互質的數有 n × (1 - 1/p1) × (1 - 1/p2) × ...... × (1 - 1/pr) 個[/color]
第二小題，
先來個觀念就是 (a, 720) = 1 與 (720-a, 720)=1 互為充要條件 [color=DimGray](就是可以互推啦。)[/color]
∵ (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 [color=DimGray](第一小題剛剛算過共有192個數)
[/color]
假設所有與 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
[color=Blue]結論公式：若 n = p1^k1 × p2^k2 × p3^k3 × .... ×pr^kr 為標準分解式，[/color]
[color=Blue] 且在 1 到 n 的自然數中，與 n 互質的數有 m 個[/color][color=DimGray](就是上一小題的結論公式)[/color][color=Blue]，[/color]
[color=Blue] 則，此 m 個數的和為 n × m / 2.[/color]
頁:
[1]