4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @zev thanks for editing the question $\endgroup$ – user350954 Jul 8 '13 at 23:31
9
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks a lot. Is there anyway to prove this beside plugging-in the number? $\endgroup$ – user350954 Jul 8 '13 at 21:53
  • $\begingroup$ @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 $\endgroup$ – Thomas Andrews Jul 8 '13 at 22:44
  • $\begingroup$ I see, thanks a lot, guys $\endgroup$ – user350954 Jul 8 '13 at 23:29
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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