Question

Say that x^2 = y^2 mod n, but x != y mod n and x != −y mod n.

Show that 1 = gcd(x − y, n) implies that n divides x + y, and that this is not possible, Show that n is non-trivial

Answer 1

x² = y² (mod n) implies, n | (x² - y²)

So, n | (x-y)(x+y) ...... (*)

Now, it is given that, x y (mod n) & x - y (mod n)

Now, if 1 = gcd(x-y, n), then, n does not divide (x-y)

Again, from (*) we have, n | (x-y)(x+y)

So, by Euclid's lemma, since, n doesn't divide (x-y), we must have, n | (x+y), which contradicts x - y (mod n)

So this is not possible. Hence n is non-trivial