数论学习——欧拉函数与中国剩余定理

欧拉函数

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

定理 11.1 ($\phi$函数公式)

(a) 如果$p$是素数且$k ≥ 1$,则

(b) 如果$\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 - a_2 \equiv 0 \mod mn$,而又因为$m,n$互素,所以我们可以得到

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

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

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

    我们便找到了一个解$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$,下面的同余方程有解。

设$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$。方程的解表示为:

在模$M$的意义下,方程组有唯一解,为:

证明过程

主要参考 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$,那么我们可以得到方程组:

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