請(qǐng)思考以下問(wèn)題:
任意給定正整數(shù)n,請(qǐng)問(wèn)在小于等于n的正整數(shù)之中,有多少個(gè)與n構(gòu)成互質(zhì)關(guān)系?(比如,在1到8之中,有多少個(gè)數(shù)與8構(gòu)成互質(zhì)關(guān)系?)
計(jì)算這個(gè)值的方法就叫做歐拉函數(shù),以φ(n)表示。在1到8之中,與8形成互質(zhì)關(guān)系的是1、3、5、7,所以 φ(n) = 4。
φ(n) 的計(jì)算方法并不復(fù)雜,但是為了得到最后那個(gè)公式,需要一步步討論。
第一種情況
如果n=1,則 φ(1) = 1 。因?yàn)?與任何數(shù)(包括自身)都構(gòu)成互質(zhì)關(guān)系。
第二種情況
如果n是質(zhì)數(shù),則 φ(n)=n-1 。因?yàn)橘|(zhì)數(shù)與小于它的每一個(gè)數(shù),都構(gòu)成互質(zhì)關(guān)系。比如5與1、2、3、4都構(gòu)成互質(zhì)關(guān)系。
第三種情況
如果n是質(zhì)數(shù)的某一個(gè)次方,即 n = p^k (p為質(zhì)數(shù),k為大于等于1的整數(shù)),則
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
這是因?yàn)橹挥挟?dāng)一個(gè)數(shù)不包含質(zhì)數(shù)p,才可能與n互質(zhì)。而包含質(zhì)數(shù)p的數(shù)一共有p^(k-1)個(gè),即1×p、2×p、3×p、...、p^(k-1)×p,把它們?nèi)コ?,剩下的就是與n互質(zhì)的數(shù)。
上面的式子還可以寫(xiě)成下面的形式:
可以看出,上面的第二種情況是 k=1 時(shí)的特例。
第四種情況
如果n可以分解成兩個(gè)互質(zhì)的整數(shù)之積,
n = p1 × p2
則
φ(n) = φ(p1p2) = φ(p1)φ(p2)
即積的歐拉函數(shù)等于各個(gè)因子的歐拉函數(shù)之積。比如,φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
這一條的證明要用到"中國(guó)剩余定理",這里就不展開(kāi)了,只簡(jiǎn)單說(shuō)一下思路:如果a與p1互質(zhì)(a<p1),b與p2互質(zhì)(b<p2),c與p1p2互質(zhì)(c<p1p2),則c與數(shù)對(duì) (a,b) 是一一對(duì)應(yīng)關(guān)系。由于a的值有φ(p1)種可能,b的值有φ(p2)種可能,則數(shù)對(duì) (a,b) 有φ(p1)φ(p2)種可能,而c的值有φ(p1p2)種可能,所以φ(p1p2)就等于φ(p1)φ(p2)。
第五種情況
因?yàn)槿我庖粋€(gè)大于1的正整數(shù),都可以寫(xiě)成一系列質(zhì)數(shù)的積。
根據(jù)第4條的結(jié)論,得到
再根據(jù)第3條的結(jié)論,得到
也就等于
這就是歐拉函數(shù)的通用計(jì)算公式。比如,1323的歐拉函數(shù),計(jì)算過(guò)程如下:
更多建議: