Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Please give me a hint.

share|improve this question

migrated from crypto.stackexchange.com Dec 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. –  Ninefingers Dec 1 '11 at 13:32
add comment

3 Answers 3

up vote 8 down vote accepted

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
2  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.