[挑戰題]互質個數與總和.....小於720 且與720互質的正整數總和

1.小於720 且與720互質的正整數幾個?
2.小於720 且與720互質的正整數總和多少?

請詳細說明為什麼

引用來源連結

 

---

(1)720=2^4x3^2x5

720x(1-1/2)x(1-1/3)x(1-1/5)=192

(2)720x1/2x[720x((1-1/2)x(1-1/3)x(1-1/5)]=69120

用Euler 公式

 

簡單敘述如下:
(1)720=2^4x3^2x5, 表720的質因數有2,3,5
比720小的數中, 2的倍數要扣掉, 3的倍數要扣掉, 5的倍數要扣掉
連續整數中, 每2個數有1個2的倍數, 有1個互質, 所以乘上比例:1/2
連續整數中, 每3個數有1個3的倍數, 有2個互質, 所以乘上比例:2/3
連續整數中, 每5個數有1個5的倍數, 有4個互質, 所以乘上比例:4/5
so, 全部互質的用720x(1-1/2)x(1-1/3)x(1-1/5)=192

詳細證明要用集合

(2)茲以12舉例說明
1~12的數: 1,2,3,4,5,6,7,8,9,10,11,12
其中與12互質的有:1,5,7,11共四個,
最前與最後分一組和為12, 次前與次後分一組和還是12, 和剛好等於最大數
故總何為12x2

換成720也一樣, (互質個數/2)=互質組數, 每組和為720
so 720x1/2x[第一小題答案]=69120