發新話題
打印

標準分解式的題目,求1~720中與720互質的數的個數,及其和

標準分解式的題目,求1~720中與720互質的數的個數,及其和

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

TOP

第一小題:

∵ 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.

多喝水。

TOP

發新話題