第一小題:
∵ 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.