欧拉函数

1. 欧拉函数定义

欧拉函数 ϕ(n){\phi(n)} 表示的是小于等于 nn 且和 nn 互质的正整数的个数。(易知 ϕ(1)=1{\phi(1) = 1}

2. 欧拉函数公式

对于任意整数 nn,若其质因数分解结果为 n=p1k1p2k1pnkn{n = p_1^{k_1}p_2^{k_1} \cdots p_n^{k_n}},则欧拉函数公式为

ϕ(n)=n(11p1)(11p2)(11pn){\begin{array}{c} \phi(n) = n(1-{1 \over p_1})(1- {1 \over p_2}) \cdots (1-{1 \over p_n}) \end{array}}

3. 欧拉函数性质

(1)欧拉函数为积性函数。(对于数论函数 f(n){f(n)} 不恒等于 0,当 (m,n)=1{(m,n) = 1} 时,满足 f(mn)=f(m)f(n){f(mn) = f(m)f(n)} ,则称 f(n){f(n)} 为积性函数)

ϕ(mn)=ϕ(m)ϕ(n),(m,n)=1{\begin{array}{c} \phi(mn) = \phi(m)\phi(n), \, (m,n) = 1 \end{array}}

(2)若 (m,n)=d{(m,n) = d},则

ϕ(mn)=dϕ(m)ϕ(n)ϕ(d){\begin{array}{c} \phi(mn) = d{\phi(m)\phi(n) \over \phi(d)} \end{array}}

(3)若 mmnn 满足 mn{m|n},则

ϕ(mn)=mϕ(n){\begin{array}{c} \phi(mn) = m \cdot \phi(n) \end{array}}

(4)若 mmnn满足 mn{m|n},则

ϕ(m)ϕ(n){\begin{array}{c} \phi(m)|\phi(n) \end{array}}

(5)对于质数 pp,其欧拉函数公式为

ϕ(p)=p1{\begin{array}{c} \phi(p) = p-1 \end{array}}

(6)对于质数 pppk{p^k}的欧拉函数公式为

ϕ(pk)=(p1)pk1{\begin{array}{c} \phi(p^k) = (p-1)p^{k-1} \end{array}}

(7)小于等于 nn 且整除 nn 的所有正整数的欧拉函数值之和等于 nn,即

n=dnϕ(d){\begin{array}{c} n = \sum_{d|n}\phi(d) \end{array}}

(8)欧拉定理:若 (a,m)=1{(a,m) = 1},则 aϕ(m)1(modm){a^{\phi(m)} \equiv 1 \, \pmod{m}}

(9)扩展欧拉定理

axaxmodϕ(m)(modm),(a,m)=1axax(modm),(a,m)1x<ϕ(m)axa(xmodϕ(m))+ϕ(m)(modm),(a,m)1xϕ(m){\begin{array}{c} a^x \equiv a^{x \bmod \phi(m)} \pmod{m}, (a,m) = 1 \\ a^x \equiv a^x \pmod{m}, (a,m) \neq 1 \wedge x \lt \phi(m) \\ a^x \equiv a^{(x \bmod \phi(m)) + \phi(m)} \pmod{m}, (a,m) \neq 1 \wedge x \geq \phi(m) \end{array}}


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!