Basic question about mod I'm having a tough time understanding why $(a^x \bmod p)^y \bmod p$ is equal to $a^{xy}\bmod p$.
Does this have a mathematical proof? Please advise.
 A: Since this was migrated from SO, I suspect that by "$n\bmod m$", you mean the remainder when $n$ is divided by $m$, typically with $0\le n<m$ (possibly negative if $n<0$).  In this interpretation, let's call $n=a^x\bmod p$, which means that $a^x=n+kp$ or $n=a^x-kp$ for some integer $k$ and with $0\le n<p$.  Now (assuming $y$ is an integer), when you take $(a^x\bmod p)^y=n^y=(a^x-kp)^y$ and expand the rightmost expression using the binomial theorem, you'll get $a^{xy}$ plus a whole bunch of terms that have a factor of $p$ and thus don't affect $(a^x\bmod p)^y\bmod p$, so that your end result will be equal to $a^{xy}\bmod p$.
A: You should be able to prove from first principles that $(a\mod p)(b \mod p) \mod p = (ab)\mod p$ for all integers $a, b$. Now you can prove your statement by induction on $y$.
A: All you need to prove is that if $a \equiv b \mod n$ then $a^m \equiv b^m \mod n$.
While this follows by induction from the product rule as mentined above, you can also prove it directly the following way:
In $n$ divides $a-b$, then $n$ also divides
$$(a-b)[a^{n-1}+a^{n-2}b+...+b^{n-1}]= a^n-b^n \,.$$
A: The proof is clearer using congruences vs. normal forms (least remainders). To translate between the two languages note that $\rm\ A\ mod\ m\ =\ a\ mod\ m\ \iff\ A\equiv a\ \ (mod\ m)\:,\:$ i.e. $\rm\ m\ |\ A-a\:.\:$ Now the sought result follows by induction after applying the following ubiquitous
Congruence Product Rule $\rm\ \ A\equiv a,\ B\equiv b\ \Rightarrow\ AB\equiv ab\ \ (mod\ m)$
Proof $\rm\:\ \ m\: |\: A-a,\ B-b\:\ \Rightarrow\:\ m\ |\ (A-a)\ B + a\ (B-b)\ =\ AB - ab $
A: It's usually simpler to work with congruences rather than the binary $\bmod$ operator, and then go tot he binary operator at the end.
Given an integer $n$, we say that $a\equiv b\pmod{n}$ ("$a$ is congruent to $b$ modulo $n$") if and only if $n$ divides $b-a$. It is easy to show that "congruent modulo $n$" is an equivalence relation; that is, $a\equiv a \pmod{n}$ for every $a$; if $a\equiv b\pmod{n}$ then $b\equiv a\pmod{n}$; and if $a\equiv b\pmod{n}$ and $b\equiv c\pmod{n}$, then $a\equiv c\pmod{n}$.
Proposition. The following are equivalent:


*

*$a\equiv b\pmod{n}$.

*$n$ divides $a-b$.

*$a = b+kn$ for some integer $k$.

*$a$ and $b$ have the same remainder when divided by $n$.


Proof. (1)$\Leftrightarrow$(2): This is the definition.
(2)$\Rightarrow$(3): Since $n$ divides $a-b$, there exists $k$ such that $nk = a-b$; hence $a=b+nk$, as claimed.
(3)$\Rightarrow$(4). Let $b=qn+r$, with $0\leq r\lt |n|$. Then $a=b+kn = qn+r+kn = (q+k)n+r$, with $0\leq r\lt |n|$. By the uniqueness clause of the division algorithm, it follows that $r$ is also the remainder of $a$ when divided by $n$.
(4)$\Rightarrow$(2). If $a=qn+r$, $b=pn+r$, $0\leq r\lt|n|$, then $a-b = (q-p)n$, so $n$ divides $a-b$. QED
Condition (4) tells you that if you have an equality between expressions involving remainders of numbers, they are equivalent to the corresponding congruence. In your question, this means that the desired equality holds if and only if $a^{xy}$ is congruent to $(a^x)^y$ modulo $n$, which holds because they are in fact equal. But to get it more carefully:
Corollary. Let $n$ be a positive integer. Then every integer $a$ is congruent modulo $n$ to one and only one of $0$, $1$, $2,\ldots,n-1$. 
Proof. Dividing $a$ by $n$ we have $a = qn + r$, $0\leq r\lt n$. Then $a\equiv r\pmod{n}$; so every integer is congruent to at least one of $0,\ldots,n-1$. For uniqueness, let $i,j$ be integers, $0\leq i,j\leq n-1$ such that $i\equiv j\pmod{n}$. Without loss of generality, assume $i\leq j$. Then $0\leq j-i\lt n$, and $n$ divides $j-i$; the only possibility is for $j-i=0$, so $j=i$. QED
Definition. Let $a$ be an integer, $n$ a positive integer. We define $a\bmod n$ ("$a$ mod $n$") to be the unique nonnegative integer $i$, $0\leq i\lt n$, such that $a\equiv i\pmod{n}$. That is, $a\equiv (a\bmod n)\pmod{n}$, and $0\leq (a\bmod n)\lt n$.
Theorem. If $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then $a+c\equiv b+d\pmod{n}$ and $ac\equiv bd\pmod{n}$.
Proof. Our hypothesis are that $n$ divides both $a-b$ and $c-d$. Therefore, it divides their sum, $(a+c)-(b+d)$ (which implies $a+c\equiv b+d\pmod{n}$); it also divides $(a-b)c$ and $b(c-d)$; adding these latter two gives that $ac-bd$ is a multiple of $n$, so $ac\equiv bd\pmod{n}$. QED
Corollary. If $a\equiv b\pmod{n}$, and $r$ is a positive integer, then $a^r\equiv b^r\pmod{n}$.
Now consider $(a^x)^y$ and $a^{xy}$. 
Note that $(a^x)^y = a^{xy}$, so $(a^x)^y\equiv a^{xy}\pmod{n}$. Also, since $a^x \equiv (a^x\bmod n)\pmod{n}$, then $(a^x)^y \equiv (a^x\bmod n)^y\pmod{n}$. Since $a^{xy}\equiv (a^x)^y\pmod{n}$, and $(a^x)^y\equiv (a^x\bmod n)^y\pmod{n}$, then $a^{xy}\equiv (a^x\bmod n)^y\pmod{n}$.
And since $a^{xy}\equiv (a^x\bmod n)^y\pmod{n}$, then $a^{xy}$ and $(a^x\bmod n)^y$ have the same remainder when divided by $n$; that is,
$$a^{xy}\bmod n = (a^x\bmod n)^y \bmod n,$$
as desired.
