一个公式的证明

我想证明的公式是：
Ax≡A(x%phi(C)+phi(C))  (mod C) (x>=phi(C))
其中phi(C)是指C的欧拉函数值,A,C,x均是正整数

首先引入欧拉定理：对于任意的整数n>1,若gcd(a,n)=1,则
aphi(n)≡1(mod n)
由欧拉定理、鸽巢定理以及a0≡1(mod n),知ax%n是一个周期函数，且周期为phi(n)（此处就不证明了，其实我也知道个大概，就当是一个事实吧），注意gcd(a,n)=1这个条件。

总结一下：如果对正整数a,n，有gcd(a,n)=1,则f(x)=ax%n是一个周期函数且周期为phi(n)(注本文的周期不一定是指最小周期)，即f(x)=f(x+phi(n))，记为事实（1）。
还有一个事实就是：ax%n首次出现循环的地方不一定是第一个位置。当gcd(a,n)=1时，第一次出现循环的地方一定是x=0。但如果gcd(a,n)!=1，则不一定啦。在这里先举几个例子：
如a=2,n=7，
x 0 1 2 3 4 5 6 7 8
ax%n 1 2 4 1 2 4 1 2 4
可以知道f(x)=2x%7的周期为3(3|phi(7))且出现循环的地方是当x=0时就开始了。
又如a=2,n=6
x 0 1 2 3 4 5 6 7 8
ax%n 1 2 4 2 4 2 4 2 4
可以知道f(x)=2x%6的周期为1(1|phi(6))但出现循环的地方是x=1时开始的，且应该注意到除了x=0时出现2x%6=1外，以后不会再出现1，这种现象是可以证明的。
先定义几个符号：设START是f(x)=ax%n第一次出现循环的地方，START>=0。下面我们要证明的是：
当START>0时，所有的ai%n的值不会在aj%n出现(i<START,j>=START)，这个记为事实（2）。这是因为如果ai%n==aj%n,则ai+1%n==aj+1%n,ai+2%n==aj+2%n……，可以知道此时开始循环的位置应该是i，而不是START，很显然是矛盾的。
好了现在开始证明上述公式。
若gcd(A,C)=1,则由事实(1)知显然成立。
若gcd(A,C)!=1,则:
设d=gcd(A,C)，A=d*k,dt<=C,dt+1>C,C=m*dt
知:gcd(C,k)=1,1<=m<d
F(x)=Ax%C=((dx%C)*(kx%C))%C,因为gcd(C,k)=1,所以由事实（1）知kx%C的周期为phi(C)。
因此要证明我们所需要的结论，只需要证明g(x)=dx%C的周期也为phi(C)即可。
设di=s*C+ri=s*dt*m+dt*vi，i>=t,vi, ri>=0,则：
di%C=ri 
di-t%m=vi,且ri=dt*vi,从而(ri,vi)一一对应。也就是说
dx%C的周期等于dx-t%m的周期。
又由于1<=m<d，从而gcd(m,d)=1,所以dx-t%m的周期为phi(m)。
因为phi(C)=phi(m*dt)=phi(m)*phi(dt),注意此处利用了条件：gcd(m,dt)=1,所以phi(m)|phi(C),从而phi(C)也是dx-t%m的周期，故dx%C的周期为phi(C)。

综上所述，
Ax≡A(x%phi(C)+phi(C))  (mod C) (x>=phi(C))成立。
至于为什么后面需要加一个条件，原因有二。
由事实(2)知当x<START时，上式显然是不成立的。
在上述证明的过程中，其实一直需要一个条件：i>=t也就是说只有当i>=t的时候，上述推导才是正确的。而当x>phi(C)时，很显然x>=SATRT,从而上式是成立的。
注:此文仅是一时之心得体会，其中定会有许多错误，欢迎各位ACMer批评指出，日后定会修改。