Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by Emil Jeřábek, Felipe Voloch, Andreas Blass, Gerry Myerson, Dan Petersen Jan 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

1 Answer 1

up vote 1 down vote accepted

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.)

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.