欧拉函数

针对前面所学习的欧拉公式，如果我们无法快速有效的计算出来欧拉函数\(\phi\)的值的话，我们就不能充分发挥欧拉公式的作用，下面给出欧拉函数的计算方法。

定理 11.1 （\(\phi\)函数公式）

1. 如果\(p\)是素数且\(k ≥ 1\)，则 \[\phi(p^k) = p^k - p^{k-1}\]

2. 如果\(\gcd (m,n) =1\)，则\(\phi(mn) = \phi(m) \phi(n)\)

证明过程

证明 (a)素数情况的证明用全部数\(p^k\)减去与\(p\)不互素的\(p,2p,3p, \cdots , (p^{k-1}-1)p, p^{k-1}p\)，共\(p^{k-1}\)个。所以是\(p^{k} - p^{k-1}\)，余下要证明(b),

构造两个集合，集合 A，\(\{ a: 1 \le a \le mn , \gcd (a, mn) = 1\}\)，集合 B， \(\{ (b,c): 1 \le b \le m, \gcd(b,m) =1 , 1 \le c \le n, \gcd(c,n) = 1 \}\)，显然两个集合的大小分别为\(\phi(mn)\)和\(\phi(m) \phi(n)\)

对于下面这种 A->B 的映射关系 \(a \mod mn \to (a \mod m, a \mod n\))，我们可以证明它是一一映射的，由此也就得到了\(\phi(mn) = \phi(m) \phi(n)\)

1. 单射的证明（A 集合的不同数对应 B 集合的不同序对），假设原像为\(a_1,a_2\)，他们在 B 中有相同的映像，则有：

   \[a_1 \equiv a_2 \mod m\] \[a_1 \equiv a_2 \mod n\]

   可以推导得\(a_1 - a_2 \equiv 0 \mod mn\)，而又因为\(m,n\)互素，所以我们可以得到

   \[a_1 \equiv a_2 \mod mn\]

2. 满射的证明（B 集合的每个序对适合 A 集合的某个数），根据映射式以及对于任意\(b,c\)已知值：

   \[ a \equiv b \mod m\] \[ a \equiv c \mod n\]

   这个同余式组有解，这个用到了中国剩余定理的简化版（两个方程），给出证明。

   因为\(\gcd(m,n) = 1\)，可计算（存在逆元）\(m^{-1} ,n^{-1}\)，满足\(m^{-1}m \equiv 1 \mod n , n^{-1}n \equiv 1 \mod m\)，则有

   \[bn^{-1}n+cm^{-1}m \equiv b \mod m\] \[bn^{-1}n+cm^{-1}m \equiv c \mod n\]

   我们便找到了一个解\(a = bn^{-1}n+cm^{-1}m\)，实际上可证明在\(\mod mn\)条件下这个解是唯一的，见后面完整版中国剩余定理的证明。

中国剩余定理

《数论概论》这本书上只介绍到了两方程的情况，查阅 Wiki 等资料拓展学习了一下。

定理 11.2 （中国剩余定理简化版） 设\(m_1,m_2, \cdots ,m_n\)是整数，其中任意两数两两互质，则对任意整数：\(a_1,a_2, \cdots , a_n\)，下面的同余方程有解。

\[ \begin{equation} \left\{ \begin{array}{lr} x \equiv a_1 , \mod m_1 & \\ x \equiv a_2 , \mod m_2 & \\ x \equiv a_3 , \mod m_3 & \\ \cdots \\ x \equiv a_n , \mod m_n & \\ \end{array} \right. \end{equation} \]

设\(M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^{n}m_i\)，并设\(M_i = M/m_i, t_i \equiv M_i^{-1} \mod m_i\)。方程的解表示为： \[x = a_1t_1M_1 + a_2t_2M_2 + \cdots + a_nt_nM_n + kM = kM + \sum_{i=1}^{n}a_it_iM_i , k \in Z\] 在模\(M\)的意义下，方程组有唯一解，为： \[x = \sum_{i=1}^{n}a_it_iM_i\]

证明过程

主要参考 Wiki 上的证明方法，中国剩余定理- 维基百科，自由的百科全书

证明 由于\({\forall i,j ,i \ne j, \gcd(m_i,m_j) =1 }\)，所以对于\(\gcd(m_i,M_i) = 1\)，所以均存在\(t_i\)使得\(t_iM_i \equiv 1 \mod m_i\)，即\(M_i\)模\(m_i\)的数论倒数，考察\(a_it_iM_i\)这个乘积：

对于\({\forall j \in \{ 1, 2, \cdots , n\}}\)，会出现两种情况：

• \(j = i\)时，\(a_it_iM_i \equiv a_i \mod m_i\)，后两项乘积是 1
• \(j \ne i\)时，\(a_it_iM_i \equiv 0 \mod m_j\)，原因是\(m_j \mid M_i\)。

那么我们不难得出，\(x = \sum_{i=1}^{n}a_it_iM_i\)符合方程组。

下证在模\(M\)条件下解的唯一性。

假设存在\(x_1,x_2\)都是方程组的解且\(1 \le x_1,x_2 \le M, x_1 \ne x_2\)，那么我们可以得到方程组：

\[ \begin{equation} \left\{ \begin{array}{lr} x_1 - x_2 \equiv 0 , \mod m_1 & \\ x_1 - x_2 \equiv 0 , \mod m_2 & \\ x_1 - x_2 \equiv 0 , \mod m_3 & \\ \cdots \\ x_1 - x_2 \equiv 0 , \mod m_n & \end{array} \right. \end{equation} \]

因而可以得到\((M = \prod_{i=1}^{n} m_i) \mid \vert x_1 -x_2 \vert\)，而由条件\(\vert x_1 - x_2 \vert \le M-1\)显然矛盾，所以在模\(M\)下解是唯一的。