Prove that if $[a]_n = [r]_n$, then $[a^k]_n = [r^k]_n$ Let $a, r, n \in \mathbb{Z}$ with $n>0$. Prove that if $[a]_n = [r]_n$, then for all $k \in \mathbb{N}$, $[a^k]_n = [r^k]_n$.
So far this is what I have:
Proof: Let $a, r, n \in \mathbb{Z}$ with $n>0$. Assume $[a]_n = [r]_n$. Note that then $n| a-r$, i.e., $a-r=nx$ for some $x\in \mathbb{Z}$. Our proof strategy will be by induction on $k$. Base Case: Let $k=1$. Then $[a^1]_n = [r^1]_n$ since $[a^1]_n=[a]_n$ and $[r^1]_n=[r]_n$. Induction Step: Let $k>1$. Assume by induction that $[a^{k-1}]_n = [r^{k-1}]_n$. Then $n|a^{k-1}-r^{k-1}$, i.e., $a^{k-1}-r^{k-1}=nz$ for some $z\in \mathbb{Z}$. 
From there I have trouble. I know I need to get to $a^k-r^k=ny$ for some $y\in \mathbb{Z}$ since then $[a^k]_n = [r^k]_n$. I am not sure how to get there from the information that I have. 
 A: Proof by induction, using the hint given by Brian. 
By taking two base cases we see:
$$k=0 \implies [a^0]_n = [r^0]_n = [1]_n$$
and by our hypothesis
$$k = 1 \implies [a^1]_n = [r^1]_n$$
Therefore our base case is established for some $k-1$ and $k-2$. Now let us show the case for $k$:
By the definition of congruence, for $z \in \mathbb{Z}$, we have 
$$a^{k-1} - r^{k-1} = nz $$
and therefore by some algebra we get
$$a^k - ar^{k-1} = n(az)$$
$$ra^{k-1} - r^k = n(rz)$$
The addition of these equations yields 
$$a^k - r^k + ra^{k-1} - ar^{k-1} = n(za + zr)$$
bringing some terms to the RHS and factoring yields
$$a^k - r^k = ar(r^{k-2} - a^{k-2}) + n(za + zr)$$
But notice that the term containing powers of $k-2$ has been shown in the base case to be a congruence relation and therefore we can rewrite again (for $x \in \mathbb{Z}$):
$$\begin{align}a^k - r^k &= ar(nx) + n(za + zr) \\ &= n(rnx + za + zr) \end{align}$$
Where we see that $n$ is multiplied by a factor which is the sum of integers and is therefore also an integer. Thus, because congruence is an equivalence relation, $a^k \equiv r^k$ (mod $n$) and $r^k \equiv a^k$ (mod $n$). So finally we have that $[r^k]_n = [a^k]_n$.
A: Multiply both sides of $a^{k-1} - r^{k-1} = nz$ by $a$ and $r$ to get two equations
$$a^k - ar^{k-1} = n(az) \\ ra^{k-1} - r^k = n(rz)$$
Now add them and solve for $a^k - r^k$:
$$a^k-r^k = n(az+rz) - ra(a^{k-2} - r^{k-2})$$
Can you think of how to proceed from here? (hint: you may want to go back to your base case and show the equation is true for $k=0$, or maybe $k=2,$ to use a slightly stronger induction)
A: 1)
$[r]_n = [a]_n \iff a = r+ nm$ for some integer $m$.
So $a^k = (r+nm)^k = \sum_{j=0}^k{k\choose j}r^{k-j}(nm)^j$
$= r^k + \sum_{j=1}^k{k\choose j}r^{k-j}(nm)^j=r^k + n(\sum_{j=1}^k{k\choose j}r^{k-j}n^{j-1}m^j)$
And so $a^k - r^k =  n(\sum_{j=1}^k{k\choose j}r^{k-j}n^{j-1}m^j)$ and $[a^k]_n= [r^k]_n$
2)
You've probably already proven if $[a]_n=[r]_n$ and $[b]_n=[s]_n$ then $[ab]_n= [rs]_n$.  (If not prove it now[1]).
And clearly by induction if you have any number of $[a_i]_n=[r_i]_n$ and  then 
$[a_1a_2]=[r_1r_2]$ so $[(a_1a_2)a_3]=[(r_1r_2)r_3]$ and so on so $[\prod a_i]=[\prod r_i]$.
And so $ [a^k]=[a\cdot a\cdot a\cdot ......\cdot a]=[r\cdot r\cdot r\cdot ......\cdot r]=[r^k] $.
.......
[1] $a= r + mn$ and $b =s + jn$ for some $m,j$ so $a+b=(r+s) + n(m+j)$
