# If $m \equiv n \pmod{A}$, then $s^m \equiv s^n \pmod{A}$?

I'm kind of stuck with the following assignment:

Prove: If $m \equiv n \pmod{A}$, then $s^m \equiv s^n \pmod{A}$

I tried $m = k_1 \times A + r$ , and $n = k_2 \times A + r$ , then $s^m = s^{k_1 \times A + r}$, but not sure how to proceed ...

Really appreciate any hints. Thanks a lot.

• @zev thanks for editing the question – user350954 Jul 8 '13 at 23:31

This is false as stated - consider $A=3$, $m=4$, $n=1$, and $s=2$. We have $$4\equiv 1\bmod 3$$ but $$16\not\equiv 2\bmod 3.$$

• Thanks a lot. Is there anyway to prove this beside plugging-in the number? – user350954 Jul 8 '13 at 21:53
• @user350954 Disproving such statements is easiest to do using examples. There are, in fact, some $m,n,A$ such that the above is true for all $s$, they are just rare – Thomas Andrews Jul 8 '13 at 22:44
• I see, thanks a lot, guys – user350954 Jul 8 '13 at 23:29

It is not true like that.

You probably meant ($\gcd(A,s)=1$ and $m\equiv n\pmod{\varphi(A)}$) implies $s^m\equiv s^n\pmod{A}$, where $\varphi$ is Euler's totient function, i.e. $\varphi(A)$ is the number of coprimes to $A$ (within one total residue class).

• Thanks for the answer Berci, but it's too advanced for me ... – user350954 Jul 8 '13 at 21:54