How to prove that if $a\equiv b \pmod{2n}$ then $a^2\equiv b^2 \pmod{2^2n}$

What I have done is this:

$a\equiv b \pmod{2n}$,

$a=b+c\times2n$, for some $c$,

$a^2=b^2+2b\times c\times2n+c^2\times2^2n^2$,

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

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

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

$a\equiv b\pmod{kn}\Rightarrow a^k\equiv b^k \pmod{k^2n}$.

-

migrated from crypto.stackexchange.comDec 1 '11 at 13:30

This question came from our site for software developers, mathematicians and others interested in cryptography.

Hi @gurghet - I've migrated your question here as it has no direct relation to cryptography as is - so this is the best place to get a good answer. –  user892 Dec 1 '11 at 13:32

Since $a\equiv b\pmod{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{k\choose i}(ckn)^ib^{k-i}.$$ For $i\geq 2$, it is clear that ${k\choose i}(ckn)^ib^{k-i}$ is divisble by $k^2n$. On the other hand, for $i=1$, we have ${k\choose 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^k\equiv b^k \pmod{k^2n}.$$

-
Thanks but I’m not sure about the binomial theorem. Is that right? I think it misses a $b^{k-i}$ in the sum. –  gurghet Dec 1 '11 at 16:01
It works anyway! Thanks! –  gurghet Dec 1 '11 at 16:09
@gurghet: Yes, you are right! I missed the term $b^{k-i}$. See my edited answer. Thanks! –  Paul Dec 1 '11 at 21:52

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

Thus to prove that $\rm\ \ k\ |\ a-b\ \Rightarrow\ k^2\ |\ 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 k\ a^{k-1}\equiv\:0 \pmod{k}.\$ QED

THEOREM $\$ For $\rm R$ a ring and $\rm\:f(x)\in R[x]\quad\$ [Universal Polynomial Derivative Formula]

$$\rm\begin{eqnarray}{}&\rm g(x,y)\ &=&\rm\ \frac{f(x)-f(y)}{x-y}\ \in\ R[x,y]\\ \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}\\ \Rightarrow\ &\rm g(x,x)\ &=&\rm\ k\ x^{k-1}\: =\ f'(x)\qquad {\bf QED} \end{eqnarray}$$

-
It is worth emphasizing that $g(x,y)=\dfrac{f(x)-f(y)}{x-y}\in R[x,y]$ is NOT the imperative "take (f(x)-f(y)) and divide by (x-y)", but the polynomial in two variables (that's what "$\in R[x,y]$" means) which when multiplied by (x-y) results in f(x)-f(y) -- this is why g(x,x) is not undefined. –  Vladimir Sotirov Feb 11 '12 at 17:39

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

-