Mfrhtyj

What I have done is this:

$aequiv b pmod{2n}$,

$a=b+ctimes2n$, for some $c$,

$a^2=b^2+2btimes ctimes2n+c^2times2^2n^2$,

$a^2-b^2=(btimes c+c^2n)times4n$, then

$a^2equiv b^2pmod{2^2n}$.

I think that this is right: what I DON’T understand is how to generalize this to:

$aequiv bpmod{kn}Rightarrow a^kequiv b^k pmod{k^2n}$.

Please give me a hint.

Since $aequiv bpmod{kn}$, we have
$$a=b+ckn$$
for some integer $c$. Now taking the $k$th power on both sides, we have
$$a^k=(b+ckn)^k.$$
By the binomial theorem, the right hand side is given by
$$(b+ckn)^k=b^k+sum_{i=1}^k{kchoose i}(ckn)^ib^{k-i}.$$
For $igeq 2$, it is clear that
${kchoose i}(ckn)^ib^{k-i}$ is divisble by $k^2n$. On the other hand, for $i=1$, we have
${kchoose i}(ckn)^ib^{k-i}=ck^2nb^{k-1}$, which is also divisble by $k^2n$. Therefore, by the above equality, we have
$$(b+ckn)^k=b^k+k^2nN$$
for some integer $N$. Combining all these, we have
$$a^k=(b+ckn)^k=b^k+k^2nN,$$
that is
$$a^kequiv b^k pmod{k^2n}.$$

Hint $ $ It's a special case of: $ $ a root of a polynomial is a double root if the derivative vanishes.

Thus to prove that $rm kmid a-b Rightarrow k^2 mid a^k-b^k = (a-b) dfrac{a^k-b^k}{a-b}, $ it suffices to prove

that $rm,k,$ divides the second factor. $ $ Theorem $Rightarrow$ it is $rm,equiv, (a^k)'equiv color{#c00}k, a^{k-1}equiv,0 pmod{!color{#c00}k}. $ QED

Theorem $ $ For $rm R$ a ring and $rm,f(x)in R[x]quad $ [Universal Polynomial Derivative Formula]

$$rmbegin{eqnarray}{}&rm g(x,y) &=&rm frac{f(x)-f(y)}{x-y} in R[x,y]\[.3em]
Rightarrow &rm g(x,x) &=&rm f'(x) in R[x]
end{eqnarray}$$

Proof $ $ By $rm,R$-linearity of the derivative it suffices to verify it for a monomial $rm f(x) = x^k,.$

$$begin{eqnarray}{}rm &rm g(x,y) &=&rm frac{x^k-y^k}{x-y}, = x^{k-1} + x^{k-2},y +, cdots, + x,y^{k-2} + y^{k-1}\[.3em]
Rightarrow &rm g(x,x) &=&rm k x^{k-1} = f'(x)quad {bf QED}
end{eqnarray}qquad $$

Remark $ $ To elaborate on a subtlety raised by a comment, $rm,g(x,y)in R[x,y],$ means that $rm ,g(x,y),$ denotes a polynomial in the indeterminates $rm,x,y,,$ whose coefficients lie in the ring $,R,$ (recall that $rm,x-y,$ divides $rm,f(x)-f(y),$ in $rm,R[x,y],$ by the Factor Theorem). Being a polynomial its value is well-defined for all values of $rm ,x,y,$ so we can "evaluate" it at $rm,y = x,$ (as is exemplified by the concrete case $rm,f(x) = x^k$ used in the proof).

In effect we exploit properties of polynomial rings to universally cancel an "apparent singularity" before evaluating. In more complicated contexts this can lead to nontrivial simplifications, e.g. replacing more complicated topological arguments by trivial algebraic arguments, e.g. see the discussion of the purely algebraic proof of Sylvester's determinant identity linked here.

Since

$a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+ldots b^{k-1})$

we need only prove that
$a^{k-1}+a^{k-2}b+ldots + b^{k-1}$ is divisible by $k$. But since $a equiv b (text{mod} k)$ we see that

$ a^{k-1}+a^{k-2}b+ldots + b^{k-1} equiv a^{k-1}+a^{k-1}+ldots +a^{k-1} equiv ka^{k-1} equiv 0 (text{mod} k). $