Modular arithmetic exponentiation

Question

Does modulus apply to exponents as well. eg Let $ xy \equiv 1 (mod\;m).$ then does $a^{xy} \equiv a^{1} (mod\;m)$ ?

Answer 1

There is a relationship between congruence of the exponents and congruence of the result, but it is more subtle than that. If you know some group theory, it is easy to see that if $a$ and $b$ are two elements of a group $G$, then $a^x = a^y$ if and only if $x$ and $y$ are congruent modulo the order of $a$ in $G$ (that is, the smallest positive integer $k$ such that $a^k$ equals the identity element of $G$).

In the special case of modular arithmetic, the version of this result which is used most often is Euler's theorem (of which Fermat's little theorem is a special case), which states that if $a$ is relatively prime to $n$ and $x \equiv y \pmod{\varphi(n)}$, then $a^x \equiv a^y \pmod n$. This is because then $a$ is an element of the multiplicative group $\mathbf{Z}_n^*$ of units modulo $n$, whose order is $\varphi(n)$. Note that here there is no "only if", because the order of $a$ in $\mathbf{Z}_n^*$ does not necessarily equal $\varphi(n)$. If it does (that is, if $a$ is a generator of $\mathbf{Z}_n^*$) then of course the "only if" part holds as well.

Answer 2

What is true, by Euler's theorem, is that if $x \equiv y \mod\varphi(m)$ ($\varphi$ is Euler's totient function), then $$a^x\equiv a^y\mod m. $$