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.