Prove that if $[a]_n = [r]_n$, then $[a^k]_n = [r^k]_n$

Question

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.

Answer 1

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)

Answer 2

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

Answer 3

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