4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user892
    Dec 1, 2011 at 13:32

3 Answers 3

9
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ This is a special case of the proof of the double root test - as explained in my answer. $\endgroup$ Mar 24, 2023 at 20:22
8
$\begingroup$

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\ \ k\mid 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 $\rm\,g.\,$ Theorem $\Rightarrow\rm\, g\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]

$$\rm\begin{align}\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]\\[.5em] \Rightarrow \ \ \rm \frac{f(x)-f(y)}{x-y}&\rm\equiv\, f'(x)\pmod{\! x-y} \end{align}\qquad\qquad$$

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 mentioned in 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 $\rm\,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.

Corollary $\rm\ \ (fg)' = fg' + f'g\quad $ [Derivative Product Rule]

$\begin{align}{\bf Proof}\rm\ \ \ \ \ \ \dfrac{f(x)g(x)-f(y)g(y)}{x-y}\, &\rm =\, f(x) \,\dfrac{g(x)-g(y)}{x-y} + \dfrac{f(x)-f(y)}{x-y}\, g(y)\\[.5em] \rm \overset{\large \rm y\ =\ x}\Longrightarrow\ \ (f(x)g(x))' &\rm =\, f(x)\,g'(x) + f'(x)\,g(x)\ \ \ \text{by evaluating at }\rm y = x \end{align}$

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 11, 2012 at 17:39
  • $\begingroup$ @VladimirSotirov Actually it does denote the result of that polynomial division. But evaluating it at "apparent singularities" requires that we compute the quotient before we evaluate it. I added a remark elaborating on this subtlety. $\endgroup$ Jan 4, 2019 at 16:16
  • $\begingroup$ See also LTE. $\endgroup$ Mar 24, 2023 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .