Math Pro 數學補給站's Archiver

能忍耐的人,才能達到他所希望達到的目的。

thankyou 發表於 2010-5-11 20:34

與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]

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)\)),

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

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


第二小題:

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\) 時,

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

頁: [1]

論壇程式使用 Discuz! Archiver 6.1.0  © 2001-2007 Comsenz Inc.