Doubt regarding modulo arithmetic

general
1

In the question 438E

editorial: http://codeforces.com/blog/entry/12513

I couldn’t understand this part:

if
S_n(z)^2 ≡ F(z) (mod z^n)

and

F(z) ≡ (1/2(S_n(z)+F(z)S_n(z)^{-1}))^2 (mod z^{2n})

then

S_{2n}(z) ≡ 1/2(S_n(z)+F(z)S_n(z)^{-1}) (mod z^{2n})

does this mean that if

X^2 ≡ Y^2(modk)

then

X ≡ Y(modk)

however for X=3,Y=4,k=7 it violates

edit:

if

X^2 ≡ Y^2(modk)

So either

X ≡ Y(modk)

or

X ≡ -Y(modk)

so now my question is how do we know 1st case is true?

thanx in advance!!

2 
however for X=3,Y=4,k=7 it violates

Even your {X}^{2}={Y}^{2}(mod k) doesnt hold for this. {X}^{2}=9 and {Y}^{2} mod K=2

Can you clarify a bit there please? :slight_smile:

3

I am soo sorry,i’ve updated my question.

4

I think I am still missing something. Shouldn’t it go on lines of-

{X}^{2}\%k \equiv {Y}^{2}\%k
\implies ({X}^{2}-{Y}^{2})\%K=0
\implies [(X-Y)*(X+Y)]\%k=0
\implies either X=Y+ck or X=ck-Y

We can see that the first condition holds in former case, and second condition holds in latter (as (-Y)\%K=(Y\%K+K)\%K)

5

Yeah i know this,however i couldn’t proof why did we took X=Y(modK) in :

if
S_n(z)^2 ≡ F(z) (mod z^n)

and

F(z) ≡ (1/2(S_n(z)+F(z)S_n(z)^{-1}))^2 (mod z^{2n})

then

S_{2n}(z) ≡ 1/2(S_n(z)+F(z)S_n(z)^{-1}) (mod z^{2n})

I mean it could be the case ,that X=-Y(modk)