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

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

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

第一小題：

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

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

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


第二小題：

Key：若 \(a\) 是小於 \(x\) 且與 \(x\) 互質的數，則 \(x-a\) 亦是。

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

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

我猜你的疑惑是，

『如果小於 \(x\) 且與 \(x\) 互質之數的個數是奇數個，且最中間的 \(\displaystyle\frac{x}{2}\) 不是整數（也就是 \(x\) 是奇數）怎麼辦？』

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

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

所以你要擔心的情況只有 \(x=1,2\) 時，

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