Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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}$

share|improve this answer
    
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
3  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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