欧拉函数
2-100欧拉函数表n φ(n)2 13 24 25 46 27 68 49 610 411 1012 413 1214 615 816 817 1618 619 1820 821 1222 1023 2224 825 2026 1227 1828 1229 2830 831 3032 1633 2034 1635 2436 1237 3638 1839 2440 1641 4042 1243 4244 2045 2446 2247 4648 1649 4250 2051 3252 2453 5254 1855 4056 2457 3658 2859 5860 1661 6062 3063 3664 3265 4866 2067 6668 3269 4470 2471 7072 2473 7274 3675 4076 3677 6078 2479 7880 3281 5482 4083 8284 2485 6486 4287 5688 4089 8890 2491 7292 4493 6094 4695 7296 3297 9698 4299 60100 40
什么是欧拉函数
欧拉函数就是指:对于一个正整数n,小于或等于n的正整数中与n互质的正整数个数(包括1)的个数,记作 φ ( n ) 。在数论，对正整数 n，欧拉函数是小于或等于 n 的正整数中与 n 互质的数的数目（因此φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为 Euler’s totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为 1,3,5,7 均和 8 互质。从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。通式：(其中 p1, p2……pn 为 x 的所有质因数，x 是不为 0 的整数)定义 φ(1)=1（和 1 互质的数(小于等于 1)就是 1 本身）。注意：每种质因数只有一个。比如 12=2*2*3 那么φ（12）=φ（4*3）=φ（2^2*3^1）=（2^2-2^1）*（3^1-3^0）=4若 n 是质数 p 的 k 次幂，，因为除了 p 的倍数外，其他数都跟 n 互质。设 n 为正整数，以 φ(n)表示不超过 n 且与 n 互素的正整数的个数，称为 n 的欧拉函数值φ：N→N，n→φ(n)称为欧拉函数。欧拉函数是积性函数——若 m,n 互质，特殊性质：当 n 为奇质数时，, 证明与上述类似。
