【摘要】：定义11.7 欧拉函数φ（n＞1）表示比n小且与n互素的正整数的个数。 由于n=15，比15小且与15互素的正整数有1，2，4，7，8，11，13，14共8个，故φ=8。，pe中p的倍数共有pe/p=pe-1个，为p，2p，…4）若gcd（m，n）=1，则φ=φφ定理11.11 设n=pn11×p2n2×…×pntt，则由欧拉函数的性质3）和4）直接可得。，18所以φ=18 求φ。
定义11.7 欧拉函数φ（n）（n＞1）表示比n小且与n互素的正整数的个数。
【例11-20】 求φ（15）。
【解析】 由于n=15，比15小且与15互素的正整数有
1，2，4，7，8，11，13，14共8个，故φ（15）=8。
欧拉函数具有如下性质：
1）当n是素数时，有
φ（n）=n-1
因为比n小且与n互素的正整数有1，2，…，n-1。
2）当n=pq，且p和q是互异的素数时，则有
φ（n）=φ（p）×φ（q）=（p-1）×（q-1）
从1到pq-1的数中，与pq不互素的元素只有
p，2p，3p，…，（q-1）p及其q，2q，…，（p-1）q
所以
φ（n）=pq-1-[（q-1）+（p-1）]=（p-1）×（q-1）
3）当n=pe，且p是素数，e是正整数时，有(www.xing528.com)
φ（n）=pe-pe-1=pe-1（p-1）
与pe不互素的正整数即为与p不互素的正整数，只能是p的倍数，在1，2，…，pe中p的倍数共有pe/p=pe-1个，为p，2p，…，pe-1p。
4）若gcd（m，n）=1，则
φ（mn）=φ（m）φ（n）
定理11.11 设n=pn11×p2n2×…×pntt，则
由欧拉函数的性质3）和4）直接可得。
【例11-21】 求φ（19）。
【解析】 由于比19小且与19互素的正整数有1，2，…，18
所以φ（19）=18
【例11-22】 求φ（187）。
【解析】 由于187=11×17
φ（11）=10，φ（17）=16
所以φ（187）=10×16=160
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
