與x互質自然數
[font=新細明體][size=12pt]請問若x為自然數,求不大於[/size][/font][size=12pt] [/size][font=新細明體][size=12pt]x且與[/size][/font][size=12pt][/size][font=新細明體][size=12pt]x互質的自然數個數?總和? [/size][/font]
[font=新細明體][size=12pt]請參閱上傳檔,謝謝!![/size][/font] 若 \(x\) 為自然數，定義 \(\phi(x)\) 為不大於 \(x\) 且與 \(x\) 互質的自然數個數.
此為 Euler 的 phi function，基礎數論的書都會提到。
第一小題：
先證 Euler's phi function 是 multiplicative 的算數函數（亦即，對互質的自然數 \(m,n\) 恆有 \(\phi(mn)=\phi(m)\phi(n)\)），
接著就可以容易推得該結論。
詳見：[url]http://math.ntnu.edu.tw/~li/ent-html/node11.html[/url]
第二小題：
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\) 時，
這兩情況你檢查看看就會發現第二小題是否會成立了。
頁:
[1]