如何證明尤拉函數？

Question

例如：不大於2400的自然數中，
和2400互質的數有多少數，可用尤拉函數直接解？

2400= 2^5 3 5（質因數有2，3，5）
所以2400互質的數有　2400 (1-1/ 2) (1-1/ 3) (1-1/ 5) = 640
此公式如何證明？

Thank 雨軒,but我還有一些疑問,如下:
(內容)解釋這個算式 2400*(1-1/2)-在2400個數中 不能被2整除的就是單數 例如 1. 3.5.7.9...2399 有1200個,再把1200個*(1-1/3)=1200-1200*1/3=800個 就是代表這些單數中不能被3整除的數,例如:1.5.7.11..2399 共有800個.
Q1:扣掉能被2整除的數後,剩1200個奇數,這1200個數並不是1~1200,所以如何能知,有1/3的比例為3的倍數呢..難道是把1,3,5,7,9,11,..
列出後,再用觀察法,觀察出有1/3的比例為3的倍數嗎?

thank Rex's answer:
but A=p^a*q^b 很容易用排容 因式分解 去得 A互質且不大於 A者就是=A(1-p)(1-q).butＡ的質因數如有5個是否又要重用因式分解去証出
A=(1-p)(1-q)(1-r)(1-y)(1-u)這樣的因式分解應該要做好幾小時?請問要如何去推廣證明當A有5 or 6 or 10個質因數時,,公式的規則還是一樣?
麻煩賜教了..

Answer 1

TO匿名於
2006-12-11 23:30:09 補充之
Q1:扣掉能被2整除的數後,剩1200個奇數,這1200個數並不是1~1200,所以如何能知,有1/3的比例為3的倍數呢..難道是把1,3,5,7,9,11,..
列出後,再用觀察法,觀察出有1/3的比例為3的倍數嗎?




Sol:
1200(1-1/3)其實乘開就是1200-1200/3
也就是說這1200個,去減掉其中還可以被3整除的數
這樣的意思~!^^

2008-04-28 00:16:47 補充：
TO匿名您於2006-12-23 21:52:21之補充:

thank Rex's answer:
but A=p^a*q^b 很容易用排容 因式分解 去得 A互質且不大於 A者就是=A(1-p)(1-q).butＡ的質因數如有5個是否又要重用因式分解去証出
A=(1-p)(1-q)(1-r)(1-y)(1-u)這樣的因式分解應該要做好幾小時?請問要如何去推廣證明當A有5 or 6 or 10個質因數時,,公式的規則還是一樣?
麻煩賜教了..





SOL:

同上述我講的,意思一樣

Answer 2

這個式子其實不用 用到證明耶.....
直接用想法就可以理解這個式子的來源


2400的互質數 就是不可以讓質因數在約化的數....

現在已經可以知道2400是由 2^5*3*5組合而成
舉個例:只要一個數字 不能被2 3 5 整除的 就是2400的互質數
例如:11 13 17 19 等等.....

好 要解釋這個算式了 2400*(1-1/2)----在2400個數當中 不能被2整除的數有幾個...簡單的說 就是單數 例如 1. 3.5.7.9......2399 有1200個

再把1200個*(1-1/3)=800個 就是代表 在這些單數中 不能被3整除的數
例如:1.5.7.11.......2399 共有800個

再把這800個*(1-1/5)=640個 就是這些數 不可被5整除的
例如:1.7.11..........2399
所以就是640個互質數

那為什麼 1-1/2 或是1-1/3 1-1/5就是代表不可被整除的數呢?
因為把所有的數當作1(這是一個比例的值).....那1當中不可被2整除的 就可以用1-1/2的比例來表示 把數值分成 單數 偶數 所以剛好是各佔一半......被3整除的數 也剛好是所有數的三分之ㄧ...同理被5整除的數 也是所有數的五分之ㄧ.....

此提需要的是理解~~~

2006-12-15 14:22:37 補充：
回答:在1200個奇數當中 你可以把它分類 你把3個數字例如1.3.5看成一團 7.9.11 看一團 是不是有400團呢?...每一團是不是剛好只有一個可以被3整除~~~400團裡 各有一個被3整除 那就是要減掉400被3整除的數字 1200個-400個=800個嚕~~可以用分類法 來將數字分類唷~5的話也是一樣的意思~....扣掉整除3的數字 剩下 1.5 7.11 13.17 .......有400團~