# How to prove $A^x\equiv A^{(x\: mod\: \varphi (c)+\varphi (c))}(mod\: c)(x\geq \varphi (c))$? [closed]

I want to caculate $A^B\: mod\: c$ and $B$ is very large like $10^{1000000}$(such as FZU1759), and I have read many solutions about it but got the formula $A^x\equiv A^{(x\: mod\: \varphi (c)+\varphi (c))}(mod\: c)(x\geq \varphi (c))$ without any proofs.

I know $A^x\equiv A^{(x\: mod\: \varphi (c))}(mod\: c)(x\geq \varphi (c))$ is right because of the Euler's theorem. But when $(A, c)\neq1$ we should plus the $\varphi (c)$ and I don't know why.

For example, $4^{10}\equiv 4^{10\: mod\: \varphi (6)+\varphi (6)}\equiv 4(mod\: 6)$, if I don't plus the $\varphi (6)$ I will get 0.

I wonder how to prove it, thanks.

-

## closed as off topic by Emil Jeřábek, Felipe Voloch, Andreas Blass, Gerry Myerson, Dan PetersenJan 18 '13 at 22:42

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

This website is for questions of research interest. –  Gerry Myerson Jan 18 '13 at 22:22

Decompose $A=BC$ where $\gcd(B,c)=1$ and all the primes that divide $C$ also divide $c$. Then you can prove that $B^x \equiv B^{(x\mod \phi(c))} \equiv B^{\phi(c) + (x\mod \phi(c))} \pmod c$ by Euler's extension of Fermat's little theorem.
As for $C$, as long as $k$ exceeds the exponent of any prime dividing $c$ (in particular, as long as $k$ exceeds $\phi(c)$), you can show that $C^k \equiv C^{k+\phi(c)}\pmod c$. (This can be shown by looking at $C\pmod{c_1}$ and $C\pmod{c_2}$ separately, where $c=c_1c_2$, $\gcd(c_1,C)=1$, and the primes dividing $c_2$ and $C$ are identical.)