# Show that if $a \equiv b\pmod{kn}$, then $a^k\equiv b^k\pmod{k^2n}$ [duplicate]

Problem

Show that if $$a \equiv b\pmod{2n}$$, then $$a^2\equiv b^2\pmod{4n}$$. More generally, show that if $$a \equiv b\pmod{kn}$$, then $$a^k\equiv b^k\pmod{k^2n}$$. [Introduction to Higher Arithmetic, ex. 2.1]

Proof of the first statement

Note that $$2n \mid a - b\implies 2n (a + b)\mid a^2 - b^2$$ but the $$\pmod{2n}$$ congruence implies that $$a$$ and $$b$$ are of the same parity and so $$2\mid (a + b)$$ which implies that $$2n \cdot 2\mid 2n (a + b)\mid a^2 - b^2$$ or $$a^2 = b^2\pmod{4n}$$.

Attempt at proof of the general case

Multiplying $$a \equiv b\pmod{kn}$$ by itself $$k$$ times, we get $$a^k \equiv b^k\pmod{kn}$$, but it is still needed to prove that $$k$$ divides $$a^k - b^k$$. It maybe stands reasonable to consider the following expansion: $$(a - b) ^ k = a^k - {k \choose 1} a^{k-1}b^1 + {k \choose 2} a^{k-2}b^2 - \cdots \mp {k \choose 1} a^1b^{k-1} \pm b^k$$ Under $$\pmod{kn}$$, we can replace any $$b$$ with $$a$$ and vice versa, which might be useful. Maybe the trick is to sum binomial coefficients to a number (or two numbers) which are divisible by $$k$$. But sum over all of coefficients is $$2^k$$, which is not necessarily divisible by $$k$$.

So, I got stuck here.

## 1 Answer

Note that $$a\equiv b\pmod{kn}\implies a=b+kln$$ for some integer $$l$$. Then $$a^k-b^k=(b+kln)^k-b^k=\binom k1b^{k-1}kln+\binom k2b^{k-2}(kln)^2+\cdots+(kln)^k$$ Every term has a factor of $$k^2n$$ from $$(kln)^t$$ for $$1 but $$\dbinom k1=k$$ so $$k^2n\mid (a^k-b^k)$$.