此文章纯属原创，内容来源：北大老师的视频教学..
把这个定理的证明弄明白真不容易啊，懂了这个定理，个人觉得欧拉函数就真的不难了...
定理：若 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;
所以就得到了这个非常重要的推论...
欧拉函数公式若干：
设 a = p1^a1*p2^a2*p3^a3*.....*pk^ak;
则 E(a) = a*( 1-1/p1 ) *( 1-1/p2 )*...*( 1-1/pk );
公式推算就不做了，因为欧拉函数是积性函数，用推论来推就行了...
为了翻译成代码：所以公式变型： E(a) = ( p1-1 )*p1^( a1-1 ) * ( p2-1 ) * p2^( a2-1 ) *........* ( pk-1 )*pk^( ak-1 );
我自己写的丑陋代码，勿喷啦..！！
#include<iostream>
#include<cmath>
using namespace std;
int euler(int n){
int sum=1;
for(int i=2;i*i<=n;i++){
int a=0;
if(n%i==0){
while(n%i==0){
n /= i;
a++;
}
}
if(a){
sum = sum * (i-1) * (int)pow(i*1.0,a-1);
}
}
if(n>1) sum *= (n-1); //// 考虑到最后的数可能是素数，所以一定要加上额
return sum;
}
int main (){
int n;
while(cin>>n,n){
int sum=0;
sum=euler(n);
cout<<sum<<endl;
}
}