請問若x為自然數,求不大於 x且與
x互質的自然數個數?總和?
請參閱上傳檔,謝謝!!

若 x 為自然數，定義 (x) 為不大於 x 且與 x 互質的自然數個數.

此為 Euler 的 phi function，基礎數論的書都會提到。

第一小題：

先證 Euler's phi function 是 multiplicative 的算數函數（亦即，對互質的自然數 mn 恆有 (mn)=(m)(n)），

接著就可以容易推得該結論。

詳見：http://math.ntnu.edu.tw/~li/ent-html/node11.html


第二小題：

Key：若 a 是小於 x 且與 x 互質的數，則 x−a 亦是。

請問    若互質的個數是奇數時,也能用a與x-a之和恰為x這個方法求總和嗎?

你可以自行舉數字實驗看看就知道了。 :-)

我猜你的疑惑是，

『如果小於 x 且與 x 互質之數的個數是奇數個，且最中間的 x2 不是整數（也就是 x 是奇數）怎麼辦？』

如果 x1 且 x 是奇數，則你可以推看看 (x) 必為偶數。

更甚者，你可以試著推得『若 x2，則 (x) 必為偶數。』

所以你要擔心的情況只有 x=12 時，

這兩情況你檢查看看就會發現第二小題是否會成立了。