Question

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.

Answer 1

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