標題:
與x互質自然數
[打印本頁]
作者:
thankyou
時間:
2010-5-11 20:34
標題:
與x互質自然數
請問若x為自然數,求不大於
x且與
x互質的自然數個數?總和?
請參閱上傳檔,謝謝!!
附件:
互質.rar
(2010-5-11 20:34, 6.6 KB) / 該附件被下載次數 7121
https://math.pro/db/attachment.php?aid=183&k=e24357e4eaa5066714a233c092644765&t=1732347468
作者:
weiye
時間:
2010-5-11 21:41
若 \(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\) 亦是。
作者:
thankyou
時間:
2010-5-13 07:55
請問 若互質的個數是奇數時,也能用a與x-a之和恰為x這個方法求總和嗎?
作者:
weiye
時間:
2010-5-13 08:42
你可以自行舉數字實驗看看就知道了。 :-)
我猜你的疑惑是，
『如果小於 \(x\) 且與 \(x\) 互質之數的個數是奇數個，且最中間的 \(\displaystyle\frac{x}{2}\) 不是整數（也就是 \(x\) 是奇數）怎麼辦？』
如果 \(x>1\) 且 \(x\) 是奇數，則你可以推看看 \(\phi(x)\) 必為偶數。
更甚者，你可以試著推得『若 \(x>2\)，則 \(\phi(x)\) 必為偶數。』
所以你要擔心的情況只有 \(x=1,2\) 時，
這兩情況你檢查看看就會發現第二小題是否會成立了。
歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/)
論壇程式使用 Discuz! 6.1.0
附件: 互質.rar (2010-5-11 20:34, 6.6 KB) / 該附件被下載次數 7121