modular exponentiation where exponent is 1 (mod m)

Question

Suppose I know that $ax + by \equiv 1 \pmod{m}$, why would then, for any $0<s<m$ it would hold that $s^{ax} s^{by} \equiv s^{ax+by} \equiv s \pmod{m}$?

I do not understand the last step here. Is it some obvious exponentiation rule I'm overlooking here?

Thanks, John.

Answer 1

It's false. $2*5 + 1*7 = 17 \equiv 1 \pmod{4}$, $0<2<4$ and $2^{17} \equiv 0 \pmod{4}$.

However, what is true is that for $s$ and $m$ coprime, $s^{\phi(m)} \equiv 1 \pmod{m}$, where $\phi$ is Euler's totent function (http://en.wikipedia.org/wiki/Euler%27s_totient_function).

$s^{\phi(m)+1} \equiv s \pmod{m}$ holds even if $s$ and $m$ are not coprime.

Answer 2

Counterexample: Let $m=3$, $ax+by=4$. It is not the case that $2^4\equiv 2\pmod{3}$. So even primality of $m$ is not sufficient.

Remark: It is hard to guess what the intended result is. Perhaps this: If $s$ is relatively prime to $m$ and $ax+by\equiv 1\pmod{\varphi(m)}$, then $s^{ax+by}\equiv s\pmod{m}$.