欧拉函数（二）

此文章纯属原创，内容来源：北大老师的视频教学..

把这个定理的证明弄明白真不容易啊，懂了这个定理，个人觉得欧拉函数就真的不难了...

定理：若 m, n 是两个互质的整数，x, y 分别是通过模 m, n 的简化剩余系，则 n*x + m*y 是通过 m*n 的简化剩余系.

换种写法：x = { x1,x2,x3,x4.... xE(m)} 是mod m 简化剩余系

y = { y1,y2,y3,y4..... xE(n)} 是mod n 简化剩余系

现在要证明：m*yi + n*xj { i = 1,2,3,4..E(m) ；j = 1,2,3，...E(n) } 是关于 n*m 的简化剩余系

即证明：1：与 n*m 互质

2：不同余

3：关于 n*m 的简化剩余系可以写成m*yi + n*xj { i = 1,2,3,4..E(m) ；j = 1,2,3，...E(n) }形式

证明1：因为（m,n）=1; { x1,x2,x3,x4.... xE(m)} 是mod m 简化剩余系,

==>（m,xj）=1; ==> ( m, n*xj ) =1; ==>

有 带余除法可得 ( a, b ) = ( a, b+a*r ) ==> ( m, m*yi + n*xj ) = 1; (1)

因为（m, n）=1; ( n, yi ) = 1; ==> ( n,m*yi ) = 1; ==>( n, m * yi + n * xj ) =1; (2)

由（1）（2）可以得 ( m*n, m*yi + n*xj ) =1;

证明2 ：假定 m*yi + n*xj 与 m*yu+n*xv 是mod m*n不同余的，那么就要证明 yi==yu 且 xj == xv ;

因为 同余，所以有 m*n | m * ( yi - yu ) + n * ( xj - xv ) ;

因为 m|m*n ，n|n*m ==>m | m * ( yi - yu ) + n * ( xj - xv ) ; ==> m | n*( xj - xv ); ==> m | ( xj - xv );

==>n | m * ( yi - yu ) + n * ( xj - xv ) ; ==> n | m*( yi - yu ); ==> n | ( yi - yu );

又因为 x = { x1,x2,x3,x4.... xE(m)} 是mod m 简化剩余系

y = { y1,y2,y3,y4..... xE(n)} 是mod n 简化剩余系

xj - xv mod m 余数一定小于 m

yi - yu mod n 余数一定小于 n

所以yi == yu ， xj == xv ;

证明3：任意取一个整数 a ( 0 <= a <= m*n - 1 ), ( m,n ) =1;

则存在 s*m + n*t =1; 两边同时乘以 a 得a*s*m + a*n*t = a;

设 y = s*a, x = a*t; 则有：m*y + n*x = a;

那现在证明：任何一个 a 和 m*n 互质的数 即（m*n，a）= 1; （3）

若 ( n, y ) = 1 并且（m,x）= 1（其中x, y一定是上面x,y简化剩余系中的数据 ）;

则 和 m * n 互质的数值一定可以写成：m*yi + n*xj 这种形式

那证明（3）（m*n，m*y+n*x）= 1； ==> ( m,m*y+n*x ) = 1; ==> ( m, n*x ) = 1; ==> ( m,x ) = 1;

==> ( n,m*y+n*x ) = 1; ==> ( n, m*y ) = 1; ==> ( n, y ) = 1;

证完！！

那现在我们来看下：n*m的简化剩余系 m*yi + n*xj 表示

m*y1+n*x1， m*y2+n*x1， m*y3+n*x1...............m*yE(n)+x1;

m*y1+n*x2， ........... ............. ..................
m*y1+n*x3， ......... ............. ................

m*y1+n*x4， .......... ............. ..............

..... ........... ............ ....................

.... .............. ............ ..............

m*y1+n*xE(m) ................. ............. m*yE(n) + n*xE(m);

所以很容易看出来 E( n*m ) = E( n ) * E( m ) ; 前提是（m,n）= 1;

所以就得到了这个非常重要的推论...