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

I want to calculate $A^B\bmod c$ (here $A$, $B$ and $c$ are all integers) and $B$ is very large like $10^{1000000}$ (such as a problem like FZU1759), and I have read many solutions about it but got the formula $A^x\equiv A^{x\bmod \varphi (c)+\varphi (c)} \bmod c (x\geq \varphi (c))$ without any proofs.

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

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

Here $\varphi(x)$ is the Euler's totient function, and $(a,b)$ means the Greatest common divisor of $a$ and $b$.

I wonder how to prove it, thanks.

-

Notice that: $$\text{If p is prime then }p^{\varphi(c)}\equiv p^{2\varphi(c)} \pmod{c}.$$ The proof is obvious:
if $p\nmid c$, $p^{\varphi(c)}\equiv p^{2\varphi(c)}\equiv 1 \pmod{c}$
if $p\mid c$, let $c:=p^kc'\ (k\in\mathbb{N^+}, p\nmid c')$,
since $\varphi(c)=\varphi(p^k)\varphi(c')\geq\varphi(p^k)=p^{k-1}(p-1)\geq k$, we have $p^k\mid p^{\varphi(c)}$
and, $p^{\varphi(c)}=(p^{\varphi(c')})^{\varphi(p^k)}\equiv 1\pmod{c'}$, we have $c'\mid p^{\varphi(c)}-1$
so $c\mid p^{\varphi(c)}(p^{\varphi(c)}-1)\Rightarrow p^{\varphi(c)}\equiv p^{2\varphi(c)}\pmod{c}$.
Hence, $$A^{\varphi(c)}=\prod\limits_{p\mid A}(p^{\varphi(c)})^k\equiv\prod\limits_{p\mid A}(p^{2\varphi(c)})^k=A^{2\varphi(c)}\pmod{c}$$ $\Rightarrow \forall k\in\mathbb{N^+},A^{\varphi(c)}\equiv A^{k\varphi(c)}\pmod{c}$
$\Rightarrow \forall x\geq \varphi(c),A^x=A^{k\varphi(c)+x\pmod{ \varphi(c)}}\equiv A^{\varphi(c)+x\pmod{\varphi(c)}}\pmod{c}$

-
Thanks a lot. Could you tell me how to understand $p^{k-1}(p-1)\geq k$? – Jingyi Xu Jan 19 '13 at 15:13
@JingyiXu Hint: to show $\phi(p^k)\ge k$ it suffices to find $k$ integers in $[1,p^k]$ that are coprime to $p,$ e.g. $1,\,1+p,\,1+p^2,\ldots,1+p^{k-1}\ \$ – Math Gems Jan 19 '13 at 18:35
Nice answer! +1 – P.. Jan 19 '13 at 22:29
@JingyiXu $p^{k-1}(p-1)\geq 2^{k-1}\geq k$. 2nd floor's note is more beautiful :-) – Shane Chern Jan 20 '13 at 9:03