数学-数论-欧拉函数

Posted by

欧拉函数

定义

对于正整数\(n\),欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目,写作\(\varphi (n)\)。特别的,\(\varphi (1)=1\)。

性质

  1. 若\(n\)、\(m\)互质,则\(\varphi (nm)=\varphi (n)\varphi (m)\);

  2. 若\(n\)为质数,则\(\varphi (n)=n-1\)。

  3. \(\varphi (p^{a})=p^{a}-p^{a-1}\)(\(p\)为质数)。

    证明:

    \([1,p^{a}]\)内总共有\(p^{a}\)个数,其中,有\(p\)这个因子的数有\(p^{a-1}\)个。

  4. \(\varphi (n)=n \prod_{i=1}^{k} \frac{p_i -1}{p_i}\)

    证明:

    由算术基本定理,设:

    \[n=\prod_{i=1}^{k} p_i^{a_i}\]

    其中\(p_i\)为质数,且\(p_i|n\);

    又:\(\varphi (p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}\)(性质3);

    把\(p_i^{a_i-1}\)提出来,得\(\varphi (p_i^{a_i})=(p_i -1)p_i^{a_i-1}\)。

    当\(i\not =j\)时,由于\(p_i^{a_i},p_j^{a_j}\)不存在共同的因子,故它们俩互质;

    于是,求\(\varphi (n)\)可以直接把\(k\)个\(\varphi (p_i^{a_i})\)相乘(性质1);

    可以初步得出

    \[\varphi (n)=\prod_{i=1}^{k} (p_i -1)p_i^{a_i-1}\]

    分子分母同时乘\(p_i\),得

    \[\varphi (n)=\prod_{i=1}^{k} \frac{(p_i -1)p_i^{a_i}}{p_i}\]

    又因为

    \[n=\prod_{i=1}^{k} p_i^{a_i}\]

    \[\varphi (n)=n \prod_{i=1}^{k} \frac{p_i -1}{p_i}\]

  5. 如果\(i\ mod\ pri_j\not =0\),那么\(\varphi (i\cdot pri_j)=\varphi (i)\cdot (pri_j-1)\)(积性函数的性质);

    如果\(i\ mod\ pri_j=0\),那么\(\varphi (i\cdot pri_j)=\varphi (i)\cdot pri_j\)。

    证明:

    引理:若\(gcd(a,b)=1\),则\(gcd(a+b,b)=1\)。

    简单证明如下:

    假设\(gcd(a+b,b)=d\not =1,a+b=xd,b=yd\);

    得\(a+yd=xd\);

    即\(a=(x-y)d\);

    得\(gcd(a,b)=d\not =1\),与\(gcd(a,b)=1\)矛盾,故假设不成立。

    在\([1,i]\)有\(\varphi (i)\)个数与\(i\)互质,而根据以上定理,在\([i+1,2i]\)也有\(\varphi (i)\)个数与\(i\)互质,在\([2i+1,3i]\)也有\(\varphi (i)\)个数与\(i\)互质……

    于是可得,在\([1,i\cdot pri_j]\)有\(\varphi (i)\cdot pri_j\)个数与\(i\)互质。

    而又因为\(pri_j\)是\(i\)的因子,故与\(i\)互质的数必定与\(pri_j\)互质,也与\(i\cdot pri_j\)互质。

  6. 欧拉定理是一个关于同余的性质:若正整数\(a,n\)互质,则\(a^{\varphi (n)}\equiv 1\quad (mod\ n)\)。

    证明:

    令\(Z_n=\{x_1,x_2,\ldots x_{\varphi (n)}\}\)即\(n\)的质因子集。

    设\(S=\{y_i|y_i=ax_i\ mod\ n\},\quad i\in [1,\varphi (n)]\);

    当\(i\not =j\)时,\(x_i\not =x_j\),故\(ax_i\ mod\ n\not =ax_j\ mod\ n\);

    又因为\(gcd(a,n)=1\),\(gcd(x_i,n)=1\),故\(gcd(ax_i,n)=1\),故\(ax_i\ mod\ n\in Z_n\);

    得出\(Z_n=S\)。

    \[a^{\varphi (n)}\prod_{i=1}^{\varphi (n)} x_i\equiv \prod_{i=1}^{\varphi (n)} ax_i\equiv \prod_{i=1}^{\varphi (n)} x_i\quad (mod\ n)\]

    观察同余式两端,由消去律可得\(a^{\varphi (n)}\equiv 1(mod\ n)\)。

    故得证。

  7. 费马小定理:若\(p\)为质数,且\(a\)与\(p\)互质,则\(a^{p-1}\equiv 1\quad (mod\ p)\)。

    欧拉定理在\(p\)为质数时的特殊情况。

  8. 小于\(n\)的与\(n\)互质的数的和为\(\frac{n\cdot\varphi(n)}{2}\)。

    引理:若\(gcd(n,n-i)=1\),则\(gcd(n,i)=1\)。

    假设\(gcd(n,i)=d\not =1,n=xd,i=yd\);

    得\(n-i=(x-y)d\);

    得\(gcd(n,n-i)=d\not =1\),与\(gcd(n,n-i)=1\)矛盾,故假设不成立。

    于是可得与\(n\)互质的数是成对出现的,且每一对的和为\(n\)。

  9. \(n=\sum_{d|n}\varphi (d)\)

    证明在莫比乌斯函数及莫比乌斯反演

求解算法

线性筛

扩展

\[a^b\equiv
\begin{align}
\begin{cases}
a^{b\ mod\ \varphi(p)} & gcd(a,p)=1\\
a^b & gcd(a,p)\neq1,b<\varphi(p)\\
a^{b\ mod\ \varphi(p)+\varphi(p)} & gcd(a,p)\neq1,b\geq\varphi(p)
\end{cases}
\end{align}\qquad(mod\ p)\]

2 comments

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注