Show that, if $a \equiv b \pmod{kn}$, then $a^k \equiv b^k \pmod{k^2 n}$.

Question

I am trying to improve my proof-writing. Is this proof easy to follow? How could it be ordered more clearly or succinctly? I have broken it into several Lemmas as follows:

Lemma 1

$a \equiv b \pmod{kn} \implies a-b=knC_1$.

Lemma 2

Since $b$ must be congruent to some integer $0\leq r\leq k-1,$ and $$a \equiv b \pmod{kn} \implies a \equiv b \pmod{k}$$ then $$b \equiv r \pmod{k} \implies a \equiv r \pmod{k}.$$

From this we get $$a^J b^R \equiv r^{k-1} \pmod{kn},$$

where $J,R\in \{0,1,...,k-1\}$ such that $J+R=k-1$.

Lemma 3

By the difference of two $nth$ powers $$a^k - b^k = \Big(a-b\Big)\Big(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}\Big).$$

Note that $$\Big(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}\Big)=\displaystyle\sum_{r=0}^{k-1} a^{k-1-r} b^r$$

and so there are $k$ terms in the sum.

Lemma 4

By Lemma 2 $$a^J b^R =kC_i + r^{k-1}.$$

Combining this with Lemmas 1 and 3 we get

$$ a^k - b^k = knC_1 \Big( kC_2 +kC_3 +...+kC_{k+1} +kr^{k-1}\Big)=k^2 nC_{k+2}.$$

Thus, assuming $$a \equiv b \pmod{kn} \implies a^k \equiv b^k \pmod{k^2 n}. \quad \square$$

---

Edited proof:

By the difference of $kth$ powers $$a^k - b^k = \Big(a-b\Big)\Big(a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1}\Big).$$

By our assumption $a-b=knC_1$ for some integer $C_1$.

For the factor on the right note that $$a \equiv b \pmod{kn} \implies a \equiv b \pmod{k} \implies a^m \equiv b^m \pmod{k}$$ for any natural number $m$.

Using the above and the fact that $a \equiv a \pmod{k}$ we get $$a^{k-1-r}b^r \equiv a^{k-1} \pmod{k},$$ for any $0\leq r \leq k-1$. Hence $$a^{k-1} + a^{k-2}b + ... + ab^{k-2} + b^{k-1} \equiv a^{k-1}+a^{k-1}+...+a^{k-1} \equiv ka^{k-1} \equiv 0 \pmod{k}.$$

Since the factor on the right is a multiple of $k$, we can write $$a^k - b^k = \Big(knC_1\Big)\Big(kC_2\Big)=k^2(nC_1 C_2),$$ for integers $C_1 , C_2$.

Thus, assuming $$a \equiv b \pmod{kn} \implies a^k \equiv b^k \pmod{k^2 n}. \quad \square$$

Answer 1

Rather confusing. Here are some comments

Lemma 1: don't forget quantifiers. You mean to say that if $a\equiv b\pmod{kn}$ then $a-b=knC_1$ for some integer $C_1$.

Lemma 2: what is the modulus? The only modulus you have mentioned in this part is $kn$, and it is certainly not true that $b$ must be congruent to something from $0$ to $k-1$ modulo $kn$.

Lemma 3: I think you have the most important point here.

Lemma 4: also pretty confusing.

---

Suggestion: whenever you think you have a proof, read through it carefully, work out what is actually important, and see if you can simplify the proof by omitting anything unnecessary.

Here is an outline which you may care to develop and write up carefully.

1. If $a\equiv b\pmod{kn}$ then $a\equiv b\pmod k$.
2. $a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})$.
3. In the above, $a-b$ is a multiple of $kn$. We look at the second factor modulo $k$: $$a^{k-1}+a^{k-2}b+\cdots+b^{k-1}\equiv a^{k-1}+a^{k-1}+\cdots+a^{k-1}\equiv ka^{k-1}\equiv0\ .$$
4. Using 2. and 3., $a^k-b^k$ is a multiple of $(kn)k$, and we are finished.